Optimization Online


Orbital shrinking

Matteo Fischetti(matteo.fischetti***at***unipd.it)
Leo Liberti(leoliberti***at***gmail.com)

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.

Keywords: Mathematical programming, discrete optimization, algebra, symmetry, relaxation, MILP, convex MINLP.

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 09/26/2011
Entry Accepted: 09/26/2011
Entry Last Modified: 09/26/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society