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.

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.

Dans ce travail nous considérons des problèmes de planification de production sur plusieurs sites avec transport de produits entre ces sites. L’objectif est de synchroniser les deux problèmes (planification et transport) et de construire une solution globale. Le système de production sur chaque site est modélisé comme un problème de Capacitated Lot-Sizing où nous travaillons avec stock et ressources. Le transport de produits entre les sites se ramène à une version simplifiée du Vehicle Routing Problem où le temps est discrétisé. D’abord nous proposons un modèle linéaire en nombres entiers que nous appelons le « Lot-Sizing and Vehicle Routing Problem » (LSVRP). Puis nous présentons deux cas particuliers : le Single-item LSVRP (SLSVRP) et le Single-level LSVRP (1-LSVRP). Les problèmes sont traités ici par six heuristiques que nous avons développé. Quatre de ces méthodes sont des heuristiques qui utilisent la programmation en nombres entiers et prennent en compte la relaxation linéaire de quelques variables du problème. Elles s’appuient sur l’exploration partielle de l’arbre de décision et la fixation de variables. Les deux autres sont spécifiques pour les cas particuliers. La première, qui traite le S-LSVRP, est basée sur la propagation des ordres de production sur chaque site. Puis à chaque itération elle calcule le plan de transport compatible et essaie d’améliorer la solution en modifiant la production sur les sites. L’autre méthode consiste en une relaxation lagrangienne qui travaille sur une modélisation du 1-LSVRP en un problème de flot. Des résultats numériques et des analyses sont présentés pour évaluer l’efficacité de ces heuristiques. / In this work we consider some problems of scheduling both a production distributed on several sites and the transportation of items between those sites. By doing so, the objective is to synchronize the two components and to build a better overall solution. The production system on each site is modeled as a Capacitated Lot-Sizing Problem where stock both on resources and produced items is available. The inter-site items transportation is a simplified version of the Vehicle Routing Problem where time is discretized. We first propose a mixed integer linear programming formulation that we call “The Lot-Sizing and Vehicle Routing Problem” (LSVRP). Then we present two particular cases : The Single-item LSVRP (S-LSVRP) and The Single-level LSVRP (1-LSVRP). All those cases are treated here by the six heuristics we develloped. Four of those methods are MIP based heuristics and take in account the the linear relaxation of some variables of the problem. They rely on partial decision tree exploration along with variable fixing. The other two are specifics for the two particular cases. The one who treats the S-LSVRP is based on production order propagation over the sites. Then, at each iteration, it computes a compatible transportation schedule and it tries to improve the solution by modifying the production on the sites. The other method consists in a lagrangian relaxation that works with an adaptation of the 1-LSVRP into a flow problem. Computational results and analysis are presented to evaluate the efficiency of those heuristics.

Le problème de la gestion de la diversité est défini sur un ensemble partiellement ordonné d'élements possédant des demandes et des coûts unitaires de production. L'objectif est de produire un sous-ensemble de $k$ éléments références, $k$ étant un nombre donné, minimisant les coûts. Chaque élément non produit doit être remplacé par une référence qui lui est supérieure, ce qui implique un sur-coût. Après une étude théorique de complexité, nous modélisons ce problème grâce à un programme linéaire en nombres entiers, proche de ceux des problèmes de localisation $k$-médians. Pour résoudre ce programme, nous présentons un algorithme lagrangien, ainsi que de nombreux critères de fixation de variables permettant de réduire la taille du problème. Nous exploitons ensuite cet algorithme pour construire des solutions de bonne qualité. Nous développons enfin un algorithme exact de Séparation et Coupe. Nous étudions un certain type de coupes ainsi qu'une heuristique permettant de les générer. Nous concluons par des tests numériques effectués sur des instances réelles.

Dans cette thèse, nous traitons des problèmes d'intégration des décisions prises aux niveaux planification (tactique) et ordonnancement (opérationnel). Que ce soit en théorie ou en pratique, ces deux niveaux sont habituellement traités indépendamment l'un de l'autre. Ainsi, les objectifs de production à réaliser sont souvent incohérents avec la capacité réelle de l'atelier. Cette thèse propose des méthodes de résolution pour des problèmes intégrés de planification et d'ordonnancement. Nous développons un nouveau modèle mathématique qui prend en compte de manière originale les contraintes de séquencement des opérations sur les machines, garantissant ainsi la faisabilité du plan de production. Ce modèle est résolu à l'aide d'une heuristique Lagrangienne pour une séquence des opérations axée. Notre approche est originale à double titre : dans la mise à jour des multiplicateurs Lagrangiens (puisque il existe un nombre exponentiel de contraintes de capacité dans notre modèle), et par la proposition d'une nouvelle procédure de lissage pour la construction d'une solution réalisable. Nous développons ensuite deux approches, basées sur le recuit simulé et la recherche taboue, qui permettent d'améliorer la séquence des opérations sur les ressources et ainsi de chercher un plan de production optimal associé à une séquence réalisable. De nombreux résultats expérimentaux ont été effectués et valident l'efficacité de nos approches.

