## 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 x_{i}≥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.

Original language | English |
---|---|

Pages (from-to) | 24-30 |

Number of pages | 7 |

Journal | Discrete applied mathematics |

Volume | 272 |

Early online date | 26 Apr 2018 |

DOIs | |

Publication status | Published - 15 Jan 2020 |

## Keywords

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