A Novel Approach to Tightening Semidefinite Relaxations for Certain Combinatorial Problems

Ce mémoire présente une nouvelle famille de coupes nommées contraintes polytopiques kprojection (kPPCs) qui peuvent être utilisées pour résoudre certains problèmes quadratiques binaires. Notamment les problèmes qui satisfont une propriété de projection pour les solutions réalisables sur un sous-graphe induit ont la même structure que les solutions faisables sur le graphe entier. Parmi ces problèmes se trouvent le problème max-cut et le problème d'ensemble stable (stable set problem). Les coupes sont généralement des inégalités, cependant les kPPCs s'en distinguent par le fait qu'elles sont formées d'un ensemble d'inégalités. De plus, elle peuvent être définies pour un seul sous-graphe induit ou pour un ensemble de sous-graphes induits, et sont utilisées pour resserrer les relaxations en programmation semi-définie. Trois aspects des kPPCs sont examinés dans ce mémoire : une hiérarchie qui converge vers une formulation exacte, une formulation pour trouver la contrainte kPPC la plus violée, et l'amélioration de la borne supérieure (pour un problème de maximisation) d'une implémentation pratique de kPPCs pour le problème max-cut. La relaxation SDP avec kPPCs forme une hiérarchie. Le kème niveau de la hiérarchie est la relaxation SDP avec kPPCs pour tous les sous-graphes induits de taille k. Lorsque k augmente, l'intensité de la relaxation augmente également puisque CUTk ⊆ CUTk+1 où CUTk est le polytope de coupe de taille k. Au nème niveau, la formulation n'est plus une relaxation et rejoint exactement le problème d'origine CUTn. Il existe n/k sous-graphes induits uniques pour un graphe à n noeuds. Par conséquent, il n'est possible d'énumérer explicitement les niveaux de la hiérarchie que pour de petits exemples. Cependant, la force de la hiérarchie des kPPCs est que la matrice semi-définie positive, qui est variable dans la relaxation SDP, n'augmente pas en taille lorsque le niveau augmente, contrairement aux hiérarchies de Lasserre. Pour un sous-graphe induit donné I, un modèle d'optimisation (nommé distance-au-polytope) est présenté pour déterminer si la solution optimale de la relaxation SDP viole les kPPCs pour I et, dans l'affirmative, pour quantifier la violation. Le modèle distance-au-polytope a une fonction objectif quadratique, des contraintes linéaires et se résout rapidement. La solution optimale est la distance euclidienne entre le mineur principal de la solution optimale de la relaxation (X*I) et le polytope de coupe (CUT|I|). Si la distance est égale à zéro, alors l'inclusion de kPPCs pour I dans la relaxation SDP ne resserrera pas la borne. Si la distance est strictement supérieure à zéro, alors les kPPCs pour I ne sont pas satisfaites par la solution courante. Par conséquent, leur inclusion dans la relaxation SDP changera la solution courante X* (bien qu'une amélioration de la borne ne soit pas garantie). Ce mémoire présente un modèle d'optimisation binaire-mixte dans un cône de second ordre (SOC) qui, pour un k donné, trouve la kPPC la plus éloignée du polytope de coupe. Le problème interne est le modèle distance-au-polytope. Le problème externe comporte des variables binaires qui prennent en compte tous les sous-graphes induits de taille k. Les problèmes à deux niveaux sont intrinsèquement difficiles à résoudre. Une reformulation est donc présentée qui change le problème à deux niveaux en un problème SOC équivalent à un seul niveau. La reformulation utilise des techniques telles que les conditions KKT, les contraintes disjointes et le saut de dualité. De plus, nous montrons comment renforcer le modèle à un seul niveau en incluant des contraintes de bris de symétrie et en incluant des variables binaires additionnelles qui réduisent la taille de l'arbre d'énumération. MOSEK est utilisé pour résoudre le problème et les résultats sont présentés jusqu'à la taille 20. À chaque itération d'une méthode de plan sécant, une relaxation est résolue et, si un critère d'arrêt n'est pas atteint, une procédure de séparation cherche les coupes violées ou valides à ajouter à la relaxation. Ce mémoire présente un algorithme de plan sécant utilisant les kPPCs pour le problème max-cut. Notre méthode de plan sécant comporte 3 étapes. La première résout la relaxation SDP simple pour fournir une solution optimale initiale. La seconde résout itérativement la relaxation SDP simple à laquelle s'ajoute des inégalités triangulaires. À chaque itération, l'ensemble des inégalités triangulaires est composé, d'une part, de certaines inégalités triangulaires qui sont violées par la solution précédente et, d'autre part, des inégalités triangulaires actives de l'itération précédente. Les inégalités non actives ne sont pas saturées et ne sont par conséquent pas conservées. La troisième étape débute quand l'étape 2 n'apporte plus d'amélioration significative : des kPPCs sont ajoutées au modèle (relaxation SDP simple avec inégalités triangulaires fournies par la dernière itération de l'étape 2). Pour trouver les kPPCs violées, la procédure de séparation résout le problème distance-aupolytope pour les indices générés à partir des inégalités triangulaires violées. Cette méthode donne de meilleurs résultats que la sélection aléatoire des sous-graphes induits pour en tester la violation. En particulier, nous montrons que davantage de kPPCs violées sont trouvées et que la violation est plus grande. Finalement, nous présentons des résultats numériques (pour n = 500 − 1000) montrant que, lorsque l'amélioration de la borne à partir d'inégalités triangulaires est faible, les kPPCs sont encore capables de resserrer la relaxation.