Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Dans cette thèse nous considérons deux problèmes d'optimisation combinatoire.Le premier s'appelle problème du double voyageur de commerce avec contraintes de piles. Dans ce problème, un véhicule doit ramasser un certain nombre d'objets dans une région pour les livrer à des clients situés dans une autre région. Lors du ramassage, les objets sont stockés dans les différentes piles du véhicule et la livraison des objets se fait selon une politique de type last-in-first-out. Le ramassage et la livraison consistent chacune en une tournée Hamiltonienne effectuée par le véhicule dans la région correspondante.Nous donnons une formulation linéaire en nombres entiers pour ce problème. Elle est basée sur des variables de précédence et sur des contraintes de chemins infaisables. Nous donnons par la suite des résultats polyédraux sur l'enveloppe convexe des solutions de notre formulation. En particulier, nous montrons des liens forts avec un polytope associé au problème du voyageur de commerce et des liens avec un polytope de type set covering. Cette étude polyédrale nous permet de renforcer la formulation initiale et de développer un algorithme de coupes et branchements efficace. Le deuxième problème que nous considérons consiste à trouver la description des polytopes lexicographiques. Ces derniers sont les enveloppes convexes des points entiers lexicographiquement compris entre deux points entiers fixés. Nous donnons une description complète de ces polytopes en termes d'inégalités linéaires. Nous démontrons que la famille des polytopes lexicographiques est fermée par intersection. / In this thesis we consider two problems arising in combinatorial optimization.The first one is the double traveling salesman problem with multiple stacks. In this problem a vehicle picks up a given set of items in a region and subsequently delivers them to demanding customers in another region. When an item is picked up, it is put in a stack of the vehicle. The items are delivered observing a last-in-first-out policy. The pickup phase and the delivery phase consist in two Hamiltonian circuits, each performed by the vehicle in the corresponding region. We give a new integer linear programming formulation for this problem. Its main features are the presence of precedence variables and new infeasible path constraints. We provide polyhedral results on the convex hull of the solutions to our formulation. In particular, we show strong links with a specific TSPpolytope and a specific set covering polytope. We deduce strengthening inequalities for the initial formulation, subsequently embedded in an efficient branch-and-cut algorithm. The second problem we consider consists in finding the description of the lexicographical polytopes. These are convex hulls of the integer points lexicographically between two given integer points. We give a complete description of these polytopes by means of linear inequalities. We show that the lexicographical polytope family is closed under intersection.

Cette thèse a pour but de contribuer à l’étude des aquifères karstiques en (1) identifiant les facteurs influençants le stockage et l’écoulement de l’eau souterraine et en (2) localisant et estimant de manière quantitative les ressources en eau au sein d’une série carbonatée. Cette étude a été réalisée sur l’aquifère de Dardennes, près de Toulon, en France. L’eau de l’aquifère est utilisée pour l’alimentation en eau potable et alimente le fleuve Las, susceptible de provoquer de fortes crues. Le bassin versant de l’aquifère est estimé à 70 km². Des mesures de porosité et de géochimie isotopique sur les roches carbonatées sont mises en relation dans le but de localiser et d’expliquer les vides créés au sein de la série sédimentaire. Des coupes équilibrées et des analyses structurales ont été réalisées pour évaluer la géométrie de l’aquifère. L’acquisition de données en continu (CTD) et de données hydrochimiques permet d’étudier le dynamisme et le fonctionnement de l'aquifère. Une approche de modélisation pluie-débit avec la plateforme de modélisation KarstMod, basée sur les chroniques de précipitations et de débits sur trois années a été utilisée afin d’estimer la part de l’écoulement disponible pour l’eau potable et celle générant des crues éclair. Une déconvolution du débit des sources a été effectuée à l’échelle annuelle et à l’échelle des crues. Les résultats du modèle ont été comparés avec la gestion actuelle de l’aquifère, montrant une exploitation actuelle équilibrée, et ouvrant des perspectives pour la mise en place d’une gestion active, combinant une exploitation plus importante de l’eau, un écrêtage des crues et un respect de l’écologie du cours d’eau en aval. / The aim of this PhD is to contribute to the karst aquifers understanding by (1) identifying the factors influencing the groundwater storage and flow and by (2) locating and quantitatively estimating water resources within the carbonate sedimentary series. This study was conducted on the Dardennes aquifer near Toulon, France. The aquifer water is used for the supply of drinking water and feeds the Las River, which can cause important floods. The recharge area of the aquifer is estimated at 70 km². Measurements of porosity and isotopic geochemistry on carbonate rocks are related in order to locate and explain the voids created within the sedimentary series. Balanced cross-sections and structural analyses were performed to evaluate the geometry of the aquifer at depth. Continuous data acquisition (specific conductivity, temperature and water depth-pressure) and hydrochemical data (major ions, stables isotopes of water and carbon-13) allow to study the aquifer dynamism and functioning. A daily rainfall-discharge modeling approach was used with the KarstMod platform to estimate the flow part available for drinking water and the part that generates karst flash-floods. A hydrograph separation of springs discharge was carried out at annual and floods scales. Model results have been compared with the current groundwater management, showing a balanced current exploitation. In new perspective, it would be interesting to establish active management, combining a greater groundwater exploitation, floods mitigation and stream ecology respect.

