Symmetries and Distances : two intriguing challenges in Mathematical Programming
Symétries et Distances : deux défis fascinants dans la programmation mathématique
Résumé
This thesis is mostly dedicated to study and discuss two important challenges existing not only in the field of Mathematical Programming: symmetries and distances. In the background we take a look into Semidefinite Programming (SDP) and its pertinency as one of the major tools employed nowadays to solve hard Mathematical Programs (MP). After the introductory Chapter 1, we discuss about symmetries in Chapter 2 and about distances in Chapter 5. In between them we present two short chapters that we actually prefer to call as entr’actes: their content is not necessarily worthy of publication yet, but they do provide a connection between the two seemingly separate Chapters 2 and 5, which are the ones containing the main contributions of this thesis. It is widely known that symmetric MPs are harder to solve to global optimality using Branch-and-Bound (B&B) type algorithms, given that the solution symmetry is reflected in the size of the B&B tree. It is also well-known that some of the solution symmetries are usually evident in the formulation, which makes it possible to attempt to deal with symmetries as a preprocessing step. Implementation-wise, one of the simplest approaches is to break symmetries by adjoining Symmetry-Breaking Constraints (SBC) to the formulation, thereby removing some symmetric global optima, then solve the reformulation with a generic solver. Sets of such constraints can be generated from each orbit of the action of the symmetries on the variable index set. It is unclear, however, whether and how it is possible to choose two or more separate orbits to generate SBCs which are compatible with each other (in the sense that they do not make all global optima infeasible). In Chapter 2 we discuss and test a new concept of Orbital Independence (OI) that clarifies this issue. The numerical experiences conducted using public MILPs and MINLPs emphasize the correctness and usefulness of the OI theory. Binary Quadratic Programming (BQP) is used to investigate symmetries and SDP in Entr'acte 3. Symmetric Binary Quadratic Programs having a certain symmetry structure are generated and used to exemplify the conditions under which the usage of SBCs is majoritarily advantageous. A preliminary discussion about the impact of symmetries and SBCs in the performance of SDP solvers is also carried out. The Euclidean Steiner Tree Problem is studied in Entr'acte 4. Two models (which are exact reformulations of an existing formulation) are derived, as well as SDP relaxations. A heuristic algorithm based on both the mathematical models and the OI principles presented in Chapter 2 is also proposed. As concerns these methods, preliminary results on a small set of well-known instances are provided. Finally and following up the Distance Geometry subject, in Chapter 5 we cope with the most fundamental problem arising in the field of Distance Geometry, the one of realizing graphs in Euclidean spaces: it asks to find a realization of an edge-weighted undirected graph in RK for some given K such that the positions for adjacent vertices respect the distance given by the corresponding edge weight. The Euclidean Distance Geometry Problem (EDGP) is of great importance since it has many applications to science and engineering. It is notoriously difficult to solve computationally, and most of the methods proposed so far either do not scale up to useful sizes, or unlikely identify good solutions. In fact, the need to constrain the rank of the matrix representing feasible solutions of the EDGP is what makes the problem so hard. Intending to overcome these issues, we propose a two-steps heuristic algorithm based on SDP (or more precisely based on the very recent Diagonally Dominant Programming paradigm) and the explicitly modeling of Rank Constraints. We provide extensive computational testing against randomly generated instances as well as against feasible realistic protein conformation instances taken from the Protein Data Bank to analyze our method.
Cette thèse est consacrée à l’étude et à la discussion de deux questions importantes qui se posent dans le domaine de la Programmation Mathématique: les symétries et les distances. En arrière-plan, nous examinons la Programmation Semidéfinie (PSD) et sa pertinence comme l’un des principaux outils employés aujourd’hui pour résoudre les Programmes Mathématiques (PM) durs. Après le chapitre introductif, nous discutons des symétries au Chapitre 2 et des distances au Chapitre 5. Entre ces deux chapitres, nous présentons deux courts chapitres que nous préférons en fait appeler entr’actes: leur contenu ne mérite pas d’être publié pour le moment, mais ils fournissent un lien entre les deux Chapitres 2 et 5 apparemment distincts, qui contiennent les principales contributions de cette thèse. Il est bien connu que les PMs symétriques sont plus difficiles à résoudre pour l’optimalité globale en utilisant des algorithmes du type Branch-and-Bound (B&B). Il est également bien connu que certaines des symétries de solution sont évidentes dans la formulation, ce qui permet d’essayer de traiter les symétries en tant qu’étape de prétraitement. L’une des approches les plus simples consiste à rompre les symétries en associant les Contraintes de Rupture de Symétrie (CRS) à la formulation, en supprimant ainsi des optima globaux symétriques, puis à résoudre la reformulation avec un solveur générique. Ces contraintes peuvent être générés à partir de chaque orbite de l’action des symétries sur l’ensemble des indices des variables. Cependant, il est difficile de savoir si et comment il est possible de choisir deux ou plus orbites distinctes pour générer des CRSs qui sont compatibles les unes avec les autres (elles ne rendent pas tous les optima globaux infaisables). Dans le Chapitre 2, nous discutons et testons un nouveau concept d’Indépendance Orbitale (IO) qui clarifie cette question. Les expériences numériques réalisées à l’aide de PLMEs et de PNLMEs soulignent l’exactitude et l’utilité de la théorie de l’IO. Programmation Quadratique Binaire (PQB) est utilisée pour étudier les symétries et SDP dans Entr'acte 3. Programmes quadratiques binaires symétriques ayant une certaine structure de symétrie sont générés et utilisés pour illustrer les conditions dans lesquelles l'utilisation de CRSs est avantageuse. Une discussion préliminaire sur l'impact des symétries et des CRSs dans la performance des solveurs PSD est également réalisée. Le Problème Euclidien de l'Arbre de Steiner est étudié dans Entr'acte 4. Deux modèles sont dérivés, ainsi que des relaxations SDP. Un algorithme heuristique basé à la fois sur les modèles mathématiques et sur les principes d'IO présentés au Chapitre 2 est également proposé. Concernant ces méthodes, des résultats préliminaires sur un petit ensemble d'exemples bien connus sont fournis. Finalement, dans le Chapitre 5, nous abordons le problème fondamental qui se pose dans le domaine de la Géométrie de Distance: il s’agit de trouver une réalisation d’un graphe pondéré non orienté dans RK pour un certain K donné, de sorte que les positions pour les sommets adjacents respectent la distance donnée par le poids de l’arête correspondante. Le Problème de la Géométrie de Distance Euclidienne (PGDE) est d’une grande importance car il a de nombreuses applications en science et en ingénierie. Il est difficile de calculer numériquement des solutions, et la plupart des méthodes proposées jusqu’à présent ne sont pas adaptées à des tailles utiles ou sont peu susceptibles d’identifier de bonnes solutions. La nécessité de contraindre le rang de la matrice représentant des solutions réalisables du PGDE rend le problème si difficile. Nous proposons un algorithme heuristique en deux étapes basé sur la PSD (en fait basé sur le paradigme de la PDD) et la modélisation explicite de Contraintes de Rang. Nous fournissons tests informatiques comprenant des instances générées de façon aléatoire ainsi que des exemples réalistes de conformation de protéines.
Origine : Version validée par le jury (STAR)
Loading...