Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Linéarisation et relaxation lagrangienne pour problèmes quadratiques en variables binaires

Serigne Guèye

Published Jan 1, 2002• 4 citations
OpenAlex

Abstract

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

Related papers

Optimisation non lineaire en variables bivalentes et applications

Rouquia Djabali

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.

•Jan 1, 1998•2 citations

Reformulations quadratiques convexes pour la programmation quadratique en variables 0-1

Marie-Christine Plateau

Dans ce travail de thèse, nous nous sommes intéressés à la résolution exacte de problèmes d'optimisation en variables 0-1 (notés (Q01)), comportant une fonction objectif quadratique soumise à des contraintes linéaires. Les problèmes de bipartition de graphe, d'affectation quadratique, du sac-à-dos quadratique en sont des exemples très connus et amplement étudiés dans la littérature de l'optimisation combinatoire. On les rencontre également, de façon plus concrète, dans les domaines scientifiques, économiques et industriels tels que le choix d'investissements, la gestion de portefeuilles, la conception de réseaux, le transport, etc. Malgré des travaux pionniers datant de plus de vingt ans, les problèmes non linéaires en variables bivalentes demeurent en général mal résolus. Parvenir à résoudre les programmes (Q01) de grande taille représente donc un enjeu très important. Le but de cette thèse est de proposer des méthodes originales et efficaces de résolution exacte des programmes (Q01). Plus précisément, notre approche prinicpale consiste en une reformulation quadratique convexe du problème initial dans le but d'utiliser les méthodes générales de résolution des programmes quadratiques convexes en variables entières. Cette approche peut être comparée, dans son esprit, à la reformulation de problèmes non linéaires en variables 0-1 par des problèmes linéaires en variables mixtes, technique étudiée depuis longtemps et connue sous le nom de linéarisation. Une partie de notre travail est consacrée à la présentation d'une nouvelle reformulation linéaire des programmes d'optimisation quadratique en 0-1. Dans les deux cas, les problèmes reformulés peuvent être résolus par des solveurs standards de programmes en variables mixtes. Nous présentons également de nombreuses expérimentations de notre reformulation quadratique convexe concernant trois problèmes non convexes classiques de l'optimisation combinatoire (le problème de bipartition, du sous-graphe le plus dense et un problème de minimisation d'échange d'outils). Les expérimentations montrent l'intérêt de l'approche : dans la plupart des cas, sur les instances étudiées, la méthode proposée est nettement plus efficace que les méthodes connues à ce jour. Des résultats expérimentaux sont également présentés, concernant trois problèmes convexes (le problème de plus court chemin probabiliste, un problème d'investissements, un problème d'ordonnancement). Notre approche peut également se révéler, dans certains cas, très intéressante.

•Jan 1, 2006•12 citations

Programmation quadratique en variables bivalentes sous contraintes linéaires. Application au placement de taches dans les systèmes distribués et a la partition de graphes

Alain Faye

Cette thèse traite du problème de la minimisation d'une fonction pseudo-booléenne quadratique (f. P. B. Q. ) sous des contraintes linéaires et de son application au problème de placement de taches sur les systèmes distribues ainsi qu'au problème de partition de graphes. Nous proposons le calcul de plusieurs bornes inférieures. Dans le cas de contraintes linéaires de transport, nous proposons une réduction de la fonction objectif et le calcul d'une borne inférieure par implications logiques. Nous utilisons cette borne inférieure pour la résolution d'un problème de placement de taches avec contraintes de ressources. Nous résolvons des problèmes de l'ordre de 20 taches et 3 processeurs. Dans le cas de contraintes linéaires quelconques, nous calculons une borne inférieure par une décomposition optimale, sous certaines hypothèses, de la fonction objectif. Nous appliquons le calcul de cette borne au problème de placement de taches sans contraintes de ressources. Une étude expérimentale montre la bonne qualité de cette borne: nous obtenons des écarts relatifs, avec la valeur exacte du problème, inférieurs a 2% pour des problèmes comportant 60 taches et 15 processeurs. Nous proposons aussi le calcul d'une borne inférieure pour un problème de partition de graphes. Cette borne est obtenue par un algorithme de coupes polyédriques. Une étude expérimentale montre la bonne qualité de cette borne pour certaines classes de problèmes. Dans le cadre de la minimisation d'une f. P. B. Q. Sous une contrainte linéaire, nous proposons le calcul d'une borne inférieure par un programme linéaire continu. Nous prouvons que cette borne est la meilleure valeur que l'on puisse obtenir sous certaines hypothèses. Ce résultat se situe dans le prolongement des travaux de Hammer, Hansen et Simeone, dans le cas sans contraintes, sur le toit dual. Nous terminons par une étude théorique comparative de ces différentes bornes

