Optimization Online


New symmetries in mixed-integer linear optimization

Philipp M. Christophel(philipp.christophel***at***sas.com)
Menal Güzelsoy(menal.guzelsoy***at***sas.com)
Imre Pólik(imre.polik***at***gmail.com)

Abstract: We present two novel applications of symmetries for mixed-integer linear programming. First we propose two variants of a new heuristic to improve the objective value of a feasible solution using symmetries. These heuristics can use either the actual permutations or the orbits of the variables to find better feasible solutions. Then we introduce a new class of symmetries for binary MILP problems. Besides the usual permutation of variables, these symmetries can also take the complement of the binary variables. This is useful in situations when two opposite decisions are actually symmetric to each other. We discuss the theory of these symmetries and present a computational method to compute them. Examples are presented to illustrate the usefulness of these techniques.

Keywords: complement, symmetry, heuristics

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

Citation: Technical report

Download: [PDF]

Entry Submitted: 07/28/2014
Entry Accepted: 07/28/2014
Entry Last Modified: 07/28/2014

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