Column generation methods for quadratic mixed binary programming

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 [....].