Generalized domino-parity inequalities for the symmetric traveling salesman problem

William J. Cook, Daniel G. Espinoza, Marcos Goycoolea

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

1 Cita (Scopus)

Resumen

We extend the work of Letchford [Letchford, A. N. 2000. Separating a superclass of comb inequalities in planar graphs. Math. Oper. Res. 25 443-454] 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.

Idioma originalInglés
Páginas (desde-hasta)479-493
Número de páginas15
PublicaciónMathematics of Operations Research
Volumen35
N.º2
DOI
EstadoPublicada - may. 2010

Huella

Profundice en los temas de investigación de 'Generalized domino-parity inequalities for the symmetric traveling salesman problem'. En conjunto forman una huella única.

Citar esto