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


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


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


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).


  cash advance online . Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.