The traveling salesman problem. A computational study.

*(English)*Zbl 1130.90036
Princeton Series in Applied Mathematics. Princeton, NJ: Princeton University Press (ISBN 978-0-691-12993-8/hbk). xi, 593 p. (2006).

The book presents the last findings on the traveling salesman problem (TSP). After describing the problem, the basic ideas for solving it are presented. The reader is led to the author’s solution approaches step by step. Several examples and computational results help the reader in better understanding the material. The book mainly consists of four parts which are subdivided into seventeen chapters in total.

Part one of the book consists of four chapters. It introduces the traveling salesman problem and focuses particularly on the cutting plane method of Dantzig et al. Chapter one takes a look at the history of the TSP. Thereby the authors describe several famous problems like the knight’s tour, Mark Twain’s tour in “The Innocents Abroad” or the “33-city contest” of Procter & Gamble in the early 1960s. Furthermore, the authors give a review about some geometric ideas, which were important contributions for solving the TSP. They list some studies of the analysis of experimental results on human and animal TSP-solutions and give an overview of exact as well as heuristic-search algorithms. The chapter finishes with a few words concerning the complexity of TSP. Chapter two motivates the reader by giving some examples of applications of the TSP in logisics, scan chains, data clustering and many other topics. Chapter three introduces the cutting-plane method of Danzig, Fulkerson, and Johnson by presenting their basic idea to solve the 42-city problem using a relaxation of the TSP. Chapter four presents a short history of TSP computation. The authors present methods of resolution like branch-and-bound, dynamic programming, Gomory cuts as well as branch-and-cut.

The second part, including the chapters five to eleven, presents several important methods for finding cutting planes. Chapter five starts with a basic introduction to graph theory, linear programming, the cutting-plane method and the branch-and-cut method. After the fundament for finding cutting planes for the TSP is set, chapter six presents three fast subtour algorithms, as well as one exact method for the subtour separation problem. After that, the chapters seven to nine discuss the use of different heuristic separation approaches. Chapter ten addresses the question how existing cuts may become improved and how they can become “glued” together with new cuts. The second part closes with chapter eleven, which presents a completely different point of view on how to determine the cuts and solve the TSP.

The third part contains chapters twelve to fifteen and familiarises the reader with solving the linear programming problems that results from using the cutting plane-method. Furthermore, several heuristics for finding a tour are presented. Chapter twelve discusses how column generation can be used in order to handle the flow of cuts and edges into and out of the LP relaxations. The thirteenth chapter gives a review about the history of linear programming solvers. Furthermore, it provides several computational results, especially run times for various solver, machines and instances of LP problems. Chapter fourteen presents some important branching rules which are integrated in the Concorde code. Tour-finding is the subject of chapter fifteen. Thereby, several heuristic algorithms were introduced, while some computational results give an impression of their performance.

The last part of the book, consisting of chapters sixteen and seventeen, describes the design of the Concorde code and presents some computational results. The book ends with a short survey of different approaches that may improve the existing algorithms.

Overall, the book contains 593 pages and lists 561 references. It is very well written and clearly structured. Many examples are provided, which help the reader to better understand the presented results. The authors succeed in describing the TSP problem, beginning with its history, and the first approaches, and ending with the state of the art.

Part one of the book consists of four chapters. It introduces the traveling salesman problem and focuses particularly on the cutting plane method of Dantzig et al. Chapter one takes a look at the history of the TSP. Thereby the authors describe several famous problems like the knight’s tour, Mark Twain’s tour in “The Innocents Abroad” or the “33-city contest” of Procter & Gamble in the early 1960s. Furthermore, the authors give a review about some geometric ideas, which were important contributions for solving the TSP. They list some studies of the analysis of experimental results on human and animal TSP-solutions and give an overview of exact as well as heuristic-search algorithms. The chapter finishes with a few words concerning the complexity of TSP. Chapter two motivates the reader by giving some examples of applications of the TSP in logisics, scan chains, data clustering and many other topics. Chapter three introduces the cutting-plane method of Danzig, Fulkerson, and Johnson by presenting their basic idea to solve the 42-city problem using a relaxation of the TSP. Chapter four presents a short history of TSP computation. The authors present methods of resolution like branch-and-bound, dynamic programming, Gomory cuts as well as branch-and-cut.

The second part, including the chapters five to eleven, presents several important methods for finding cutting planes. Chapter five starts with a basic introduction to graph theory, linear programming, the cutting-plane method and the branch-and-cut method. After the fundament for finding cutting planes for the TSP is set, chapter six presents three fast subtour algorithms, as well as one exact method for the subtour separation problem. After that, the chapters seven to nine discuss the use of different heuristic separation approaches. Chapter ten addresses the question how existing cuts may become improved and how they can become “glued” together with new cuts. The second part closes with chapter eleven, which presents a completely different point of view on how to determine the cuts and solve the TSP.

The third part contains chapters twelve to fifteen and familiarises the reader with solving the linear programming problems that results from using the cutting plane-method. Furthermore, several heuristics for finding a tour are presented. Chapter twelve discusses how column generation can be used in order to handle the flow of cuts and edges into and out of the LP relaxations. The thirteenth chapter gives a review about the history of linear programming solvers. Furthermore, it provides several computational results, especially run times for various solver, machines and instances of LP problems. Chapter fourteen presents some important branching rules which are integrated in the Concorde code. Tour-finding is the subject of chapter fifteen. Thereby, several heuristic algorithms were introduced, while some computational results give an impression of their performance.

The last part of the book, consisting of chapters sixteen and seventeen, describes the design of the Concorde code and presents some computational results. The book ends with a short survey of different approaches that may improve the existing algorithms.

Overall, the book contains 593 pages and lists 561 references. It is very well written and clearly structured. Many examples are provided, which help the reader to better understand the presented results. The authors succeed in describing the TSP problem, beginning with its history, and the first approaches, and ending with the state of the art.

Reviewer: Stefan Nickel (Saarbrücken)

##### MSC:

90C27 | Combinatorial optimization |

90C35 | Programming involving graphs or networks |

90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |

90C59 | Approximation methods and heuristics in mathematical programming |

90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |