Lagrangian-informed mixed integer programming reformulations

La programmation linéaire en nombres entiers est une approche robuste qui permet de résoudre rapidement de grandes instances de problèmes d'optimisation discrète. Toutefois, les problèmes gagnent constamment en complexité et imposent parfois de fortes limites sur le temps de calcul. Il devient alors nécessaire de développer des méthodes spécialisées afin de résoudre approximativement ces problèmes, tout en calculant des bornes sur leurs valeurs optimales afin de prouver la qualité des solutions obtenues. Nous proposons d'explorer une approche de reformulation en nombres entiers guidée par la relaxation lagrangienne. Après l'identification d'une forte relaxation lagrangienne, un processus systématique permet d'obtenir une seconde formulation en nombres entiers. Cette reformulation, plus compacte que celle de Dantzig et Wolfe, comporte exactement les mêmes solutions entières que la formulation initiale, mais en améliore la borne linéaire: elle devient égale à la borne lagrangienne. L'approche de reformulation permet d'unifier et de généraliser des formulations et des méthodes de borne connues. De plus, elle offre une manière simple d'obtenir des reformulations de moins grandes tailles en contrepartie de bornes plus faibles. Ces reformulations demeurent de grandes tailles. C'est pourquoi nous décrivons aussi des méthodes spécialisées pour en résoudre les relaxations linéaires. Finalement, nous appliquons l'approche de reformulation à deux problèmes de localisation. Cela nous mène à de nouvelles formulations pour ces problèmes; certaines sont de très grandes tailles, mais nos méthodes de résolution spécialisées les rendent pratiques.

Exact Lagrangian cobordism and pseudo-isotopy

Dans cette thèse, on étudie les propriétés des sous-variétés lagrangiennes dans une variété symplectique en utilisant la relation de cobordisme lagrangien. Plus précisément, on s'intéresse à déterminer les conditions pour lesquelles les cobordismes lagrangiens élémentaires sont en fait triviaux. En utilisant des techniques de l'homologie de Floer et le théorème du s-cobordisme on démontre que, sous certaines hypothèses topologiques, un cobordisme lagrangien exact est une pseudo-isotopie lagrangienne. Ce resultat est une forme faible d'une conjecture due à Biran et Cornea qui stipule qu'un cobordisme lagrangien exact est hamiltonien isotope à une suspension lagrangianenne.

Éclatement et contraction lagrangiens et applications

Soit (M, ω) une variété symplectique. Nous construisons une version de l’éclatement et de la contraction symplectique, que nous définissons relative à une sous-variété lagrangienne L ⊂ M. En outre, si M admet une involution anti-symplectique ϕ, et que nous éclatons une configuration suffisament symmetrique des plongements de boules, nous démontrons qu’il existe aussi une involution anti-symplectique sur l’éclatement ~M. Nous dérivons ensuite une condition homologique pour les surfaces lagrangiennes réeles L = Fix(ϕ), qui détermine quand la topologie de L change losqu’on contracte une courbe exceptionnelle C dans M. Finalement, on utilise ces constructions afin d’étudier le packing relatif dans (ℂP²,ℝP²).

Structures quantiques de certaines sous-variétés lagrangiennes non-monotones

Soit (M,ω) un variété symplectique fermée et connexe.On considère des sous-variétés lagrangiennes α : L → (M,ω). Si α est monotone, c.- à-d. s’il existe η > 0 tel que ημ = ω, Paul Biran et Octav Conea ont défini une version relative de l’homologie quantique. Dans ce contexte ils ont déformé l’opérateur de bord du complexe de Morse ainsi que le produit d’intersection à l’aide de disques pseudo-holomorphes. On note (QH(L), ∗), l’homologie quantique de L munie du produit quantique. Le principal objectif de cette dissertation est de généraliser leur construction à un classe plus large d’espaces. Plus précisément on considère soit des sous-variétés presque monotone, c.-à-d. α est C1-proche d’un plongement lagrangian monotone ; soit les fibres toriques de variétés toriques Fano. Dans ces cas non nécessairement monotones, QH(L) va dépendre de certains choix, mais cela sera irrelevant pour les applications présentées ici. Dans le cas presque monotone, on s’intéresse principalement à des questions de déplaçabilité, d’uniréglage et d’estimation d’énergie de difféomorphismes hamiltoniens. Enfin nous terminons par une application combinant les deux approches, concernant la dynamique d’un hamiltonien déplaçant toutes les fibres toriques non-monotones dans CPn.

Quelques propriétés des sous-variétés lagrangiennes monotones : Rayon de Gromov et morphisme de Seidel

