Parity polytopes and binarization

Dominik Ermel, Matthias Walter

Research output: Contribution to journalArticleAcademicpeer-review

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 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
JournalDiscrete applied mathematics
Volume272
Early online date26 Apr 2018
DOIs
Publication statusPublished - 15 Jan 2020

    Fingerprint

Keywords

  • Binarization
  • Complete description
  • Extended formulation
  • Parity polytopes
  • Separation algorithm

Cite this