2018/03/28 by Dominik Ermel, Ermel, Dominik, Matthias Walter +1
Computer Science · Mathematics · #90C57 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #G.2.1 #acm:90C57 #cs.DM #math.CO #msc:90C57
paper · pdf · doi:10.48550/arxiv.1803.10561
9 pages, 1 figure, presented at 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization 2017
arxiv created 2018/04/18 · arxiv updated 2018/04/19
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 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.