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 wellknown to be NPhard, 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 wellresearched 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 hardtobeat tradeoff 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 offtheshelf SDP algorithms and require highly specialized methods to be addressed. In the last decades, LiftandProject 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\ and \sch's LiftandProject 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 LiftandProject 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 interiorpoint 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 firstorder 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.
On semidefinite liftandproject of combinatorial optimization problems / Battista, Federico.  (2023 Jan 25).
On semidefinite liftandproject of combinatorial optimization problems
BATTISTA, FEDERICO
25/01/2023
Abstract
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 wellknown to be NPhard, 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 wellresearched 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 hardtobeat tradeoff 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 offtheshelf SDP algorithms and require highly specialized methods to be addressed. In the last decades, LiftandProject 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\ and \sch's LiftandProject 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 LiftandProject 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 interiorpoint 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 firstorder 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.File  Dimensione  Formato  

Tesi_dottorato_Battista.pdf
accesso aperto
Note: Tesi completa
Tipologia:
Tesi di dottorato
Licenza:
Creative commons
Dimensione
3.74 MB
Formato
Adobe PDF

3.74 MB  Adobe PDF 
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.