Optimization Online


Reformulations in Mathematical Programming: Symmetry

Leo Liberti(leoliberti***at***gmail.com)

Abstract: If a mathematical program (be it linear or nonlinear) has many symmetric optima, solving it via Branch-and-Bound techniques often yields search trees of disproportionate sizes; thus, finding and exploiting symmetries is an important task. We propose a method for automatically finding the formulation group of any given Mixed-Integer Nonlinear Program, and reformulating the problem so that some symmetric solutions become infeasible. The reformulated problem can then be solved via standard Branch-and-Bound codes such as CPLEX (for linear programs) and {\sc Couenne} (for nonlinear programs). Our computational results include formulation group tables for the MIPLib3, MIPLib2003, GlobalLib and MINLPLib instance libraries, solution tables for some instances in the aforementioned libraries, and a theoretical and computational study of the symmetries of the Kissing Number Problem.

Keywords: symmetry, mixed integer nonlinear programming, branch and bound, kissing number problem

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

Category 2: Global Optimization (Theory )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 12/03/2008
Entry Accepted: 12/03/2008
Entry Last Modified: 12/03/2008

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 Programming Society