Efficient separation routines for the symmetric traveling salesman problem I: general tools and comb separation |
| |
| Authors: | Denis Naddef Stefan Thienel |
| |
| Affiliation: | Laboratoire Informatique et Distribution-IMAG, Institut National Polytechnique de Grenoble, e-mail: denis.naddef@imag.fr, FR
Institut für Informatik, Universit?t zu K?ln, e-mail: stefan.thienel@sdm.de, DE
|
| |
| Abstract: | This is the first of a series of two papers dedicated to efficient separation heuristics for violated inequalities in the context of solving to optimality instances of the Traveling Salesman Problem via branch-and-cut. In this paper we give the basic ideas behind these heuristics and design heuristics for comb separation. The second paper will deal with more complex inequalities such as Clique Tree, Star or Path and Ladder inequalities and give computational results. Received: September 1999 / Accepted: August 2001?Published online February 14, 2002 |
| |
| Keywords: | Mathematics Subject Classification (2000): 90C57 |
| 本文献已被 SpringerLink 等数据库收录！ |
