Cette thèse est dédiée à la résolution de deux problèmes d'optimisation combinatoire NP-complets surgissant en bioinformatique, à savoir le problème classique d'alignement de séquences, ainsi qu'un problème nouvellement formalisé, le problème de coloration par contraintes d'intervalles ou Interval Constraint Coloring Problem (ICP). Nous montrons dans cette thèse qu'il est possible de résoudre des instances réelles et de grande taille de ces problèmes apparaissant en biologie, et ceci par des méthodes de programmation mathématiques avancées. Nous démontrons également l'existence de méthodes plus efficaces, permettant d'obtenir des solutions approchées pour ces mêmes problèmes. Dans la première partie de la thèse, nous présentons un algorithme pour la solution du problème classique de l'alignement de séquences, basé sur la relaxation lagrangienne. Le problème de l'alignement de séquences est une abstraction mathématique courante du problème de comparaison de séquences biologiques, comme l'ADN, l'ARN ou les séquences de protéines. Si le poids d'un alignement séquentiel multiple est calculé comme la somme des poids des paires de séquence projetées de l'alignement considéré, alors le problème de déterminer un alignement de poids maximal est NP-complet, tant que le nombre de séquences n'est pas fixé. La plupart des logiciels disponibles pour la résolution du problème d'alignement de séquences se focalisent donc sur des approches heuristiques. Aucune méthode n'est actuellement capable de résoudre efficacement des instances de taille moyenne, ou des instances comportant des séquences d'un faible taux de similitude, de ce problème de manière exacte. Nous présentons un nouvel algorithme pour la résolution du problème de l'alignement de séquences, basé sur la technique de séparation et évaluation (branch-and-bound ou B&B). Nous approchons la solution optimale en nombres entiers dans les nœuds de l'arbre B&B par une relaxation lagrangienne de la formulation en tant que PLNE du problème d'alignement de séquences multiples. Un nombre exponentiel d'inégalités supplémentaires doit alors être vérifié afin de garantir que l'alignement de séquences multiples peut être reconstruit sans conflits à partir des alignements individuels. En renforcant ces inégalités avant de les dualiser, le sous-problème lagrangien devient le problème d'alignement par paires étendu: il s'agit alors de trouver le plus long chemin dans un graphe acyclique, auquel sont ajoutés des pénalités lors du passage à travers certaines zones ``obstacles''. Nous introduisons un algorithme efficace permettant de résoudre ce problème de manière répétitive, afin de trouver une bonne approximation des multiplicateurs de Lagrange via optimization du sous-gradient. La reformulation des inégalités dualisées par rapport à des variables supplémentaires améliore de manière significative le taux de convergence de l'algorithme. Nous adressons le problème du nombre exponentiel d'inégalités par une approche itérative. L'ensemble des contraintes est vide au début. Après chaque itération, nous rajoutons à cet ensemble ces inégalités qui sont le plus violées par la combinaison convexe d'un petit nombre des solutions lagrangiennes précédentes (y compris la solution courante). Conformément au schéma relax-and-cut, nous dualisons exclusivement les inégalités présents dans l'ensemble des contraintes décrit précédemment. L'ICP est un problème qui se pose lors de l'analyse et l'interprétation de données expérimentales en biochimie. L'analyse du taux d'échange hydrogène/deutérium par spectrométrie de masse est une des méthodes utilisées pour obtenir des informations sur la structure tertiaire des protéines. Les résultats de ces expériences se présentent sous forme de taux d'échange des résidus dans les segments chevauchés de la protéine. Ces segments doivent être recollés afin d'obtenir une vision globale de la structure de la protéine. L'ICP est l'abstraction mathématique de ce process de recombinaison. L'objectif de l'ICP est d'attribuer une couleur (taux d'échange) à un ensemble d'entiers (résidus de protéines) de telle manière à ce qu'un ensemble de contraintes est vérifié. Chaque contrainte représente un intervalle fermé (segment d'une protéine) ainsi qu'un ensemble d'exigences supplémentaires concernant le nombre d'éléments qui doivent appartenir à chacune des catégories de couleur (taux d'échanges observés lors des expériences). Nous montrons que le problème peut être résolu par des méthodes de programmation linéraire en nombres entiers (PLNE), et nous utilisons un algorithme d'énumération implicite qui s'avère efficace pour la plupart des problèmes qu'on rencontre dans la pratique. Puisque notre motivation est de fournir aux biochimistes une liste exhaustive des solutions potentielles, une version améliorée de notre approche PLNE consiste à regrouper des solutions similaires dans des classes d'équivalence, ceci afin d'établir une version améliorée et plus performante de la procédure d'énumération. Nous démontrons ensuite la solvabilité du cas particulier à deux couleurs par la contrainte de solution en nombres entiers du polytope P, défini à travers la relaxation linéaire, tout en proposant un algorithme de résolution de complexité polynomielle pour ce cas précis. Cet algorithme sert ensuite de base pour l'établissement de solutions approchés d'instances de dimension quelconque mais fixe (pour le moment sans garantie sur la qualité de la solution obtenue). Nous obtenons ainsi une amélioration d'un ordre de grandeur en termes de performance par rapport à la solution exacte, basée sur l'approche PLNE. Nous démontrons que ce problème est NP-complet pour un nombre arbitraire de couleurs. Nous établissons ensuite un algorithme qui, étant donné P?Ø, est capable de déterminer une coloration satisfaisante toutes les contraintes données avec un écart maximal de ±1 des valeurs cible. Vue la complexité en NP du problème, il ne semble pas possible d'obtenir des solutions d'une qualité sensiblement supérieure. Notre approche est essentiellement basée sur la théorie des polyèdres et des techniques d'arrondissage randomisés. Les données obtenues lors des expériences biologiques réelles sont souvent bruitées, ce qui entraine le plus souvent l'insolvabilité du problème, voire même P=Ø. Afin d'adresser ce problème, l'objectif de la PLNE est de minimiser la somme des déviations absolues des contraintes de coloration sur l'intégralité des intervalles. L'approche particulière à deux couleurs optimise en effet cette même fonction. En outre, nous utilisons cette approche combinatoire pour déterminer, d'une façon lagrangienne, une borne sur l'erreur minimale, qui sera ensuite utilisée dans un algorithme de type branch-and-bound pour déterminer toutes les colorations optimales. Nous proposons une variante du problème précédent, dans laquelle nous essayons de maximiser le nombre contraintes qui peuvent être satisfaits en même temps. Nous démontrons que ce problème est APX-dur et qu'il ne permet donc pas de schéma d'approximation polynomial sauf si P=NP. C'est pourquoi nous relaxons légèrement le critère de satisfiabilité (par un facteur (1+e) et décrivons par la suite un schéma d'approximation d'une complexité quasi-polynomiale, permettant de ``satisfaire'' le plus grand nombre de contraintes possible. / This thesis is devoted to two NP-complete combinatorial optimization problems arising in computational biology, the well-studied multiple sequence alignment problem and the new formulated interval constraint coloring problem. It shows that advanced mathematical programming techniques are capable of solving large scale real-world instances from biology to optimality. Furthermore, it reveals alternative methods that provide approximate solutions. In the first part of the thesis, we present a Lagrangian relaxation approach for the multiple sequence alignment (MSA) problem. The multiple alignment is one common mathematical abstraction of the comparison of multiple biological sequences, like DNA, RNA, or protein sequences. If the weight of a multiple alignment is measured by the sum of the projected pairwise weights of all pairs of sequences in the alignment, then finding a multiple alignment of maximum weight is NP-complete if the number of sequences is not fixed. The majority of the available tools for aligning multiple sequences implement heuristic algorithms; no current exact method is able to solve moderately large instances or instances involving sequences exhibiting a lower degree of similarity. We present a branch-and-bound (B&B) algorithm for the MSA problem. We approximate the optimal integer solution in the nodes of the B&B tree by a Lagrangian relaxation of an ILP formulation for MSA relative to an exponential large class of inequalities, that ensure that all pairwise alignments can be incorporated to a multiple alignment. By lifting these constraints prior to dualization the Lagrangian subproblem becomes an extended pairwise alignment (EPA) problem: Compute the longest path in an acyclic graph, that is penalized a charge for entering ``obstacles''. We describe an efficient algorithm that solves the EPA problem repetitively to determine near-optimal Lagrangian multipliers via subgradient optimization. The reformulation of the dualized constraints with respect to additionally introduced variables improves the convergence rate dramatically. We account for the exponential number of dualized constraints by starting with an empty constraint pool in the first iteration to which we add cuts in each iteration, that are most violated by the convex combination of a small number of preceding Lagrangian solutions (including the current solution). In this relax-and-cut scheme, only inequalities from the constraint pool are dualized. The interval constraint coloring problem appears in the interpretation of experimental data in biochemistry. Monitoring hydrogen-deuterium exchange rates via mass spectroscopy is a method used to obtain information about protein tertiary structure. The output of these experiments provides aggregate data about the exchange rate of residues in overlapping fragments of the protein backbone. These fragments must be re-assembled in order to obtain a global picture of the protein structure. The interval constraint coloring problem is the mathematical abstraction of this re-assembly process. The objective of the interval constraint coloring problem is to assign a color (exchange rate) to a set of integers (protein residues) such that a set of constraints is satisfied. Each constraint is made up of a closed interval (protein fragment) and requirements on the number of elements in the interval that belong to each color class (exchange rates observed in the experiments). We introduce a polyhedral description of the interval constraint coloring problem, which serves as a basis to attack the problem by integer linear programming (ILP) methods and tools, which perform well in practice. Since the goal is to provide biochemists with all possible candidate solutions, we combine related solutions to equivalence classes in an improved ILP formulation in order to reduce the running time of our enumeration algorithm. Moreover, we establish the polynomial-time solvability of the two-color case by the integrality of the linear programming relaxation polytope P, and also present a combinatorial polynomial-time algorithm for this case. We apply this algorithm as a subroutine to approximate solutions to instances with arbitrary but fixed number of colors and achieve an order of magnitude improvement in running time over the (exact) ILP approach. We show that the problem is NP-complete for arbitrary number of colors, and we provide algorithms that, given an instance with P?Ø, find a coloring that satisfies all the coloring requirements within ±1 of the prescribed value. In light of our NP-completeness result, this is essentially the best one can hope for. Our approach is based on polyhedral theory and randomized rounding techniques. In practice, data emanating from the experiments are noisy, which normally causes the instance to be infeasible, and, in some cases, even forces P to be empty. To deal with this problem, the objective of the ILP is to minimize the total sum of absolute deviations from the coloring requirements over all intervals. The combinatorial approach for the two-color case optimizes the same objective function. Furthermore, we use this combinatorial method to compute, in a Lagrangian way, a bound on the minimum total error, which is exploited in a branch-and-bound manner to determine all optimal colorings. Alternatively, we study a variant of the problem in which we want to maximize the number of requirements that are satisfied. We prove that this variant is APX-hard even in the two-color case and thus does not admit a polynomial time approximation scheme (PTAS) unless P=NP. Therefore, we slightly (by a factor of (1+e)) relax the condition on when a requirement is satisfied and propose a quasi-polynomial time approximation scheme (QPTAS) which finds a coloring that ``satisfies'' the requirements of as many intervals as possible.

La localisation de sites est une des décisions stratégiques les plus importantes pour les entreprises dans le contexte de la mondialisation d'aujourd'hui. Les travaux existant dans la littérature traitant ce type de problèmes se concentrent principalement sur la détermination de l'emplacement des sites et des flux de produits provenant les sites localisés aux clients dans le but de minimiser le coût total de construction, de production et logistiques. Cependant, il est très important de bien choisir simultanément la capacité et la localisation des sites parce que la taille des sites a une grande influence sur ces coûts sur le long terme. La détermination de la location et de capacité des sites reste encore un problème ouvert.Dans cette thèse, nous étudions trois nouvelles variantes de problèmes de location de sites à deux échelons avec la sélection de taille (TECFLP). Les deux premières parties concentrent sur les TECFLPs avec sélection séparée de taille d’usines ou de dépôts. La troisième partie étudie le TECFLP avec sélection simultanée des tailles d’usines et de dépôts. Pour ces problèmes, trois modèles de programmation linéaire mixte sont proposés. Ensuite les approches basées sur la relaxation lagrangienne selon les caractéristiques de chaque problème sont développés. Pour améliorer les meilleures solutions proposées par les approches de relaxation lagrangienne, une méthode de recherche tabou, une méthode hybride de recherche tabou et à voisinage variable, une méthode hybride du recuit simulé et de la recherche tabou sont respectivement adaptées pour ces trois problèmes. Les algorithmes développés sont testés et évalués à travers 810 instances générées aléatoirement. Les résultats numériques montrent que nos méthodes sont capables de fournir des solutions de qualité avec un temps de calcul raisonnable. / Facility location is one of the most important strategic decisions for firms in globalization. Previous works on facility location in the literature mainly focus on determining the locations of facilities and the flows of products from facilities to customers with the goal of minimizing the sum of facility opening costs, production and logistic costs. However, it’s very important to determine at the same time the appropriate sizes for these facilities because they greatly affects these costs on the long term. Determining facility location and size is always an open problem.In this thesis, we study three new two-echelon capacitated facility location problems (TECFLP) with facility size selection. The two first parts of the wok focus on two-echelon facility location problems with plant and depot size selection, respectively. The third part concentrates on TECFLP considering simultaneously plant and depot size selection. For these problems, three corresponding mixed integer programming models are formulated and then Lagrangean relaxation approaches according to the problems’ characteristics are developed. To further improve the best solutions obtained by the Lagrangean Relaxation approaches, a tabu search, a hybrid variable neighborhood tabu search and a hybrid simulated annealing tabu search are adapted for the three problems respectively. The developed algorithms are tested and evaluated through 810 randomly generated instances. Computational results show ours algorithms can provide high quality solutions within a reasonable computation time.

Les sous-variées isotropes maximales en géométries symplectique sont appelées lagrangiennes ; parmi celles-ci on distingue les lagrangiennes monotones. Historiquement leur définition est motivée en partie par la construction de l'homologie de Floer lagrangiennes ; elles présentent ainsi une classe plus rigide, moins étendue, de lagrangiennes. Ce manuscrit établit une contrainte sur le groupe fondamental de certaines lagrangiennes monotones, qui s'applique en particulier lorsque la variété symplectique ambiante est l'espace projectif complexe. Une des conséquences du théorème principal est d'exclure toute une classe d'exemples classiques de lagrangiennes, due à L. Polterovich, du cas monotone. Elle conduit également à une discussion sur les topologies possibles en dimension 3. / This thesis establishes a topological constraint on the fundamental group of some monotone Lagrangien. One useful consequence is to rule out a class of examples of Lagrangians due to L. Polterovich as monotone ones. It also leads to a discussion on the possible topologies en dimension 3.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Les effets de taille finie et de densité de particules sur leur dynamique Lagrangienne dans un écoulement turbulent ont été étudiés, dans ce travail de recherche. L'écoulement de choix est la turbulence de grille en soufflerie. Des bulles de savon, gonflée au gaz ont été utilisés comme particules, la densité est la taille de les quelles peuvent ajuster à souhait dans une gamme réalisable. Celles-ci sont injectées dans l'écoulement, et sont suivies de manière Lagrangienne, en se basant sur l'état de l'art en Vélocimétrie Doppler Acoustique. Pour un même configuration d'écoulement, les tailles et les densités de particules ont été varié à l'intérieur d'une gamme faisable. Pour chaque série de particules, la vitesse et l'accélération statistiques Lagrangienne ont été déterminées, après avoir enregistré quelques mille signaux de vitesses. Les résultats montrent que les PDFs de vitesse Lagrangienne sont Gaussiennes et : indépendantes de la taille et de la densité des particules ; et sont similaire aux PDFs des vitesses Eulérienne de l'écoulement porteur. Aucuns effets de taille et de densité n'ont été trouvés sur la PDF d'accélération normalisée. Par contre, ces effets sont dominant dans la variance d'accélération, qui pour les particules iso densité décroit dans une façon monotone avec la taille de particule. Par contre, pour les bulles lourdes ces effets de taille finie peut traduire ni à partir des modèle limite de point particule ni du cas de particule iso densité. La dynamique de toutes les séries étudiées a été trouvé intermittente. Le temps de forçage turbulente été calculé à partir de l'auto corrélation d'accélération qui ont été trouvé de n'est pas varié beaucoup et qui reste dans l'ordre de temps de kolmogorov par rapport aux temps de réponses de particules calculé normalement.

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. / In this thesis we study the properties of Lagrangian submanifolds of a symplectic manifold by using the relation of Lagrangian cobordism. More precisely, we are interested in determining when an elementary Lagrangian cobordism is trivial. Using techniques coming from Floer homology and the s-cobordism theorem, we show that under some topological assumptions, an exact Lagrangian cobordism is a Lagrangian pseudo-isotopy. This is a weaker version of a conjecture proposed by Biran and Cornea, which states that any exact Lagrangian cobordism is Hamiltonian isotopic to a Lagrangian suspension.

Ce travail, qui a été réalisé dans le cadre d'un projet européen, avait pour objectif de faire la simulation numérique de l'injection d'un alliage d'aluminium (A356) à l'état semi-solide. Pour atteindre cet objectif, nous avons travaillé sur deux principaux axes qui sont l'expérience et la simulation numérique. Sur le plan expérimental, l'objectif était de trouver une loi de comportement et ses paramètres pour caractériser le comportement de notre alliage à l'état semi-solide. Cette étude nous a conduit d'une part à passer en revue les différentes classes de loi disponibles dans la bibliographie et à utiliser une loi de comportement viscoplastique, et d'autre part à réaliser un nouveau test rhéologique, le test de l'écoulement de Stephan. Les résultats expérimentaux ont été satisfaisants et l'identification des paramètres a pu être faite, en utilisant une stratégie de type essai-erreur. Ceci nous a permis de trouver pour notre cas des paramètres en concordance avec ceux trouvés dans la bibliographie et d'obtenir un accord raisonnable entre simulation numérique et mesures sur l'ensemble des essais effectués. Sur le plan purement numérique, nous avons dans un premier temps adapté le code de calcul R3 à la mise en forme à l'état semi-solide. Ce travail nous a conduit à y introduire un module de contact matière/matière et à développer le module de contact matière/outil existant. Nous avons alors été confrontés au problème de préconditionnement de la matrice hessienne, dont le conditionnement est fortement dégradé par l'ajout de la condition de non-interpénétration du contact matière/matière. Ce problème a été résolu grâce à l'utilisation du préconditionneur par factorisation incomplète de Crout. Nous avons ensuite travaillé sur la formulation eulérienne lagrangienne arbitraire et sur la procédure de remaillage automatique. Malheureusement, ces travaux ne nous ont pas permis de pouvoir simuler jusqu'au bout le remplissage de pièces industrielles. Nous sommes alors passés dans un deuxième temps à une formulation eulérienne en utilisant le code de calcul Rem3D, initialement développé pour l'injection de thermoplastiques. Nous y avons introduit les termes d'inertie, ainsi que notre loi de comportement. Ce dernier code de calcul nous a alors permis de simuler l'injection de notre alliage d'aluminium à l'état semi-solide. Les résultats obtenus montrent une bonne concordance avec le procédé industriel et le logiciel peut constituer un outil précieux d'aide à la conception.

Avec la généralisation du recours à l’infographie dans l’industrie des loisirs, la demande concernant la production de scènes de simulation de fluides d’un réalisme croissant a fortement augmenté durant les deux dernières décennies. Nous proposons de nombreux éléments pertinents pour simuler le fluide, essentiellement tournés vers l’approche lagrangienne (les méthodes particulaires). Cette présentation a donc pour objet l’étude et la mise au point de techniques permettant de reproduire le comportement des fluides s’appuyant sur l’aspect particulaire du fluide. Les algorithmes de ces dernières années permettent un gain de performance significatif, nous permettant d’obtenir des simulations de fluides incompressibles en temps réel. L’usage des noyaux constants par morceaux, nouvel outil de calcul numérique, au sein de simulations de fluides dites lagrangiennes sera également abordé. Avec l’augmentation continue de la puissance de calcul et de nouvelles avancées telles que la programmation dite GPGPU, nous verrons également comment obtenir une recherche de voisinage efficace permettant d’augmenter grandement les performances de calcul.

.