•Jan 1, 1994•3 citations

Méthodes de génération de colonnes en programmatin quadratique mixte binaire

Enrico Bettiol

La programmation non lineaire mixte peut modeliser un grand nombre de problemes reels. Cependant, ces problemes peuvent contenir de nombreuses variables ou contraintes, il convient donc de proposer des methodes de decomposition afin de les resoudre efficacement. Parmi ces techniques on peut citer la generation de colonnes et notamment la decomposition de Dantzig-Wolfe. Il s’agit d’une reformulation du probleme original, qui permet de generer une sequence de sous-problemes plus simples, appeles maitre et pricing, pour obtenir la valeur optimale. Developpee d’abord pour les problemes lineaires, la decomposition de Dantzig-Wolfe peut etre generalisee a des problemes convexes: dans ce contexte, elle est notamment connue sous le nom de decomposition simpliciale. Cette these presente des algorithmes de decomposition pour des problemes quadratiques. La premiere partie de ce manuscrit est dediee aux problemes quadratiques convexes, continus et mixtes binaires. Dans la deuxieme partie, des algorithmes pour resoudre des problemes binaires avec contraintes quadratiques sont presentes. La premiere partie est consacree a la resolution de problemes convexes, quadratiques et continus. Un algorithme base sur la decomposition simpliciale est propose: des nouveaux elements sont ajoutes a la fois au probleme maitre et au pricing; nous avons teste notre algorithme sur une grande quantite d’instances avec une structure determinee, et nos resultats montrent que l’algorithme que nous proposons est tres efficace par rapport a Cplex, un solveur generique pour ces problemes. Ce premier travail a ete soumis a un journal pour publication. Ensuite, nous etendons cet algorithme aux problemes convexes mixtes binaires. Nous incorporons la methode pour le cas continu dans un algorithme de branch and bound qui nous permet d’exploiter des proprietes de notre formulation. Dans ce contexte aussi, des resultats numeriques sont fournis: ils montrent que, dans certains cas, les performances de notre algorithme sont efficaces par rapport a Cplex. Ce travail est en preparation pour soumission a un journal. La deuxieme partie de cette these est dediee a l’etude d’algorithmes pour des problemes quadratiques avec contraintes quadratiques. On se concentre sur les problemes binaires, dont la relaxation continue peut etre non convexe. Nous considerons en premier lieu la formulation etendue avec une matrice qui represente les produits des variables. Nous proposons ensuite un algorithme base sur la decomposition 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 cone des matrices completement positives et des matrices semidefinies positives. Notre algorithme permet de resoudre 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, un solveur ad-hoc. On montre aussi que la relaxation BQP est une reformulation du probleme binaire original, en exploitant un resultat sur les matrices completement positives, pour les problemes a contraintes lineaires en egalite. Ensuite, nous considerons des problemes ou les matrices sont decomposables par blocs. Une relaxation basee sur les blocs est proposee et nous prouvons que cette relaxation est valide pour la relaxation BQP. De plus, prouver l’equivalence entre les deux relaxations est un probleme de completion BQP. La relaxation decomposee par blocs est BQPcompletable dans certains cas, mais n’est pas possible dans d’autres cas. A partir de resultats experimentaux, nous conjecturons que la classe de problemes qui sont BQPcompletables est la classe de problemes dont le graphe de specification des matrices est chordal. Des resultats computationnels montrent que la formulation par blocs, dans certaines instances ou elle est equivalente a la relaxation originale, peut etre beaucoup plus efficace. Ce travail est en preparation pour soumission a un journal.

•Nov 6, 2019•0 citations

Plénière: Programmation non-linéaire en variables mixtes et applications

Pierre Bonami

La programmation non-linéaire en variable mixtes consiste à minimiser une fonction non-linéaire sur un ensemble de solutions décrit par des fonctions non-linéaires et des contraintes d'intégrité portant sur tout ou partie des variables. Depuis une dizaine d'année de nombreux travaux se sont intéressé aux aspects théoriques et algorithmiques de la résolution de ces problèmes. Ces travaux ont donné lieu à la réalisation de plusieurs solveurs open-source ou commerciaux. Dans cette présentation, nous décrirons les principales classes de problèmes et les idées algorithmiques implémentées dans les logiciels de résolutions actuels. Nous nous intéresserons en particulier au cas où la relaxation continue naturelle du problème est un problème convexe et au cas ou seule la fonction objective est non-linéaire et est quadratique. Nous nous appuierons en particulier sur les exemples du solveur Bonmin et du solveur global de programmation quadratique non-convexe récemment introduit dans le logiciel CPLEX.