Dans ce travail nous considérons des problèmes de planification de production sur plusieurs sites avec transport de produits entre ces sites. L'objectif est de synchroniser les deux problèmes (planification et transport) et de construire une solution globale. Le système de production sur chaque site est modélisé comme un problème de Capacitated Lot-Sizing où nous travaillons avec stock et ressources. Le transport de produits entre les sites se ramène à une version simplifiée du Vehicle Routing Problem où le temps est discrétisé. D'abord nous proposons un modèle linéaire en nombres entiers que nous appelons le " Lot-Sizing and Vehicle Routing Problem " (LSVRP). Puis nous présentons deux cas particuliers : le Single-item LSVRP (SLSVRP) et le Single-level LSVRP (1-LSVRP). Les problèmes sont traités ici par six heuristiques que nous avons développé. Quatre de ces méthodes sont des heuristiques qui utilisent la programmation en nombres entiers et prennent en compte la relaxation linéaire de quelques variables du problème. Elles s'appuient sur l'exploration partielle de l'arbre de décision et la fixation de variables. Les deux autres sont spécifiques pour les cas particuliers. La première, qui traite le S-LSVRP, est basée sur la propagation des ordres de production sur chaque site. Puis à chaque itération elle calcule le plan de transport compatible et essaie d'améliorer la solution en modifiant la production sur les sites. L'autre méthode consiste en une relaxation lagrangienne qui travaille sur une modélisation du 1-LSVRP en un problème de flot. Des résultats numériques et des analyses sont présentés pour évaluer l'efficacité de ces heuristiques.

Les travaux présentés dans cette thèse portent sur le choix des produits semi-finis (PSF) à stocker dans un contexte de très forte diversité. Nous faisons tout d'abord un état de l'art de tout ce qui se rapporte à la diversité de produits. Nous nous sommes positionnés dans une optique de mise en place de cette diversité en adoptant une politique d'assemblage à la commande. La question centrale est la détermination des différents PSF à stocker. Pour ce faire, nous faisons appel à deux critères pour évaluer les différentes compositions de stock de PSF : i) le nombre de type de PSF stockés : NPSF et ii) le temps moyen d'assemblage : TMA. Nous proposons deux approches : 1) Pour un NPSF fixé, déterminer les références de PSF à stocker qui permettent de satisfaire la demande de produits en minimisant le TMA. 2) Déterminer le nombre et les références des PSF à stocker permettant de garantir un temps d'assemblage fixé au moindre coût. Nous avons proposé des formulations mathématiques des problèmes, ainsi que des heuristiques et des méthodes exactes pour résoudre ces différents problèmes.

Dès lors qu'une structure est organisée, la capacité de placer les bonnes personnes au bon moment devient cruciale pour satisfaire les besoins d'un service, d'une école ou d'une entreprise. On définit les problèmes de planification de personnel comme le procédé consistant à construire de manière optimisée les emplois du temps de travail du personnel. La motivation de cette thèse est de proposer un moyen d'exprimer ces problèmes de manière simple et automatique, sans avoir à intervenir ensuite dans le processus de résolution. Pour cela, nous proposons de rassembler le pouvoir de modélisation des automates avec la capacité de la programmation par contraintes à résoudre efficacement des problèmes complexes. Le caractère expressif des automates est ainsi utilisé pour modéliser des règles de séquencement complexes. Puis, afin d'intégrer ces automates multi-pondérés dans un modèle de programmation par contraintes, nous introduisons un nouvel algorithme de filtrage basé sur la relaxation lagrangienne : multicost-regular. Nous présentons également une version souple de cette contrainte permettant de pénaliser les violations d'une règle modélisée par un tel automate : soft-multicost-regular. Le modèle contraintes basé sur ces contraintes est automatiquement construit. Il est résolu à l'aide de la librairie de contraintes CHOCO et à été testé sur des instances réalistes issues des librairies ASAP et NRP10. La recherche de solution est améliorée par l'utilisation d'heuristiques spécifiques basées sur les regrets et s'appuyant sur la structure des contraintes multicost-regular et soft-multicost-regular.