# 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>

x

for

binary variables.

A

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(V

separation

algorithm

for the nonsimple 1-wheel inequalities

(Cheng and Cunningham, 1995), which is faster than the

previously known

O(V

for

the sparse instances coming from the conflict graphs of

general

integer programs.

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>

x

_{i}1for

binary variables.

A

*stable set*in a graph G=(V,E) is a set of pairwisenonadjacent

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(V

^{2}E+V^{3}log V)separation

algorithm

for the nonsimple 1-wheel inequalities

(Cheng and Cunningham, 1995), which is faster than the

previously known

O(V

^{4}) algorithm. In particular this is fasterfor

the sparse instances coming from the conflict graphs of

general

integer programs.