Les travaux présentés dans ce mémoire portent sur l'étude de matériaux piézoélectriques de synthèse de la famille des langasite et sur la réalisation de micro-résonateurs basse fréquence dans ces matériaux. La première partie de l'étude se concentre sur la recherche des orientations des coupes compensées en température pour les coupes X de la langasite (LGS) et de la langatate (LGT), pour les modes d'extension selon Y et de flexion autour de X. Un modèle analytique simple et des simulations par éléments finis permettent de déterminer les valeurs théoriques de ces orientations. Des dispositifs de types barreau et diapason sont ensuite réalisés afin d'effectuer des mesures électriques pou confirmer l'existence de ces coupes compensées. La seconde partie de l'étude concerne la fabrication de micro-résonateurs en langasite. Plusieurs méthodes d'usinage (mécanique, DRIE,...) sont envisagées avant que notre choix ne se porte sur l'usinage chimique (solution HCl). Le procédé de fabrication est détaillé puis des mesures de vibration sont menées pour les dispositifs obtenus.

Le contourage des ventricules cardiaques sur IRM est nécessaire à la détermination de la fonction contractile du cœur. Cette tâche est difficile, en particulier pour le ventricule droit (VD), due au flou aux frontières des cavités, aux irrégularités des intensités et à sa forme complexe et variable. Peu de travaux ont cependant été réalisés afin de résoudre cette problématique de segmentation. Dans ce but, nous avons proposé et développé deux méthodes de segmentation basées sur la méthode des coupes de graphe (GC), à laquelle nous avons incorporé des a priori de forme. La première méthode, semi-automatique, repose sur une carte d'a priori statistique créée à base d'Analyses en Composantes Principales et intégrée à la méthode des GC binaires. La seconde, automatique, permet la segmentation d'un ensemble d'objets par GC multi-labels à partir d'un modèle de forme probabiliste basé sur le recalage et la fusion d'atlas. Ces méthodes ont été évaluées sur une base importante d'IRM cardiaques, composée de 48 patients. Une comparaison aux méthodes de l'état de l'art pour cette application à travers le challenge de segmentation du VD MICCAI'12, que nous avons organisé, montre l'efficacité de nos méthodes.

