## Invited Session Fri.3.H 2013

#### Friday, 15:15 - 16:45 h, Room: H 2013

**Cluster 11: Integer & mixed-integer programming** [...]

### Symmetry issues in integer programming

**Chair: Volker Kaibel**

**Friday, 15:15 - 15:40 h, Room: H 2013, Talk 1**

**Matteo Fischetti**

Orbital shrinking

**Coauthor: Leo Liberti**

**Abstract:**

Symmetry plays an important role in optimization. The usual approach to cope with symmetry in discrete optimization is to try to eliminate it by introducing artificial symmetry-breaking conditions into the problem, and/or by using an ad-hoc search strategy. In this paper we argue that symmetry is instead a beneficial feature that we should preserve and exploit as much as possible, breaking it only as a last resort. To this end, we outline a new approach, that we call orbital shrinking, where additional integer variables expressing variable sums within each symmetry orbit are introduces and used to encapsulate model symmetry. This leads to a discrete relaxation of the original problem, whose solution yields a bound on its optimal value. Encouraging preliminary computational experiments on the tightness and solution speed of this relaxation are presented.

**Friday, 15:45 - 16:10 h, Room: H 2013, Talk 2**

**Marc E. Pfetsch**

A computational comparison of symmetry handling methods in integer programming

**Coauthor: Thomas Rehn**

**Abstract:**

During the past years several methods to handle symmetries in integer programs have been introduced. This includes isomorphism pruning by Margot, orbital branching by Ostrowski et al., symmetry breaking constraints by Liberti, etc. In this talk we present a computational comparison of these different approaches in the framework SCIP. We discuss implementation issues like symmetry detection and the detection of interesting subgroups of the symmetry group as well as their exploitation during the solution process. The tests are run on the highly symmetric instances of Margot and on the MIPLIB 2010. We discuss the results of these test runs, which, as can be expected, depend on the instances at hand. We also compare two different ways to detect symmetry via graph isomorphism.

**Friday, 16:15 - 16:40 h, Room: H 2013, Talk 3**

**Jim Ostrowski**

Dominance-strengthened symmetry breaking constraints in the unit commitment problem

**Coauthor: Jianhui Wang**

**Abstract:**

Adding symmetry-breaking to a highly symmetric instance of a MILP problem can

reduce the size of the problem's feasible region considerably. The same can be

said for good dominance constraints. In this talk we will examine the impact of

using dominance arguments to strengthen symmetry breaking constraints for the

Unit Commitment (UC) problem. Symmetry is present in (traditional formulations

of) the UC problem when there are several generators of the same type. We show

that by adding dominance strengthened cuts, the number of feasible solutions

that need to be considered only grows polynomially as the number of generators

increases (so long as the number of unique generators is fixed).