Generalized domino-parity inequalities for the symmetric traveling salesman problem

Generalized domino-parity inequalities for the symmetric traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20104595
Volume: 35
Issue: 2
Start Page Number: 479
End Page Number: 493
Publication Date: May 2010
Journal: Mathematics of Operations Research
Authors: , ,
Abstract:

We extend the work of Letchford (2000) by introducing a new class of valid inequalities for the traveling salesman problem, called the generalized domino-parity (GDP) constraints. Just as Letchford's domino-parity constraints generalize comb inequalities, GDP constraints generalize the most well-known multiple-handle constraints, including clique-tree, bipartition, path, and star inequalities. Furthermore, we show that a subset of GDP constraints containing all of the clique-tree inequalities can be separated in polynomial time, provided that the support graph G * is planar, and provided that we bound the number of handles by a fixed constant h.

Reviews

Required fields are marked *. Your email address will not be published.