Nous étudions des problèmes NP-difficiles portant sur les graphes contenant des blocages.Nous traitons les problèmes de coupes du point de vue de la complexité paramétrée. La taille p de la coupe est le paramètre. Étant donné un ensemble de sources {s1,...,sk} et une cible t, nous proposons un algorithme qui construit une coupe de taille au plus p séparant au moins r sources de t. Nous nommons ce problème NP-complet Partial One-Target Cut. Notre algorithme est FPT. Nous prouvons également que la variante de Partial One-Target Cut, où la coupe est composée de noeuds, est W[1]-difficile. Notre seconde contribution est la construction d'un algorithme qui compte les coupes minimums entre deux ensembles S et T en temps $2^{O(plog p)}n^{O(1)}$.Nous présentons ensuite plusieurs résultats sur le ratio de compétitivité des stratégies déterministes et randomisées pour le problème du voyageur canadien.Nous prouvons que les stratégies randomisées n'utilisant pas de mémoire ne peuvent pas améliorer le ratio 2k+1. Nous apportons également des éléments concernant les bornes inférieures de compétitivité de l'ensemble des stratégies randomisées. Puis, nous étudions la compétitivité en distance d'un groupe de voyageurs avec et sans communication. Enfin, nous nous penchons sur la compétitivité des stratégies déterministes pour certaines familles de graphes. Deux stratégies, avec un ratio inférieur à 2k+1 sont proposées: une pour les graphes cordaux avec poids uniformes et l'autre pour les graphes où la taille de la plus grande coupe minimale séparant s et t est au plus k. / We study NP-hard problems on graphs with blockages seen as models of networks which are exposed to risk of failures.We treat cut problems via the parameterized complexity framework. The cutset size p is taken as a parameter. Given a set of sources {s1,...,sk} and a target $t, we propose an algorithm which builds a small edge cut of size p separating at least r sources from t. This NP-complete problem is called Partial One-Target Cut. It belongs to the family of multiterminal cut problems. Our algorithm is fixed-parameter tractable (FPT) as its execution takes $2^{O(p^2)}n^{O(1)}$. We prove that the vertex version of this problem, which imposes cuts to contain vertices instead of edges, is W[1]-hard. Then, we design an FPT algorithm which counts the minimum vertex (S,T)-cuts of an undirected graph in time $2^{O(plog p)}n^{O(1)}$.We provide numerous results on the competitive ratio of both deterministic and randomized strategies for the Canadian Traveller Problem. The optimal ratio obtained for the deterministic strategies on general graphs is 2k+1, where k is a given upper bound on the number of blockages. We show that randomized strategies which do not use memory cannot improve the bound 2k+1. In addition, we discuss the tightness of lower bounds on the competitiveness of randomized strategies. The distance competitive ratio for a group of travellers possibly equipped with telecommunication devices is studied. Eventually, a strategy dedicated to equal-weight chordal graphs is proposed while another one is built for graphs with small maximum (s,t)-cuts. Both strategies outperform the ratio 2k+1.

Cette thèse traite de l’enregistrement de la déformation, à différentes échelles de temps et d’espace dans la chaîne plissée de Malargüe et le bloc de San Rafael, situés dans la partie septentrionale du bassin de Neuquén en Argentine. La première partie du travail comprend une analyse de la déformation finie (chaîne de Malargüe) et de la déformation active (bloc de San Rafael) à l’échelle macroscopique. De manière générale, les coupes structurales régionales proposées mettent clairement en évidence le rôle l’héritage structural lié aux structures générées lors de l’ouverture du bassin au Jurassique. Nous montrons également que les mécanismes de soulèvement actuels du bloc de San Rafael à l’est reprennent les modalités de la déformation d’âge Miocène dans la chaîne. Contrairement au mode de structuration des prismes critiques classiques caractérisés par la localisation de la déformation le long d’un niveau de décollement, la structuration de la chaîne est ici issue d’une déformation distribuée plus largement dans la lithosphère. A l’échelle de l’endommagement mesoscopique, la fracturation régionale nous a permis d’enregistrer les différents champs de contraintes régionaux liés aux phases de raccourcissement depuis le domaine pré-plissement jusqu’à la phase syn-plissement. Ces différentes phases sont en accord avec la cinématique de la convergence de la plaque Nazca depuis le Crétacé supérieur. A l’échelle microscopique, l’analyse des propriétés de susceptibilité magnétique des roches met en évidence, d’une part, une compartimentalisation de la déformation à l’échelle de la matrice liée à l’héritage structural extensif. D’autre part, la distribution spatiale de cet endommagement ne démontre pas l’existence de gradient clair des fabriques magnétiques depuis l’avant-pays vers les zones internes ce qui confirme le caractère atypique du système Andin à la latitude de 35°S. Ce dernier étant principalement contrôlé par une déformation distribuée, liée à l’héritage structural et singulièrement différente de celle attendu dans le cadre de la théorie du prisme critique. / This PhD project deals with multiscale record of the tectonic signal in the Malargüe fold-and-thrust-belt (MFTB) located in the northern part of the Neuquén basin (Argentina). The first results presented rely on the study of the macroscopic finite strain in the fold-belt and the characterization of the active deformation of the San Rafael Block uplift. The cross-sections we produce show that structural inheritance related to the Jurassic extension is the main parameter controlling the belt structure. In addition we proposed that the building mechanisms that controlled the MFTB evolution by Miocene times are the same than those triggering the present day San Rafael block uplift. The second part of this work is dedicated to mesoscopic strain pattern analysis recorded by fracture networks. Throughout the MFTB, we are able to describe the occurrence of four main fractures sets emplaced in several stress regime that are linked (1) to the inheritance and (2) to the well-known compression phases from pre-folding to syn-folding settings. Finally the third part of this work describes the microscopic damage recorded by the anisotropy of magnetic susceptibility method. We mainly evidence that there is no clear gradient of magnetic fabrics from foreland to hinterland and that deformation is compartmentalized by structural inheritance. This atypical pattern of magnetic fabrics succession reveals that the matrix damage is governed by the same strain distribution as those observed at macroscopic scale thus providing a supplementary argument to consider the Andean system at these latitudes as singularly different from a classical Coulomb wedge.

