Thesis title: On Semidefinite Lift-and-Project relaxations of Combinatorial Optimization Problems
Finding the stability and the chromatic number of a graph are two among the fundamental problems in combinatorial optimization. Given a graph, the first calls for a stable set of maximum cardinality, i.e. a subset of vertices such that no two are adjacent; the latter asks for a partition of the nodes into the minimum number of stable sets (i.e. colors).
Both the stable set and graph coloring problems are well-known to be NP-hard, hence no
polynomial time algorithm to solve them exactly is expected to exists unless P=NP. Thus, the study of strong relaxations of these two problems is a well-researched topic. In particular, the Lov\'asz theta function $\theta(G)$ provides at the same time a good upper bound on the stability number of a graph $G$ and a lower bound on the chromatic number of its complement. It can be computed in polynomial time by solving a semidefinite program, which in addition turns often out to be fairly tractable in practice. As a consequence, $\theta(G)$ achieves a hard-to-beat trade-off between computational effort and strength of the bound. Hierarchies of relaxations to strengthen $\theta(G)$ both towards the stability and chromatic number have been documented, but in general such improvements come at a heavy computational burden with off-the-shelf SDP algorithms and require highly specialized methods to be addressed.
In the last decades, Lift-and-Project methods have gained a lot of attention, being able to generate strong relaxations for combinatorial optimization problems. In particular, starting from any linear relaxation Lovász and Schrijver's Lift-and-Project framework generates a semidefinite relaxation. Its application to the fractional stable set polytope showed its potential, producing bounds stronger than $\theta(G)$ but in general they come at a nontrivial computational cost.
In this thesis we introduce a new semidefinite relaxation for the stable set problem obtained by the lifting of a more compact linear formulation than the classical one. Then, we characterize some classes of valid inequalities for the stable set polytope which are implied by our proposal. We then discuss how to face the computational burden arising from these semidefinite programs by the employment of a general purpose solver for SDPs.
Despite Lift-and-Project applications have been widely studied on the Stable Set problem, to the best of our knowledge none on the Graph Coloring problem have been presented. We investigate its employment in this problem, showing that the resulting SDP can yield bounds above the fractional chromatic number, a remarkable threshold not so straightforward to cross with semidefinite programming.
Although interior-point methods achieve good accuracy in reasonable time for small and medium size SDPs, their scalability to large instances is often compromised by memory requirements.
On the other hand, Alternating Direction Methods of Multipliers currently represent the most popular first-order alternatives, being suited to scale to much larger semidefinite programs. This of course at some cost in accuracy, that should be correctly addressed when bounding the optimal solution of some combinatorial optimization problem. In this work we focus on an ADMM designed for SDPs in standard form and extend it to deal with inequalities. Moreover, we report different methods to compute a valid bound on the optimal value of the SDP starting from a medium accuracy solution and we discuss the employments of these methodologies within ADMMs.