Nous considérons le problème (QP) de la minimisation d'une fonction quadratique sous des contraintes linéaires ou quadratiques. Les variables sont entières et bornées. Ce problème très général permet de modéliser de nombreux problèmes classiques en Optimisation Combinatoire et constitue une première généralisation de la programmation linéaire en nombres entiers. Une différence majeure entre (QP) et les programmes linéaires en nombres entiers réside dans le fait que, en général, sa relaxation continue fournit un problème lui aussi NP-difficile. Pour contourner cette difficulté, la reformulation quadratique convexe transforme (QP) en un problème (QP') équivalent mais dont la relaxation continue est un problème convexe. Afin de calculer une solution optimale de (QP), on peut alors résoudre (QP') par un algorithme d'énumération implicite basé sur l'optimisation continue convexe. Nous faisons un tour d'horizon de développements récents de cette approche. Nous montrons en particulier comment les relaxations semi-définies positives permettent de construire les problèmes équivalents (QP') les plus intéressants. Dans le cas des variables binaires, nous donnons une vision des linéarisations classiques comme un cas particulier de reformulation quadratique convexe. Enfin, nous illustrons la généralité et l'efficacité expérimentale de la résolution exacte par reformulation quadratique convexe sur différents problèmes d'Optimisation Combinatoire. Références A. Billionnet et S. Elloumi. Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem . Mathematical Programming, 109(1): 55-68, 2007. A. Billionnet, S. Elloumi et M.-C. Plateau. Improving standard solvers convex reformulation for constrained quadratic 0-1 programs: the QCR method. Discrete Applied Math, vol. 157(6), 2009, pp. 1185-1197. A. Billionnet, S. Elloumi et A. Lambert. Extending the QCR method to general mixed-integer programs. Mathematical Programming, vol. 131(1), 2012, pp.381-401
Nous considérons le problème (QP) de la minimisation d'une fonction quadratique sous des contraintes linéaires ou quadratiques. Les variables sont entières et bornées. Ce problème très général permet de modéliser de nombreux problèmes classiques en Optimisation Combinatoire et constitue une première généralisation de la programmation linéaire en nombres entiers. Une différence majeure entre (QP) et les programmes linéaires en nombres entiers réside dans le fait que, en général, sa relaxation continue fournit un problème lui aussi NP-difficile. Pour contourner cette difficulté, la reformulation quadratique convexe transforme (QP) en un problème (QP') équivalent mais dont la relaxation continue est un problème convexe. Afin de calculer une solution optimale de (QP), on peut alors résoudre (QP') par un algorithme d'énumération implicite basé sur l'optimisation continue convexe. Nous faisons un tour d'horizon de développements récents de cette approche. Nous montrons en particulier comment les relaxations semi-définies positives permettent de construire les problèmes équivalents (QP') les plus intéressants. Dans le cas des variables binaires, nous donnons une vision des linéarisations classiques comme un cas particulier de reformulation quadratique convexe. Enfin, nous illustrons la généralité et l'efficacité expérimentale de la résolution exacte par reformulation quadratique convexe sur différents problèmes d'Optimisation Combinatoire. Références A. Billionnet et S. Elloumi. Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem . Mathematical Programming, 109(1): 55-68, 2007. A. Billionnet, S. Elloumi et M.-C. Plateau. Improving standard solvers convex reformulation for constrained quadratic 0-1 programs: the QCR method. Discrete Applied Math, vol. 157(6), 2009, pp. 1185-1197. A. Billionnet, S. Elloumi et A. Lambert. Extending the QCR method to general mixed-integer programs. Mathematical Programming, vol. 131(1), 2012, pp.381-401
Dans ce travail de these, nous nous sommes interesses a la resolution exacte de problemes d'optimisation en variables 0-1 (notes (Q01)), comportant une fonction objectif quadratique soumise a des contraintes lineaires. Les problemes de bipartition de graphe, d'affectation quadratique, du sac-a-dos quadratique en sont des exemples tres connus et amplement etudies dans la litterature de l'optimisation combinatoire. On les rencontre egalement, de facon plus concrete, dans les domaines scientifiques, economiques et industriels tels que le choix d'investissements, la gestion de portefeuilles, la conception de reseaux, le transport, etc. Malgre des travaux pionniers datant de plus de vingt ans, les problemes non lineaires en variables bivalentes demeurent en general mal resolus. Parvenir a resoudre les programmes (Q01) de grande taille represente donc un enjeu tres important. Le but de cette these est de proposer des methodes originales et efficaces de resolution exacte des programmes (Q01). Plus precisement, notre approche prinicpale consiste en une reformulation quadratique convexe du probleme initial dans le but d'utiliser les methodes generales de resolution des programmes quadratiques convexes en variables entieres. Cette approche peut etre comparee, dans son esprit, a la reformulation de problemes non lineaires en variables 0-1 par des problemes lineaires en variables mixtes, technique etudiee depuis longtemps et connue sous le nom de linearisation. Une partie de notre travail est consacree a la presentation d'une nouvelle reformulation lineaire des programmes d'optimisation quadratique en 0-1. Dans les deux cas, les problemes reformules peuvent etre resolus par des solveurs standards de programmes en variables mixtes. Nous presentons egalement de nombreuses experimentations de notre reformulation quadratique convexe concernant trois problemes non convexes classiques de l'optimisation combinatoire (le probleme de bipartition, du sous-graphe le plus dense et un probleme de minimisation d'echange d'outils). Les experimentations montrent l'interet de l'approche : dans la plupart des cas, sur les instances etudiees, la methode proposee est nettement plus efficace que les methodes connues a ce jour. Des resultats experimentaux sont egalement presentes, concernant trois problemes convexes (le probleme de plus court chemin probabiliste, un probleme d'investissements, un probleme d'ordonnancement). Notre approche peut egalement se reveler, dans certains cas, tres interessante.
Méthodes de génération de colonnes en programmation quadratique mixte binaire La programmation non linéaire mixte peut modéliser un grand nombre de problèmes réels. Cependant, ces problèmes peuvent contenir de nombreuses variables ou contraintes, il convient donc de proposer des méthodes de décomposition afin de les résoudre efficacement. Parmi ces techniques on peut citer la génération de colonnes et notamment la décomposition de Dantzig-Wolfe. Il s’agit d’une reformulation du problème original, qui permet de générer une séquence de sous-problèmes plus simples, appelés maître etpricing, pour obtenir la valeur optimale. Développée d’abord pour les problèmes linéaires, la décomposition de Dantzig-Wolfe peut être généralisée à des problèmes convexes: dans ce contexte, elle est notamment connue sous le nom de décomposition simpliciale. Cette thèse présente des algorithmes de décomposition pour des problèmes quadratiques. La première partie de ce manuscrit est dédiée aux problèmes quadratiques convexes, continus et mixtes binaires. Dans la deuxième partie, des algorithmes pour résoudre des problèmes binaires avec contraintes quadratiques sont présentés. La première partie est consacrée à la résolution de problèmes convexes, quadratiques et continus. Un algorithme basé sur la décomposition simpliciale est proposé: des nouveaux éléments sont ajoutés à la fois au problème maître et au pricing; nous avons testé notre algorithme sur une grande quantité d’instances avec une structure déterminée, et nos résultats montrent que l’algorithme que nous proposons est très efficace par rapport à Cplex, un solveur générique pour ces problèmes. Ce premier travail a été soumis à un journal pour publication. Ensuite, nous étendons cet algorithme aux problèmes convexes mixtes binaires. Nous incorporons la méthode pour le cas continu dans un algorithme de branch and bound qui nous permet d’exploiter des propriétés de notre formulation. Dans ce contexte aussi, des résultats numériques sont fournis: ils montrent que, dans certains cas, les performances de notre algorithme sont efficaces par rapport à Cplex. Ce travail est en préparation pour soumission à un journal. La deuxième partie de cette thèse est dédiée à l’étude d’algorithmes pour des problèmes quadratiques avec contraintes quadratiques. On se concentre sur les problèmes binaires, dont la relaxation continue peut être non convexe. Nous considérons en premier lieu la formulation étendue avec une matrice qui représente les produits des variables. Nous proposons ensuite un algorithme basé sur la décomposition de Dantzig-Wolfe pour obtenir une relaxation dans le Boolean Quadric Polytope (BQP). Ce polytope est connu aussi comme Correlation polytope et il est strictement contenu dans le cône des matrices complètement positives et des matrices semi définies positives. Notre algorithme permet de résoudre cette relaxation, les bornes obtenues sont plus fortes que les bornes SDP et, dans certains cas, les temps de calcul sont comparables ou meilleurs que ceux de BiqCrunch, unsolveur ad-hoc. On montre aussi que la relaxation BQP est une reformulation du problème binaire original, en exploitant un résultat sur les matrices complètement positives, pour les problèmes à contraintes linéaires en égalité. Ensuite, nous considérons des problèmes où les matrices sont décomposables par blocs. On montre aussi que la relaxation BQP est une reformulation du problème binaire original, en exploitant un résultat sur les matrices complètement positives, pour les problèmes à contraintes linéaires en égalité. Ensuite, nous considérons des problèmes où les matrices sont décomposables par blocs. Une relaxation basée sur les blocs est proposée et nous prouvons que cette relaxation est valide pour la relaxation BQP. De plus, prouver l’équivalence entre les deux relaxations est un problème de complétion BQP. La relaxation décomposée par blocs est BQP complétable dans certains cas, mais n’est pas possible dans d’autres cas [....].
La programmation non linéaire mixte peut modéliser un grand nombre de problèmes réels. Cependant, ces problèmes peuvent contenir de nombreuses variables ou contraintes, il convient donc de proposer des méthodes de décomposition afin de les résoudre efficacement. Parmi ces techniques on peut citer la génération de colonnes et notamment la décomposition de Dantzig-Wolfe. Il s’agit d’une reformulation du problème original, qui permet de générer une séquence de sous-problèmes plus simples, appelés maître etpricing, pour obtenir la valeur optimale. Développée d’abord pour les problèmes linéaires, la décomposition de Dantzig-Wolfe peut être généralisée à des problèmes convexes: dans ce contexte, elle est notamment connue sous le nom de décomposition simpliciale. Cette thèse présente des algorithmes de décomposition pour des problèmes quadratiques. La première partie de ce manuscrit est dédiée aux problèmes quadratiques convexes, continus et mixtes binaires. Dans la deuxième partie, des algorithmes pour résoudre des problèmes binaires avec contraintes quadratiques sont présentés. La première partie est consacrée à la résolution de problèmes convexes, quadratiques et continus. Un algorithme basé sur la décomposition simpliciale est proposé: des nouveaux éléments sont ajoutés à la fois au problème maître et au pricing; nous avons testé notre algorithme sur une grande quantité d’instances avec une structure déterminée, et nos résultats montrent que l’algorithme que nous proposons est très efficace par rapport à Cplex, un solveur générique pour ces problèmes. Ce premier travail a été soumis à un journal pour publication. Ensuite, nous étendons cet algorithme aux problèmes convexes mixtes binaires. Nous incorporons la méthode pour le cas continu dans un algorithme de branch and bound qui nous permet d’exploiter des propriétés de notre formulation. Dans ce contexte aussi, des résultats numériques sont fournis: ils montrent que, dans certains cas, les performances de notre algorithme sont efficaces par rapport à Cplex. Ce travail est en préparation pour soumission à un journal. La deuxième partie de cette thèse est dédiée à l’étude d’algorithmes pour des problèmes quadratiques avec contraintes quadratiques. On se concentre sur les problèmes binaires, dont la relaxation continue peut être non convexe. Nous considérons en premier lieu la formulation étendue avec une matrice qui représente les produits des variables. Nous proposons ensuite un algorithme basé sur la décomposition de Dantzig-Wolfe pour obtenir une relaxation dans le Boolean Quadric Polytope (BQP). Ce polytope est connu aussi comme Correlation polytope et il est strictement contenu dans le cône des matrices complètement positives et des matrices semi définies positives. Notre algorithme permet de résoudre cette relaxation, les bornes obtenues sont plus fortes que les bornes SDP et, dans certains cas, les temps de calcul sont comparables ou meilleurs que ceux de BiqCrunch, unsolveur ad-hoc. On montre aussi que la relaxation BQP est une reformulation du problème binaire original, en exploitant un résultat sur les matrices complètement positives, pour les problèmes à contraintes linéaires en égalité. Ensuite, nous considérons des problèmes où les matrices sont décomposables par blocs. On montre aussi que la relaxation BQP est une reformulation du problème binaire original, en exploitant un résultat sur les matrices complètement positives, pour les problèmes à contraintes linéaires en égalité. Ensuite, nous considérons des problèmes où les matrices sont décomposables par blocs. Une relaxation basée sur les blocs est proposée et nous prouvons que cette relaxation est valide pour la relaxation BQP. De plus, prouver l’équivalence entre les deux relaxations est un problème de complétion BQP. La relaxation décomposée par blocs est BQP complétable dans certains cas, mais n’est pas possible dans d’autres cas [....].
Un probleme quadratique en variables binaires est un probleme d'optimisation en variables binaires consistant a minimiser une fonction objectif quadratique sous des contraintes lineaires. Dans cas general, c'est un probleme dificile a resoudre de maniere exacte (NP- difficile), trouvant de nombreuses applications pratiques. La resolution exacte du probleme passe par determination de bornes inferieures qu'il convient d'integrer dans des schemas de separation et evaluation progressive (ou Branch-and-Bound). Plusieurs techniques, allant de programmation semi-definie positive a l'optimisation globale, sont utilisees pour determiner ces bornes. Nous nous sommes particulierement interesses aux methodes lagrangiennes et aux techniques de linearisation. Nous avons traite dans cette these deux instances particulieres du probleme : la bipolarisation de graphes avec contrainte de cardinalite et le probleme quadratique en variables binaires sans contrainte. Pour bipartition de graphes, nous avons propose une demarche hybride melant relaxation lagrangienne et linearisation de probleme. Les tests numeriques, issus de l'algorithme resultant, ont montre des ameliorations significatives par rapport a certaines techniques existantes. Pour probleme quadratique en variables binaires sans contrainte, des etudes sur les techniques de linearisation ont ete effectuees. Elles consistent a remplacer fonction objectif quadratique par une forme lineaire, grâce a l'ajout de variables permettant de remplacer les parties quadratiques de fonction. L'ajout de ces variables entrainent [sic] aussi l'ajout de contraintes visant a s'assurer de validite du remplacement. Apres etude et tests des linearisations existantes, nous unifions ces techniques dans un schema general de linearisation. De nouveaux modeles ont, grâce a ce schema , vu jour et ameliorent significativement les resultats numeriques des formulations lineaires precedentes
Relaxations en programmation mixte en nombres entiers avec contraintes quadratiques et en programmation robuste De nombreux problèmes de la vie réelle sont exprimés sous la forme de décisions à prendre à l’aide de l’information accessible dans le but d’atteindre certains objectifs. La programmation numérique a prouvé être un outil efficace pour modéliser et résoudre une grande variété de problèmes de ce type. Cependant, de nombreux problèmes en apparence faciles sont encore durs à résoudre. Et même des problèmes faciles de programmation linéaire deviennent durs avec l’incertitude de l’information disponible. Motivés par un problème de télécommunication où l’on doit associer des machines virtuelles à des serveurs tout en minimisant les coûts, nous avons employé plusieurs outils de programmation mathématique dans le but de résoudre efficacement le problème, et développé de nouveaux outils pour des problèmes plus généraux. Dans l’ensemble, résumons les principaux résultats de cette thèse comme suit. Une formulation exacte et plusieurs reformulations pour le problème d’affectation de machines virtuelles dans le cloud sont données. Nous utilisons plusieurs inégalités valides pour renforcer la formulation exacte, accélérant ainsi l’algorithme de résolution de manière significative. Nous donnons en outre un résultat géométrique sur la qualité de la borne lagrangienne montrant qu’elle est généralement beaucoup plus forte que la borne de la relaxation continue. Une hiérarchie de relaxation est également proposée en considérant une séquence de couverture de l’ensemble de la demande. Ensuite, nous introduisons une nouvelle formulation induite par les symétries du problème. Cette formulation permet de réduire considérablement le nombre de termes bilinéaires dans le modèle, et comme prévu, semble plus efficace que les modèles précédents. Deux approches sont développées pour la construction d’enveloppes convexes et concaves pour l’optimisation bilinéaire sur un hypercube. Nous établissons plusieurs connexions théoriques entre différentes techniques et nous discutons d’autres extensions possibles. Nous montrons que deux variantes de formulations pour approcher l’enveloppe convexe des fonctions bilinéaires sont équivalentes. Nous introduisons un nouveau paradigme sur les problèmes linéaires généraux avec des paramètres incertains. Nous proposons une hiérarchie convergente de problèmes d’optimisation robuste – approche robuste multipolaire, qui généralise les notions de robustesse statique, de robustesse d’affinement ajustable, et de robustesse entièrement ajustable. En outre, nous montrons que l’approche multipolaire peut générer une séquence de bornes supérieures et une séquence de bornes inférieures en même temps et les deux séquences convergent vers la valeur robuste des FARC sous certaines hypothèses modérées
Le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sous une contrainte lineaire est np-difficile. Par consequent, l'obtention de bornes inferieures est importante. Nous avons etudie differentes methodes pour calculer des bornes inferieures de la solution optimale et nous montrons que le calcul de ces bornes revient a la resolution de programmes lineaires continus. La principale originalite de nos travaux, est qu'ils generalisent les bornes proposees pour le probleme de la minimisation d'une fonction pseudo-booleenne quadratique sans contraintes. Nous avons ensuite applique le calcul des bornes proposees a des problemes particuliers ; la bipartition minimale d'un graphe, l'ensemble stable de cardinal maximal d'un graphe et le sac a dos quadratique. Pour chaque probleme nous avons mis en evidence des proprietes interessantes qui permettent de simplifier le calcul des bornes et des coupes qui permettent d'ameliorer la qualite des bornes proposees. En outre, pour reduire le temps de resolution des programmes lineaires continus consideres, nous avons elabore une methode de coupes qui permet de resoudre des programmes lineaires continus de maniere approchee. Enfin, pour chaque probleme particulier, nous avons integre notre methode de coupes dans un algorithme de resolution exacte (branch and cut). Nous nous sommes egalement interesse a un probleme d'optimisation lie a l'architecture des futurs reseaux numeriques urbains. Le probleme est de determiner une topologie en anneau de cout minimal qui respecte un certain nombre de contraintes. Nous avons modelise ce probleme a l'aide de la programmation mathematique et montre qu'une methode de resolution fondee sur la programmation lineaire en nombres entiers et les methodes de coupes permet de traiter des problemes reels avec un temps de calcul raisonnable.