•Feb 26, 2014•0 citations

Relaxations in mixed-integer quadratically constrained programming and robust programming

Guanglei Wang

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

•Nov 28, 2016•4 citations
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
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.
Dans ce travail de thèse, nous nous sommes intéressés à la résolution exacte de problèmes d'optimisation en variables 0-1 (notés (Q01)), comportant une fonction objectif quadratique soumise à des contraintes linéaires. Les problèmes de bipartition de graphe, d'affectation quadratique, du sac-à-dos quadratique en sont des exemples très connus et amplement étudiés dans la littérature de l'optimisation combinatoire. On les rencontre également, de façon plus concrète, dans les domaines scientifiques, économiques et industriels tels que le choix d'investissements, la gestion de portefeuilles, la conception de réseaux, le transport, etc. Malgré des travaux pionniers datant de plus de vingt ans, les problèmes non linéaires en variables bivalentes demeurent en général mal résolus. Parvenir à résoudre les programmes (Q01) de grande taille représente donc un enjeu très important. Le but de cette thèse est de proposer des méthodes originales et efficaces de résolution exacte des programmes (Q01). Plus précisément, notre approche prinicpale consiste en une reformulation quadratique convexe du problème initial dans le but d'utiliser les méthodes générales de résolution des programmes quadratiques convexes en variables entières. Cette approche peut être comparée, dans son esprit, à la reformulation de problèmes non linéaires en variables 0-1 par des problèmes linéaires en variables mixtes, technique étudiée depuis longtemps et connue sous le nom de linéarisation. Une partie de notre travail est consacrée à la présentation d'une nouvelle reformulation linéaire des programmes d'optimisation quadratique en 0-1. Dans les deux cas, les problèmes reformulés peuvent être résolus par des solveurs standards de programmes en variables mixtes. Nous présentons également de nombreuses expérimentations de notre reformulation quadratique convexe concernant trois problèmes non convexes classiques de l'optimisation combinatoire (le problème de bipartition, du sous-graphe le plus dense et un problème de minimisation d'échange d'outils). Les expérimentations montrent l'intérêt de l'approche : dans la plupart des cas, sur les instances étudiées, la méthode proposée est nettement plus efficace que les méthodes connues à ce jour. Des résultats expérimentaux sont également présentés, concernant trois problèmes convexes (le problème de plus court chemin probabiliste, un problème d'investissements, un problème d'ordonnancement). Notre approche peut également se révéler, dans certains cas, très intéressante.
Cette thèse traite du problème de la minimisation d'une fonction pseudo-booléenne quadratique (f. P. B. Q. ) sous des contraintes linéaires et de son application au problème de placement de taches sur les systèmes distribues ainsi qu'au problème de partition de graphes. Nous proposons le calcul de plusieurs bornes inférieures. Dans le cas de contraintes linéaires de transport, nous proposons une réduction de la fonction objectif et le calcul d'une borne inférieure par implications logiques. Nous utilisons cette borne inférieure pour la résolution d'un problème de placement de taches avec contraintes de ressources. Nous résolvons des problèmes de l'ordre de 20 taches et 3 processeurs. Dans le cas de contraintes linéaires quelconques, nous calculons une borne inférieure par une décomposition optimale, sous certaines hypothèses, de la fonction objectif. Nous appliquons le calcul de cette borne au problème de placement de taches sans contraintes de ressources. Une étude expérimentale montre la bonne qualité de cette borne: nous obtenons des écarts relatifs, avec la valeur exacte du problème, inférieurs a 2% pour des problèmes comportant 60 taches et 15 processeurs. Nous proposons aussi le calcul d'une borne inférieure pour un problème de partition de graphes. Cette borne est obtenue par un algorithme de coupes polyédriques. Une étude expérimentale montre la bonne qualité de cette borne pour certaines classes de problèmes. Dans le cadre de la minimisation d'une f. P. B. Q. Sous une contrainte linéaire, nous proposons le calcul d'une borne inférieure par un programme linéaire continu. Nous prouvons que cette borne est la meilleure valeur que l'on puisse obtenir sous certaines hypothèses. Ce résultat se situe dans le prolongement des travaux de Hammer, Hansen et Simeone, dans le cas sans contraintes, sur le toit dual. Nous terminons par une étude théorique comparative de ces différentes bornes
La programmation non lineaire mixte peut modeliser un grand nombre de problemes reels. Cependant, ces problemes peuvent contenir de nombreuses variables ou contraintes, il convient donc de proposer des methodes de decomposition afin de les resoudre efficacement. Parmi ces techniques on peut citer la generation de colonnes et notamment la decomposition de Dantzig-Wolfe. Il s’agit d’une reformulation du probleme original, qui permet de generer une sequence de sous-problemes plus simples, appeles maitre et pricing, pour obtenir la valeur optimale. Developpee d’abord pour les problemes lineaires, la decomposition de Dantzig-Wolfe peut etre generalisee a des problemes convexes: dans ce contexte, elle est notamment connue sous le nom de decomposition simpliciale. Cette these presente des algorithmes de decomposition pour des problemes quadratiques. La premiere partie de ce manuscrit est dediee aux problemes quadratiques convexes, continus et mixtes binaires. Dans la deuxieme partie, des algorithmes pour resoudre des problemes binaires avec contraintes quadratiques sont presentes. La premiere partie est consacree a la resolution de problemes convexes, quadratiques et continus. Un algorithme base sur la decomposition simpliciale est propose: des nouveaux elements sont ajoutes a la fois au probleme maitre et au pricing; nous avons teste notre algorithme sur une grande quantite d’instances avec une structure determinee, et nos resultats montrent que l’algorithme que nous proposons est tres efficace par rapport a Cplex, un solveur generique pour ces problemes. Ce premier travail a ete soumis a un journal pour publication. Ensuite, nous etendons cet algorithme aux problemes convexes mixtes binaires. Nous incorporons la methode pour le cas continu dans un algorithme de branch and bound qui nous permet d’exploiter des proprietes de notre formulation. Dans ce contexte aussi, des resultats numeriques sont fournis: ils montrent que, dans certains cas, les performances de notre algorithme sont efficaces par rapport a Cplex. Ce travail est en preparation pour soumission a un journal. La deuxieme partie de cette these est dediee a l’etude d’algorithmes pour des problemes quadratiques avec contraintes quadratiques. On se concentre sur les problemes binaires, dont la relaxation continue peut etre non convexe. Nous considerons en premier lieu la formulation etendue avec une matrice qui represente les produits des variables. Nous proposons ensuite un algorithme base sur la decomposition 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 cone des matrices completement positives et des matrices semidefinies positives. Notre algorithme permet de resoudre 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, un solveur ad-hoc. On montre aussi que la relaxation BQP est une reformulation du probleme binaire original, en exploitant un resultat sur les matrices completement positives, pour les problemes a contraintes lineaires en egalite. Ensuite, nous considerons des problemes ou les matrices sont decomposables par blocs. Une relaxation basee sur les blocs est proposee et nous prouvons que cette relaxation est valide pour la relaxation BQP. De plus, prouver l’equivalence entre les deux relaxations est un probleme de completion BQP. La relaxation decomposee par blocs est BQPcompletable dans certains cas, mais n’est pas possible dans d’autres cas. A partir de resultats experimentaux, nous conjecturons que la classe de problemes qui sont BQPcompletables est la classe de problemes dont le graphe de specification des matrices est chordal. Des resultats computationnels montrent que la formulation par blocs, dans certaines instances ou elle est equivalente a la relaxation originale, peut etre beaucoup plus efficace. Ce travail est en preparation pour soumission a un journal.
La programmation non-linéaire en variable mixtes consiste à minimiser une fonction non-linéaire sur un ensemble de solutions décrit par des fonctions non-linéaires et des contraintes d'intégrité portant sur tout ou partie des variables. Depuis une dizaine d'année de nombreux travaux se sont intéressé aux aspects théoriques et algorithmiques de la résolution de ces problèmes. Ces travaux ont donné lieu à la réalisation de plusieurs solveurs open-source ou commerciaux. Dans cette présentation, nous décrirons les principales classes de problèmes et les idées algorithmiques implémentées dans les logiciels de résolutions actuels. Nous nous intéresserons en particulier au cas où la relaxation continue naturelle du problème est un problème convexe et au cas ou seule la fonction objective est non-linéaire et est quadratique. Nous nous appuierons en particulier sur les exemples du solveur Bonmin et du solveur global de programmation quadratique non-convexe récemment introduit dans le logiciel CPLEX.
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