Campuses:

Faster separation of 1-wheel inequalities for stable set<br/><br/> polytopes

Tuesday, July 26, 2005 - 9:30am - 10:15am
EE/CS 3-180
Sven de Vries (TU München)
For the solution of hard integer programs with
branch-and-cut
algorithms it is a necessity to check during the separation
phase for
violated inequalities of the stable set relaxation of the
instances
conflict graph. These conflict graphs turn out to be sparse.
For instance the majority (39/60) of the new and difficult
MIPLIB2003 integer programs contain
large substructures with constraints of type src=http://www.ima.umn.edu/springer/greek/sum.gif>
xi 1
for
binary variables.

A stable set in a graph G=(V,E) is a set of pairwise
nonadjacent
vertices. A common approach for finding a maximum weight
stable set
of G is
to optimize over the convex hull STAB(G) of the incidence
vectors of stable sets; this approach requires
knowledge of strong valid inequalities and algorithms to
separate
them.
We present an O(V2E+V3log V)
separation
algorithm
for the nonsimple 1-wheel inequalities
(Cheng and Cunningham, 1995), which is faster than the
previously known
O(V4) algorithm. In particular this is faster
for
the sparse instances coming from the conflict graphs of
general
integer programs.