
Pubblicazioni Aperte DIgitali Sapienza >
Scienze statistiche >
RICERCA OPERATIVA >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10805/1598

Title:  The Stable Set Problem: Some Structural Properties and Relaxations 
Authors:  MICHINI, CARLA 
Tutor:  Sassano, Antonio 
Keywords:  stable set problem edge formulation simplex pivot vertex adjacency combinatorial diameter corner relaxation 
Issue Date:  4Jun2012 
Abstract:  Given a graph, the edge formulation of the stable set problem is defined by twovariable constraints, one for each edge, expressing the simple condition that two adjacent nodes cannot belong to a stable set. We study the fractional stable set polytope, i.e. the polytope defined by the linear relaxation of the edge formulation. Even if this polytope is a weak approximation of the stable set polytope, its simple geometrical structure provides deep theoretical insight as well as interesting algorithmic opportunities.
Exploiting a graphic characterization of the bases, we first redefine simplex pivots in terms of simple graphic operations, that turn a given basis into an adjacent one. Between all possible pivots, we characterize degenerate and nondegenerate ones, and we differentiate those leading to an integer or to a fractional vertex. The graphic characterization of bases is crucial to prove another structural property of the fractional stable set polytope, concerning the adjacency of its vertices. In particular, we extend a necessary and sufficient condition due to Chvátal for adjacency of (integer) vertices of the stable set polytope to arbitrary (and possibly fractional) vertices of the fractional stable set polytope. These results lead us to prove that the Hirsch Conjecture is true for the fractional stable set polytope, i.e. the combinatorial diameter of this fractional polytope is at most equal to the number of edges of the given graph. We actually refine this bound in the nonbipartite case by proving a tighter bound, equal to the number of nodes of the graph. We also design a simplexlike algorithm for the stable set problem that relies on the adjacency properties mentioned above. Our algorithm generates only integer solutions without using cutting plane methods. Preliminary results are encouraging but show that cycling can occur, due to the high degree of degeneracy of the polytope. Nevertheless, the perspective of an exact combinatorial method of solution for the stable set problem based on this algorithm seems intriguing, provided that an anticycling rule is embedded in its current design.
The graphic characterization of bases also provides a significant assessment on strength of different corner relaxations for the edge formulation of the Maximum Cardinality Stable Set Problem.
The corner relaxation of a mixedinteger linear program is a central concept in cutting plane theory. In a recent paper Fischetti and Monaci provide an empirical study of the strength of the corner and other related relaxations on benchmark problems. We validate with theoretical arguments the empirical results obtained by Fischetti and Monaci: we give a precise characterization of the bounds given by the corner relaxation and three of its extensions in the special case of the edge formulation of the stable set problem, for which a full description of the corner polyhedron is available. Our theoretical analysis shows that degeneracy plays a major role, as the difference in the bounds given by corner relaxations from two different optimal bases can be significantly large. Therefore, exploiting multiple degenerate bases for cut generation could give better bounds than working with just a single basis.
Finally, a concave reformulation for Set Covering problems is presented, where integrality constraints are dropped and the original linear objective function is replaced by a concave one, penalizing fractional values. For such reformulation, any integer local optimum corresponds to a heuristic solution of the original problem. To determine local optima of our concave reformulation, we apply the FrankWolfe algorithm with a multistart approach. The choice of a suitable parametric concave function allows us to regulate the smoothness of the objective function and to achieve sparseness of the local optimum. When applied to the edge formulation of the stable set problem, additional properties of local optima can be established. Namely, if the parameter of the objective function belongs to a certain range, binary valued variables of the local optimum can be fixed, allowing a reduction of the dimension of the problem. Computational experiments show that the concave heuristic is effective on some difficult benchmark problems. 
URI:  http://hdl.handle.net/10805/1598 
Research interests:  Combinatorial Optimization, Integer Programming, Polyhedral Combinatorics 
Appears in PhD:  RICERCA OPERATIVA

Files in This Item:
File 
Description 
Size  Format 
thesisCarlaMichini.pdf  documento integrale tesi  752.47 kB  Adobe PDF    File del Curriculum Vitae:  CurriculumVitae.pdf   61.16 kB  Adobe PDF 

This item is protected by original copyright

Items in PADIS are protected by copyright, with all rights reserved, unless otherwise indicated.
