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