  


On the exact separation of rank inequalities for the maximum stable set problem
Stefano Coniglio(stefano.conigliogmail.com) Abstract: When addressing the maximum stable set problem on a graph G = (V,E), rank inequalities prescribe that, for any subgraph G[U] induced by U ⊆ V , at most as many vertices as the stability number of G[U] can be part of a stable set of G. These inequalities are very general, as many of the valid inequalities known for the problem can be seen as rank inequalities in which G[U] is restricted to a specific topology. In spite of their generality, their exact separation (without introducing topological restrictions) has not yet been investigated, at least to our knowledge. In this work, we first formulate the separation problem of rank inequalities as a bilevel integer program. Starting from it, we derive what we call rounded fractional rank inequalities, a weaker version of rank inequalities which we show to contain clique, odd hole, odd antihole, odd wheel (with unit weights), antiweb, and a (well characterized) subset of web inequalities. We show that these inequalities can be separated exactly by solving a single level mixedinteger linear program. We then propose a restriction of rank inequalities where the righthand side is fixed to a given constant, which we again show to be separated exactly by solving a single level integer linear program. By iteratively increasing the righthand side, the exact separation of the whole family is achieved. Computational results adopting the separation algorithms that we develop show that rounded fractional rank inequalities and rank inequalities with a small, fixed righthand Keywords: Maximum stable set problem, Rank inequalities, Cutting planes, Integer programming, Combinatorial optimization, Bilevel programming Category 1: Integer Programming (Cutting Plane Approaches ) Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Category 3: Combinatorial Optimization (Polyhedra ) Citation: Download: [PDF] Entry Submitted: 08/23/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  