Optimization Online


On the exact separation of rank inequalities for the maximum stable set problem

Stefano Coniglio(stefano.coniglio***at***gmail.com)
Stefano Gualandi(stefano.gualandi***at***gmail.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 mixed-integer linear program. We then propose a restriction of rank inequalities where the right-hand 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 right-hand 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 right-hand

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 )


Download: [PDF]

Entry Submitted: 08/23/2014
Entry Accepted: 08/23/2014
Entry Last Modified: 08/23/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society