Zurück zu den Preprints des Jahres 2009


2009-20

Orbitopal Fixing

by Kaibel, Volker, Peinhardt, Matthias, Pfetsch, Marc.


Series: 2009-20, Preprints

MSC:
90C10 Integer programming

Abstract:
The topic of this paper are integer programming models in which a subset
of 0/1-variables encode a partitioning of a set of objects into disjoint
subsets. Such models can be surprisingly hard to solve by branch-and-cut
algorithms if the order of the subsets of the partition is irrelevant, since
this kind of symmetry unnecessarily blows up the search tree.

We present a general tool, called orbitopal fixing, for enhancing the
capabilities of branch-and-cut algorithms in solving such symmetric
integer programming models. We devise a linear time algorithm that,
applied at each node of the search tree, removes redundant parts
of the tree produced by the above mentioned symmetry. The method relies
on certain polyhedra, called orbitopes, which have been introduced
in~\cite{KaPf08}. It does, however, not explicitly add inequalities to the model.
Instead, it uses certain fixing rules for variables.
We demonstrate the computational power of
orbitopal fixing at the example of a graph partitioning problem.

Keywords:
symmetry; orbitope; graph partitioning