Global Optimization of the Maximum K-Cut Problem

Le problème de la k-coupe maximale (max-k-cut) est un problème de partitionnement de graphes qui est un des représentatifs de la classe des problèmes combinatoires NP-difficiles. Le max-kcut peut être utilisé dans de nombreuses applications industrielles. L'objectif de ce problème est de partitionner l'ensemble des sommets en k parties de telle façon que le poids total des arrêtes coupées soit maximisé. Les méthodes proposées dans la littérature pour résoudre le max-k-cut emploient, généralement, la programmation semidéfinie positive (SDP) associée. En comparaison avec les relaxations de la programmation linéaire (LP), les relaxations SDP sont plus fortes mais les temps de calcul sont plus élevés. Par conséquent, les méthodes basées sur la SDP ne peuvent pas résoudre de gros problèmes. Cette thèse introduit une méthode efficace de branchement et de résolution du problème max-k-cut en utilisant des relaxations SDP et LP renforcées. Cette thèse présente trois approches pour améliorer les solutions du max-k-cut. La première approche se concentre sur l'identification des classes d'inégalités les plus pertinentes des relaxations de max-k-cut. Cette approche consiste en une étude expérimentale de quatre classes d'inégalités de la littérature : clique, general clique, wheel et bicycle wheel. Afin d'inclure ces inégalités dans les formulations, nous utilisons un algorithme de plan coupant (CPA) pour ajouter seulement les inégalités les plus importantes . Ainsi, nous avons conçu plusieurs procédures de séparation pour trouver les violations. Les résultats suggèrent que les inégalités de wheel sont les plus fortes. De plus, l'inclusion de ces inégalités dans le max-k-cut peut améliorer la borne de la SDP de plus de 2%. La deuxième approche introduit les contraintes basées sur formulation SDP pour renforcer la relaxation LP. De plus, le CPA est amélioré en exploitant la technique de terminaison précoce d'une méthode de points intérieurs. Les résultats montrent que la relaxation LP avec les inégalités basées sur la SDP surpasse la relaxation SDP pour de nombreux cas, en particulier pour les instances avec un grand nombre de partitions (k � 7). La troisième approche étudie la méthode d'énumération implicite en se basant sur les résultats des dernières approches. On étudie quatre composantes de la méthode. Tout d'abord, nous présentons quatre méthodes heuristiques pour trouver des solutions réalisables : l'heuristique itérative d'agrégation, l'heuristique d'opérateur multiple, la recherche à voisinages variables, et la procédure de recherche aléatoire adaptative gloutonne. La deuxième procédure analyse les stratégies dichotomiques et polytomiques pour diviser un sous-problème. La troisième composante étudie cinq règles de branchement. Enfin, pour la sélection des noeuds de l'arbre de branchement, nous considérons les stratégies suivantes : meilleur d'abord, profondeur d'abord, et largeur d'abord. Pour chaque stratégie, nous fournissons des tests pour différentes valeurs de k. Les résultats montrent que la méthode exacte proposée est capable de trouver de nombreuses solutions. Chacune de ces trois approches a contribué à la conception d'une méthode efficace pour résoudre le problème du max-k-cut. De plus, les approches proposées peuvent être étendues pour résoudre des problèmes génériques d'optimisation en variables mixtes.

Abstract

In graph theory, the maximum k-cut (max-k-cut) problem is a representative problem of the class of NP-hard combinatorial optimization problems. It arises in many industrial applications and the objective of this problem is to partition vertices of a given graph into at most k partitions such that the total weight of the cut is maximized. The methods proposed in the literature to optimally solve the max-k-cut employ, usually, the associated semidefinite programming (SDP) relaxation in a branch-and-bound framework. In comparison with the linear programming (LP) relaxation, the SDP relaxation is stronger but it suffers from high CPU times. Therefore, methods based on SDP cannot solve large problems. This thesis introduces an efficient branch-and-bound method to solve the max-k-cut problem by using tightened SDP and LP relaxations. This thesis presents three approaches to improve the solutions of the problem. The first approach focuses on identifying relevant classes of inequalities to tighten the relaxations of the max-k-cut. This approach carries out an experimental study of four classes of inequalities from the literature: clique, general clique, wheel and bicycle wheel. In order to include these inequalities, we employ a cutting plane algorithm (CPA) to add only the most important inequalities in practice and we design several separation routines to find violations in a relaxed solution. Computational results suggest that the wheel inequalities are the strongest by far. Moreover, the inclusion of these inequalities in the max-k-cut improves the bound of the SDP formulation by more than 2%. The second approach introduces the SDP-based constraints to strengthen the LP relaxation. Moreover, the CPA is improved by exploiting the early-termination technique of an interior-point method. Computational results show that the LP relaxation with the SDP-based inequalities outperforms the SDP relaxations for many instances, especially for a large number of partitions (k � 7). The third approach investigates the branch-and-bound method using both previous approaches. Four components of the branch-and-bound are considered. First, four heuristic methods are presented to find a feasible solution: the iterative clustering heuristic, the multiple operator heuristic, the variable neighborhood search, and the greedy randomized adaptive search procedure. The second procedure analyzes the dichotomic and polytomic strategies to split a subproblem. The third feature studies five branching rules. Finally, for the node selection, we consider the following strategies: best-first search, depth-first search, and breadth-first search. For each component, we provide computational tests for different values of k. Computational results show that the proposed exact method is able to uncover many solutions. Each one of these three approaches contributed to the design of an efficient method to solve the max-k-cut problem. Moreover, the proposed approaches can be extended to solve generic mixinteger SDP problems.