Optimization Online


Parity Polytopes and Binarization

Dominik Ermel(dominik.ermel***at***st.ovgu.de)
Matthias Walter(walter***at***or.rwth-aachen.de)

Abstract: We consider generalizations of parity polytopes whose variables, in addition to a parity constraint, satisfy certain ordering constraints. More precisely, the variable domain is partitioned into k contiguous groups, and within each group, we require the variables to be sorted nonincreasingly. Such constraints are used to break symmetry after replacing an integer variable by a sum of binary variables, so-called binarization. We provide extended formulations for such polytopes, derive a complete outer description, and present a separation algorithm for the new constraints. It turns out that applying binarization and only enforcing parity constraints on the new variables is often a bad idea. For our application, an integer programming model for the graphic traveling salesman problem, we observe that parity constraints do not improve the dual bounds, and we provide a theoretical explanation of this effect.

Keywords: binarization, parity, polyhedral description, extended formulation

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Combinatorial Optimization

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


Download: [PDF]

Entry Submitted: 04/04/2018
Entry Accepted: 04/09/2018
Entry Last Modified: 04/04/2018

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