Volker
Kaibel
Title:
Orbitopal fixing
Abstract:
The topic of this talk 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 permutation of the subsets of the
partition is irrelevant. This kind of symmetry unnecessarily blows up
the branch-and-cut tree.
We present a general tool, called orbitopal fixing, for enhancing the
capabilities of branch-and-cut algorithms in solving this kind of sym-
metric integer programming models. We devise a linear time algorithm
that, applied at each node of the branch-and-cut tree, removes redun-
dant parts of the tree produced by the above mentioned permutations.
The method relies on certain polyhedra, called orbitopes, which we
presented
at last year's Aussois meeting. However, it does not add inequalities
to the
model, and thus, it does not increase the difficulty of solving the
linear
programming relaxations. We demonstrate the computational power of
orbitopal fixing at the example of a graph partitioning problem moti-
vated from frequency planning in mobile telecommunication networks.