Cette thèse présente quelques propriétés des sous-variétés lagrangiennes monotones. On résoud d'abord une conjecture de Barraud et Cornea dans le cadre monotone en montrant que le rayon de Gromov relatif à deux lagrangiennes dans la même classe d'isotopie hamiltonienne donne une borne inférieure à la distance de Hofer entre ces deux mêmes lagrangiennes. Le cas non-monotone de cette conjecture reste ouvert encore. On définit toutes les structures nécessaires à l'énoncé et à la preuve de cette conjecture. Deuxièmement, on définit une nouvelle version d'un morphisme de Seidel relatif à l'aide des cobordismes lagrangiens de Biran et Cornea. On montre que cette version est chaîne-homotope aux différentes autres versions apparaissant dans la littérature. Que toutes ces définitions sont équivalentes fait partie du folklore mais n'apparaît pas dans la littérature. On conclut par une conjecture qui identifie un triangle exact obtenu par chirurgie lagrangienne et un autre dû à Seidel et faisant intervenir le twist de Dehn symplectique.

Source spaces and perturbations for cluster complexes

Dans ce travail, nous définissons des objets composés de disques complexes marqués reliés entre eux par des segments de droite munis d’une longueur. Nous construisons deux séries d’espaces de module de ces objets appelés clus- ters, une qui sera dite non symétrique, la version ⊗, et l’autre qui est dite symétrique, la version •. Cette construction permet des choix de perturba- tions pour deux versions correspondantes des trajectoires de Floer introduites par Cornea et Lalonde ([CL]). Ces choix devraient fournir une nouvelle option pour la description géométrique des structures A∞ et L∞ obstruées étudiées par Fukaya, Oh, Ohta et Ono ([FOOO2],[FOOO]) et Cho ([Cho]). Dans le cas où L ⊂ (M, ω) est une sous-variété lagrangienne Pin± mono- tone avec nombre de Maslov ≥ 2, nous définissons une structure d’algèbre A∞ sur les points critiques d’une fonction de Morse générique sur L. Cette struc- ture est présentée comme une extension du complexe des perles de Oh ([Oh]) muni de son produit quantique, plus récemment étudié par Biran et Cornea ([BC]). Plus généralement, nous décrivons une version géométrique d’une catégorie de Fukaya avec seul objet L qui se veut alternative à la description (relative) hamiltonienne de Seidel ([Sei]). Nous vérifions la fonctorialité de notre construction en définissant des espaces de module de clusters occultés qui servent d’espaces sources pour des morphismes de comparaison.

Représentation et identification des hypersurfaces

L’objectif à moyen terme de ce travail est d’explorer quelques formulations des problèmes d’identification de forme et de reconnaissance de surface à partir de mesures ponctuelles. Ces problèmes ont plusieurs applications importantes dans les domaines de l’imagerie médicale, de la biométrie, de la sécurité des accès automatiques et dans l’identification de structures cohérentes lagrangiennes en mécanique des fluides. Par exemple, le problème d’identification des différentes caractéristiques de la main droite ou du visage d’une population à l’autre ou le suivi d’une chirurgie à partir des données générées par un numériseur. L’objectif de ce mémoire est de préparer le terrain en passant en revue les différents outils mathématiques disponibles pour appréhender la géométrie comme variable d’optimisation ou d’identification. Pour l’identification des surfaces, on explore l’utilisation de fonctions distance ou distance orientée, et d’ensembles de niveau comme chez S. Osher et R. Fedkiw ; pour la comparaison de surfaces, on présente les constructions des métriques de Courant par A. M. Micheletti en 1972 et le point de vue de R. Azencott et A. Trouvé en 1995 qui consistent à générer des déformations d’une surface de référence via une famille de difféomorphismes. L’accent est mis sur les fondations mathématiques sous-jacentes que l’on a essayé de clarifier lorsque nécessaire, et, le cas échéant, sur l’exploration d’autres avenues.

Dynamic Facility Location with Modular Capacities : Models, Algorithms and Applications in Forestry

