Parity polytopes and binarization

Dominik Ermel, Matthias Walter*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
34 Downloads (Pure)


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 xi≥xi+1 for all relevant i. 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.

Original languageEnglish
Pages (from-to)24-30
Number of pages7
JournalDiscrete applied mathematics
Early online date26 Apr 2018
Publication statusPublished - 15 Jan 2020


  • Binarization
  • Complete description
  • Extended formulation
  • Parity polytopes
  • Separation algorithm
  • UT-Hybrid-D
  • 22/2 OA procedure


Dive into the research topics of 'Parity polytopes and binarization'. Together they form a unique fingerprint.

Cite this