La chaîne alpine est un domaine à croûte épaissie pour lequel le déplacement imposé aux limites est absorbé alternativement par deux mécanismes de raccourcissement. Le premier correspond au glissement d'écailles crustales sur des discontinuités (déformation localisée) exprimé d'une part par des translations transversales à la chaîne (chevauchements), d'autre part, et de manière synchrone, par des rotations antihoraires (décrochevauchements longitudinaux). Le second correspond à une déformation interne généralisée des écailles et de l'avant-pays lorsque les glissements se bloquent. Le mécanisme de glissement, démontré par la structure discontinue de la croûte (superposition d'écailles contenant de la croûte inférieure et éventuellement du manteau supérieur), absorbe la plus grande partie du raccourcissement. L'évolution cinématique se décompose en trois grandes périodes : - Jusqu'à 37-38 Ma (Eocène) la croûte austro-alpine chevauche la marge européenne. - De 37-38 Ma à 21-22 Ma (Oligocène - Aquitanien) un chevauchement de la croûte pennique (avec le corps d'lvrea) sur la croûte delphino-helvétlque et un décrochevauchementdextre (rotation antihoraire de 18°) de l'austro-alpin par rapport au pennique, absorbent 150 à 200 km de raccourcissement. - De 21-22 Ma à l'Actuel (Miocène - Quaternaire), le chevauchement crustal des massifs cristallins externes et un décrochevauchement dextre (rotation antihoraire de 26-27°) du Pennique par rapport au Delphino-helvétique absorbent autour de 150 km de raccourcissement. Il se vérifie que ce modèle s'applique également aux déformations actuelles et permet d'intégrer aussi bIen les données sur la sismicité (mécanismes au foyer) que sur les mouvements verticaux (surrection actuelle). Le mécanisme de déformation interne est associe aux périodes qui font la transition (c'est à dire autour de 37-38 Ma et autour de 21-22 Ma) entre les périodes où les glissements dominent. Ces périodes dont la durée exacte reste à préciser sont à rapprocher des "phases tectoniques" classiques dont l'importance, en termes de raccourcissement crustal, apparaît ainsi bien moindre que dans l'approche traditionnelle.

Cette thèse est consacrée à l'étude des signaux mesurés par Electroencéphalographie (EEG) et Magnétoencéphalographie (MEG) afin d'améliorer notre compréhension du cerveau humain. La MEG et l'EEG sont des modalités d'imagerie cérébrale non invasives. Elles permettent de mesurer, hors de la tête, respectivement le potentiel électrique et le champ magnétique induits par l'activité neuronale. Le principal objectif lié à l'exploitation de ces données est la localisation dans l'espace et dans le temps des sources de courant ayant généré les mesures. Pour ce faire, il est nécessaire de résoudre un certain nombre de problèmes mathématiques et informatiques difficiles. La première partie de cette thèse part de la présentation des fondements biologiques à l'origine des données M/EEG, jusqu'à la résolution du problème direct. Le problème direct permet de prédire les mesures générées pour une configuration de sources de courant donnée. La résolution de ce problème à l'aide des équations de Maxwell dans l'approximation quasi-statique passe par la modélisation des générateurs de courants, ainsi que de la géométrie du milieu conducteur, dans notre cas la tête. Cette modélisation aboutit à un problème direct linéaire qui n'admet pas de solution analytique lorsque l'on considère des modèles de tête réalistes. Notre première contribution porte sur l'implémentation d'une résolution numérique à base d'éléments finis surfaciques dont nous montrons l'excellente précision comparativement aux autres implémentations disponibles. Une fois le problème direct calculé, l'étape suivante consiste à estimer les positions et les amplitudes des sources ayant généré les mesures. Il s'agit de résoudre le problème inverse. Pour ce faire, trois méthodes existent: les méthodes paramétriques, les méthodes dites de "scanning", et les méthodes distribuées. Cette dernière approche fournit un cadre rigoureux à la résolution de problème inverse tout en évitant de faire de trop importantes approximations dans la modélisation. Toutefois, elle impose de résoudre un problème fortement sous-contraint qui nécessite de fait d'imposer des a priori sur les solutions. Ainsi la deuxième partie de cette thèse est consacrée aux différents types d'a priori pouvant être utilisés dans le problème inverse. Leur présentation part des méthodes de résolution mathématiques jusqu'aux détails d'implémentation et à leur utilisation en pratique sur des tailles de problèmes réalistes. Un intérêt particulier est porté aux a priori induisant de la parcimonie et conduisant à l'optimisation de problèmes convexes non différentiables pour lesquels sont présentées des méthodes d'optimisation efficaces à base d'itérations proximales. La troisième partie porte sur l'utilisation des méthodes exposées précédemment afin d'estimer des cartes rétinotopiques dans le système visuel à l'aide de données MEG. La présentation porte à la fois sur les aspects expérimentaux liés au protocole d'acquisition jusqu'à la mise en oeuvre du problème inverse en exploitant des propriétés sur le spectre du signal mesuré. La contribution suivante ambitionne d'aller plus loin que la simple localisation d'activités par le problème inverse afin de donner accès à la dynamique de l'activité corticale. Partant des estimations de sources sur le maillage cortical, la méthode proposée utilise des méthodes d'optimisation combinatoires à base de coupes de graphes afin d'effectuer de façon robuste le suivi de l'activité au cours du temps. La dernière contribution de cette thèse porte sur l'estimation de paramètres sur des données M/EEG brutes non moyennées. Compte tenu du faible rapport signal à bruit, l'analyse de données M/EEG dites "simple essai" est un problème particulièrement difficile dont l'intérêt est fondamental afin d'aller plus loin que l'analyse de données moyennées en explorant la variabilité inter-essais. La méthode proposée utilise des outils récents à base de graphes. Elle garantit des optimisations globales et s'affranchit de problèmes classiques tels que l'initialisation des paramètres ou l'utilisation du signal moyenné dans l'estimation. L'ensemble des méthodes développées durant cette thèse ont été utilisées sur des données M/EEG réels afin de garantir leur pertinence dans le contexte expérimental parfois complexe des signaux réelles M/EEG. Les implémentations et les données nécessaires à la reproductibilité des résultats sont disponibles. Le projet de rétinotopie par l'exploitation de données de MEG a été mené en collaboration avec l'équipe du LENA au sein de l'hôpital de La Pitié-Salpêtrière (Paris).

Cette thèse -spécialisée en Recherche Opérationnelle- traite de l'intégration, dans le processus décisionnel industriel, de deux facteurs-clés: la planification des ressources humaines et l'ordonnancement de la production. Un premier cas de ce genre de problématiques est tout d'abord étudié. Deux bornes inférieures obtenues par relaxation lagrangienne et deux méthodes de résolution exacte par décomposition et génération de coupes sont présentées. Si la première approche relève d'une technique connue de la littérature (décomposition de Benders), la seconde se veut plus spécifique. Une technique de génération de coupes énergétiques valides, applicable en préprocess de toute méthode de résolution, est également proposée. La seconde partie traite d'un autre cas particulier, déjà évoqué dans la littérature, de la problématique générale. Ces travaux prolongent ceux effectués lors de la première étude dans le sens où le problème traité est intrinsèquement plus complexe et le but avoué est d'expérimenter les techniques de décomposition et génération de coupes, a priori efficaces, sur une autre problématique. Une technique de génération d'inégalités valides, applicable elle aussi en préprocess de toute méthode de résolution, est tout d'abord mise en place. Deux méthodes de résolution exacte sont ensuite développées. La première est analogue à la technique spécifique de décomposition décrite auparavant. La seconde, plus novatrice, exploite la décomposition intuitive de la problématique et la génération de coupes dédiées dans un cadre où les solutions à valider sont construites via une approche arborescente de type Procédure de Séparation et Evaluation Séquentielle.