Parity polytopes and binarization

DOI10.1016/J.DAM.2018.04.008zbMATH Open1434.90103arXiv1803.10561OpenAlexW2962738415MaRDI QIDQ2283103FDOQ2283103

Authors: Dominik Ermel, Matthias Walter 

Publication date: 30 December 2019

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On defining sets of vertices of the hypercube by linear inequalities
• Title not available (Why is that?)
• 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
• Odd Minimum Cut-Sets and b-Matchings
• Odd Minimum Cut Sets and b-Matchings Revisited
• Cut generation through binarization
• ``Binarize and project to generate cuts for general mixed-integer programs

Cited In (3)

• The parity problem of polymatroids without double circuits
• The graphical traveling salesperson problem has no integer programming formulation in the original space
• \(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)