Les décisions de localisation sont souvent soumises à des aspects dynamiques comme des changements dans la demande des clients. Pour y répondre, la solution consiste à considérer une flexibilité accrue concernant l’emplacement et la capacité des installations. Même lorsque la demande est prévisible, trouver le planning optimal pour le déploiement et l'ajustement dynamique des capacités reste un défi. Dans cette thèse, nous nous concentrons sur des problèmes de localisation avec périodes multiples, et permettant l'ajustement dynamique des capacités, en particulier ceux avec des structures de coûts complexes. Nous étudions ces problèmes sous différents points de vue de recherche opérationnelle, en présentant et en comparant plusieurs modèles de programmation linéaire en nombres entiers (PLNE), l'évaluation de leur utilisation dans la pratique et en développant des algorithmes de résolution efficaces. Cette thèse est divisée en quatre parties. Tout d’abord, nous présentons le contexte industriel à l’origine de nos travaux: une compagnie forestière qui a besoin de localiser des campements pour accueillir les travailleurs forestiers. Nous présentons un modèle PLNE permettant la construction de nouveaux campements, l’extension, le déplacement et la fermeture temporaire partielle des campements existants. Ce modèle utilise des contraintes de capacité particulières, ainsi qu’une structure de coût à économie d’échelle sur plusieurs niveaux. L'utilité du modèle est évaluée par deux études de cas. La deuxième partie introduit le problème dynamique de localisation avec des capacités modulaires généralisées. Le modèle généralise plusieurs problèmes dynamiques de localisation et fournit de meilleures bornes de la relaxation linéaire que leurs formulations spécialisées. Le modèle peut résoudre des problèmes de localisation où les coûts pour les changements de capacité sont définis pour toutes les paires de niveaux de capacité, comme c'est le cas dans le problème industriel mentionnée ci-dessus. Il est appliqué à trois cas particuliers: l'expansion et la réduction des capacités, la fermeture temporaire des installations, et la combinaison des deux. Nous démontrons des relations de dominance entre notre formulation et les modèles existants pour les cas particuliers. Des expériences de calcul sur un grand nombre d’instances générées aléatoirement jusqu’à 100 installations et 1000 clients, montrent que notre modèle peut obtenir des solutions optimales plus rapidement que les formulations spécialisées existantes. Compte tenu de la complexité des modèles précédents pour les grandes instances, la troisième partie de la thèse propose des heuristiques lagrangiennes. Basées sur les méthodes du sous-gradient et des faisceaux, elles trouvent des solutions de bonne qualité même pour les instances de grande taille comportant jusqu’à 250 installations et 1000 clients. Nous améliorons ensuite la qualité de la solution obtenue en résolvent un modèle PLNE restreint qui tire parti des informations recueillies lors de la résolution du dual lagrangien. Les résultats des calculs montrent que les heuristiques donnent rapidement des solutions de bonne qualité, même pour les instances où les solveurs génériques ne trouvent pas de solutions réalisables. Finalement, nous adaptons les heuristiques précédentes pour résoudre le problème industriel. Deux relaxations différentes sont proposées et comparées. Des extensions des concepts précédents sont présentées afin d'assurer une résolution fiable en un temps raisonnable.

Abdominal aortic aneurysm follow-up after endovascular repair in a canine model with non-invasive vascular elastography

Le traitement chirurgical des anévrismes de l'aorte abdominale est de plus en plus remplacé par la réparation endovasculaire de l’anévrisme (« endovascular aneurysm repair », EVAR) en utilisant des endoprothèses (« stent-grafts », SGs). Cependant, l'efficacité de cette approche moins invasive est compromise par l'incidence de l'écoulement persistant dans l'anévrisme, appelé endofuites menant à une rupture d'anévrisme si elle n'est pas détectée. Par conséquent, une surveillance de longue durée par tomodensitométrie sur une base annuelle est nécessaire ce qui augmente le coût de la procédure EVAR, exposant le patient à un rayonnement ionisants et un agent de contraste néphrotoxique. Le mécanisme de rupture d'anévrisme secondaire à l'endofuite est lié à une pression du sac de l'anévrisme proche de la pression systémique. Il existe une relation entre la contraction ou l'expansion du sac et la pressurisation du sac. La pressurisation résiduelle de l'anévrisme aortique abdominale va induire une pulsation et une circulation sanguine à l'intérieur du sac empêchant ainsi la thrombose du sac et la guérison de l'anévrisme. L'élastographie vasculaire non-invasive (« non-invasive vascular elastography », NIVE) utilisant le « Lagrangian Speckle Model Estimator » (LSME) peut devenir une technique d'imagerie complémentaire pour le suivi des anévrismes après réparation endovasculaire. NIVE a la capacité de fournir des informations importantes sur l'organisation d'un thrombus dans le sac de l'anévrisme et sur la détection des endofuites. La caractérisation de l'organisation d'un thrombus n'a pas été possible dans une étude NIVE précédente. Une limitation de cette étude était l'absence d'examen tomodensitométrique comme étalon-or pour le diagnostic d'endofuites. Nous avons cherché à appliquer et optimiser la technique NIVE pour le suivi des anévrismes de l'aorte abdominale (AAA) après EVAR avec endoprothèse dans un modèle canin dans le but de détecter et caractériser les endofuites et l'organisation du thrombus. Des SGs ont été implantés dans un groupe de 18 chiens avec un anévrisme créé dans l'aorte abdominale. Des endofuites de type I ont été créés dans 4 anévrismes, de type II dans 13 anévrismes tandis qu’un anévrisme n’avait aucune endofuite. L'échographie Doppler (« Doppler ultrasound », DUS) et les examens NIVE ont été réalisés avant puis à 1 semaine, 1 mois, 3 mois et 6 mois après l’EVAR. Une angiographie, une tomodensitométrie et des coupes macroscopiques ont été réalisées au moment du sacrifice. Les valeurs de contrainte ont été calculées en utilisant l`algorithme LSME. Les régions d'endofuite, de thrombus frais (non organisé) et de thrombus solide (organisé) ont été identifiées et segmentées en comparant les résultats de la tomodensitométrie et de l’étude macroscopique. Les valeurs de contrainte dans les zones avec endofuite, thrombus frais et organisé ont été comparées. Les valeurs de contrainte étaient significativement différentes entre les zones d'endofuites, les zones de thrombus frais ou organisé et entre les zones de thrombus frais et organisé. Toutes les endofuites ont été clairement caractérisées par les examens d'élastographie. Aucune corrélation n'a été trouvée entre les valeurs de contrainte et le type d'endofuite, la pression de sac, la taille des endofuites et la taille de l'anévrisme.

