Parity polytopes and binarization

DOI10.1016/J.DAM.2018.04.008MaRDI QIDQ2283103zbMATHOpenAlexFDO

Authors Dominik Ermel, Matthias Walter

Publication date 30 December 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.10561

zbMATH Keywords

binarizationextended formulationseparation algorithmcomplete descriptionparity polytopes

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Integer programming (90C10) Mixed integer programming (90C11)

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 that $x_{i}geq{x}_{i+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.

Recommendations

• Polytopes associated with symmetry handling
• A Study of Domino-Parity and k-Parity Constraints for the TSP
• Orbitopal fixing
• Symmetries in binary programs. A polyhedral perspective
• Binary clutter inequalities for integer programs

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 1538127 (Why is no real title available?)
• Cut generation through binarization
• Odd Minimum Cut Sets and b-Matchings Revisited
• Odd Minimum Cut-Sets and b-Matchings
• On defining sets of vertices of the hypercube by linear inequalities
• Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
• ``Binarize and project to generate cuts for general mixed-integer programs

Cited in

(3)

• The graphical traveling salesperson problem has no integer programming formulation in the original space
• The parity problem of polymatroids without double circuits
• \(S\)-hypersimplices, pulling triangulations, and monotone paths

This page was built for publication: Parity polytopes and binarization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2283103)