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.

Abstract

This thesis introduces a new family of cuts called k-projection polytope constraints (kPPCs)that can be used to solve certain binary quadratic problems. Specifically those problems that satisfy a projection property in which feasible solutions on an induced subgraph have the same structure as feasible solutions on the full graph, such as the max-cut problem and the stable set problem. Typically cuts (also called valid inequalities) are inequalities, however kPPCs differ as they are a set of equalities. Furthermore they can be defined for a single induced subgraph or a set of induced subgraphs and are used to tighten semidefinite programming (SDP) relaxations. Three aspects of kPPCs are examined in this thesis: a hierarchy that converges to an exact formulation, a formulation to find the most violated kPPC and a practical implementation of a cutting plane algorithm using kPPCs that improves the upper bound (of a maximization problem) for the max-cut problem. The SDP relaxation with kPPCs forms a hierarchy. The kth level of the hierarchy is the SDP relaxation with kPPCs for all induced subgraphs of size k. As k increases, the strength of the relaxation also increases since CUTk ⊆ CUTk+1 where CUTk is the cut polytope of size k. At the nth level the formulation is no longer a relaxation and defines the original problem, CUTn, exactly. There are n/K unique induced subgraphs for a graph with n vertices. Therefore explicitly producing the levels of the hierarchy is only possible for small examples. However the strength of the hierarchy of kPPCs is that the positive semidefinite matrix variable in the SDP relaxation does not grow in size as the level is increased. This is in contrast to other hierarchies including the Lasserre hierarchy. For a given induced subgraph I, an optimization model (denoted distance-to-polytope) is presented to determine if the optimal solution to an SDP relaxation violates the kPPC for I and, if so, to quantify the violation. The distance-to-polytope model has a quadratic objective function, linear constraints and solves quickly. The optimal solution is the euclidean distance between the principal minor of the optimal solution to the relaxation (X*I ) and the cut polytope (CUT|I|). If the distance equals zero then including the kPPC for I in the SDP relaxation will not tighten the bound. If the distance is strictly greater than zero then the kPPC for I is not satisfied by the current solution. Therefore including it in the SDP relaxation will change the current solution X* (although a strict improvement in the bound is not guaranteed). The maximally violated valid inequality problem (MVVIP) determines the valid inequality from a family of cuts that is most violated. This thesis examines this problem for kPPCs. Specifically we present a mixed-binary second order cone optimization model that, for a given k, finds the kPPC that is furthest from the cut polytope. The inner problem is the distance-to-polytope model. The outer problem includes binary variables that consider all induced subgraphs of size k. Bilevel problems are inherently hard to solve. A reformulation is presented that changes the bilevel model into an equivalent single level second order cone problem. The reformulation uses techniques such as KKT conditions, disjunctive constraints and the duality gap. Moreover we show how to strengthen the single level model by including symmetry breaking constraints and including additional binary variables that reduce the size of the enumeration tree. MOSEK is used to solve the problem and results are presented up to size 20. At each iteration of a cutting plane method a relaxation is solved and if a stopping criteria is not met a separation procedure looks for violated and valid cuts to add to the relaxation. This thesis presents a cutting plane algorithm using kPPCs for the max-cut problem. There are 3 stages in our cutting plane method. The first solves the basic SDP relaxation to give an initial optimal solution. The second stage iteratively solves the basic SDP relaxation plus some triangle inequalities. At each iteration the set of triangle inequalities is composed of some triangle inequalities that are violated by the previous solution and the triangle inequalities from the previous iteration that are active. The non-active inequalities are not binding and therefore are not kept. When there are no more violated triangle inequalities (or the improvement has stalled) we begin the third stage in which kPPCs are added to the model (basic SDP relaxation plus triangle inequalities from the last iteration of stage 2). The separation procedure to find violated kPPCs solves the distance-to-polytope problem for indices generated from violated triangle inequalities. Compared to randomly selecting induced subgraphs to test for violation, generating them from the indices used in triangle inequalities gives better results. Specifically we show that more violated kPPCs are found and that the amount of violation is larger. Finally we examine dense graphs of size 500 to 1000 and present computational results showing that kPPCs are able to improve the bound even after triangle inequalities can no longer tighten the relaxation.