Robust optimization with interval data <BR>

<P>
Volker Kaibel <BR>
ZIB, Berlin <BR>

<p>
Abstract: <BR>

<p>
It is an often observed phenomenon that certain symmetries may 
severely hamper the solution of integer programming models. This 
happens, e.g., if a large group operates on the set of variables in 
such a way that the objective function is constant along every orbit. 
This not only makes branch-and-bound type algorithms
investigate many equivalent subtrees, but it can also lead to very 
poor linear programming bounds. A classical example is a natural 0/1-
programming model for the vertex coloring problem.

<p>
In this talk, we introduce a new way to deal with such kinds of 
symmetries. The approach is to identify polyhedral regions 
('orbitopes') that cut off all but one point from every orbit. The 
basic paradigm is to do this polyhedral work not for a specific 
problem, but rather to develop a generic tool for large classes of 
integer programming models suffering from such symmetries. We present 
first computational results of our method for the vertex coloring 
problem.

<p>
The talk is based on joint work with Marc Pfetsch (ZIB).