Simulations magnétohydrodynamiques en régime idéal

Cette thèse s’intéresse à la modélisation magnétohydrodynamique des écoulements de fluides conducteurs d’électricité multi-échelles en mettant l’emphase sur deux applications particulières de la physique solaire: la modélisation des mécanismes des variations de l’irradiance via la simulation de la dynamo globale et la reconnexion magnétique. Les variations de l’irradiance sur les périodes des jours, des mois et du cycle solaire de 11 ans sont très bien expliquées par le passage des régions actives à la surface du Soleil. Cependant, l’origine ultime des variations se déroulant sur les périodes décadales et multi-décadales demeure un sujet controversé. En particulier, une certaine école de pensée affirme qu’une partie de ces variations à long-terme doit provenir d’une modulation de la structure thermodynamique globale de l’étoile, et que les seuls effets de surface sont incapables d’expliquer la totalité des fluctuations. Nous présentons une simulation globale de la convection solaire produisant un cycle magnétique similaire en plusieurs aspects à celui du Soleil, dans laquelle le flux thermique convectif varie en phase avec l’ ́energie magnétique. La corrélation positive entre le flux convectif et l’énergie magnétique supporte donc l’idée qu’une modulation de la structure thermodynamique puisse contribuer aux variations à long-terme de l’irradiance. Nous analysons cette simulation dans le but d’identifier le mécanisme physique responsable de la corrélation en question et pour prédire de potentiels effets observationnels résultant de la modulation structurelle. La reconnexion magnétique est au coeur du mécanisme de plusieurs phénomènes de la physique solaire dont les éruptions et les éjections de masse, et pourrait expliquer les températures extrêmes caractérisant la couronne. Une correction aux trajectoires du schéma semi-Lagrangien classique est présentée, qui est basée sur la solution à une équation aux dérivées partielles nonlinéaire du second ordre: l’équation de Monge-Ampère. Celle-ci prévient l’intersection des trajectoires et assure la stabilité numérique des simulations de reconnexion magnétique pour un cas de magnéto-fluide relaxant vers un état d’équilibre.

Cobordismes lagrangiens et uniréglage

Ce mémoire traite de la question suivante: est-ce que les cobordismes lagrangiens préservent l'uniréglage? Dans les deux premiers chapitres, on présente en survol la théorie des courbes pseudo-holomorphes nécessaire. On examine d'abord en détail la preuve que les espaces de courbes $ J $-holomorphes simples est une variété de dimension finie. On présente ensuite les résultats nécessaires à la compactification de ces espaces pour arriver à la définition des invariants de Gromov-Witten. Le troisième chapitre traite ensuite de quelques résultats sur la propriété d'uniréglage, ce qu'elle entraine et comment elle peut être démontrée. Le quatrième chapitre est consacré à la définition et la description de l'homologie quantique, en particulier celle des cobordismes lagrangiens, ainsi que sa structure d'anneau et de module qui sont finalement utilisées dans le dernier chapitre pour présenter quelques cas ou la conjecture tient.