Christopher Hojny (TU/e)

Possibilities and Limitations of Symmetry Handling Cutting Planes

Branch-and-bound is a well-established tool for solving combinatorial optimization problems. If the combinatorial problem contains symmetric structures (such as symmetric graphs or identical objects), however, branch-and-bound will also explore many symmetric, and thus unnecessary, subproblems during the solving process. To accelerate the solution procedure, a standard technique is to detect symmetries of the problem and to add inequalities (cutting planes) to the problem formulation that prevent the solver from computing symmetric solutions. A common drawback of the inequalities known in the literature is that the cutting planes with the largest symmetry reduction effect are numerically instable, and thus, cannot be used for practical instances.

In this presentation, I will review one class of such cutting planes and show how to derive a set of alternative inequalities with the same symmetry handling effect that are stable numerically. The trade-off for numerical stability is that the class of alternative inequalities is exponentially large, which prevents us from adding all of them to the solver simultaneously. The question arises whether this trade-off is intrinsic to the symmetry handling model or whether there exists a small set of numerically stable inequalities with the symmetry handling effect. I will answer the former affirmatively and provide some pointers to further research directions.

VIDEOSTREAM