Optimization Online


Extended Formulations for Column Constrained Orbitopes

Christopher Hojny(hojny***at***mathematik.tu-darmstadt.de)
Marc E. Pfetsch(pfetsch***at***mathematik.tu-darmstadt.de)
Andreas Schmitt(aschmitt***at***mathematik.tu-darmstadt.de)

Abstract: In the literature, packing and partitioning orbitopes were discussed to handle symmetries that act on variable matrices in certain binary programs. In this paper, we extend this concept by restrictions on the number of 1-entries in each column. We develop extended formulations of the resulting polytopes and present numerical results that show their effect on the LP relaxation of a graph partitioning problem.

Keywords: symmetry, binary programming, extended formulation, disjunctive programming

Category 1: Integer Programming (0-1 Programming )

Citation: TU Darmstadt, Department of Mathematics, Research Group Optimization, Dolivostr. 15, 64293 Darmstadt, June 2017

Download: [PDF]

Entry Submitted: 06/21/2017
Entry Accepted: 06/21/2017
Entry Last Modified: 06/21/2017

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