T3: Combinatorial Optimization and the Traveling Salesman Problem

Turno Tarde (14 a 17 horas)

Vašek Chvátal,Canada Research Chair in Combinatorial Optimization, Concordia University, Canadá. (Curso en inglés)

http://www.cs.concordia.ca/~chvatal/

Vašek Chvátal got his Ph.D. in mathematics from University of Waterloo in 1970. Before joining Concordia in 2004, he taught at Stanford, McGill, and Rutgers. His initial research interests were in graph theory (with an emphasis on hamiltonian cycles and later on perfect graphs) and in combinatorics (with an emphasis on extremal problems and on random discrete structures). Then they extended to analysis of algorithms (with an emphasis on cutting-plane proofs) and to operations research. His textbook "Linear Programming" appeared in 1983. In the 1990s, jointly with David Applegate, Robert Bixby, and William Cook, he developed the computer code Concorde for solving the traveling salesman problem; for this work, the team was awarded the Beale-Orchard-Hays Prize for Excellence in Computational Mathematical Programming. In the near future, Vašek Chvátal would like to try his hand at computational neuroscience (with an emphasis on predicting epileptic seizures).

Objetivos del Curso:

Problems that belong to the domain called combinatorial optimization have the objective of minimizing (or maximizing) a prescribed function over a subset of a Euclidean space which is prescribed by an efficient membership-testing oracle and whose elements have some combinatorial meaning. A classic example is the traveling salesman problem, where each instance is specified by an assignment of a weight to each edge of a complete graph and the objective is to find a minimum-weight hamiltonian cycle in this graph.

Methods of combinatorial optimization fall mainly in one of two categories: local search and mathematical programming.  The umbrella of local search comprises heuristics -- simulated annealing, tabu search, genetic algorithms, neural networks -- aimed at quickly finding a near-optimal solution. Starting from such a solution, methods of mathematical programming -- particularly branch-and-cut algorithms -- proceed, often through a lot of hard work, to find a provably optimal solution. The origin of these algorithms is the cutting-plane method, developed by George Dantzig, Ray Fulkerson, and Selmer Johnson in 1954.

In the 1990s, David Applegate, Robert Bixby, Vašek Chvátal, and William Cook wrote the computer code Concorde for solving the traveling salesman problem by branch-and-cut. We will study selected ingredients of Concorde in the general framework of combinatorial optimization.

Programa:

  • What is combinatorial optimization?
  • The Dantzig-Fulkerson-Johnsoncutting-plane method.
  • The template paradigm and its use in Concorde: Subtour cuts and PQ-trees, combs from consecutive ones, combs from dominos, and cuts from blocks and blossoms.
  • Cuts which do not follow the template paradigm: cut metamorphoses and local cuts.
  • General methods used in finding local cuts: delayed column generation, the continued fraction method, Minkowski's theorem, sequential lifting.
  • Managing and solving the linear programming relaxations.
  • Branching.
  • Tour finding.

Requisitos:

  • Knowledge of the simplex method and linear programming duality is a helpful but not a required prerequisite.

Bibliografía:

  • G. Dantzig, R. Fulkerson, and S. Johnson, "Solution of a large-scale traveling-salesman problem", Operations Research 2, 393-410.
  • V.Chvátal, "Linear Programming", W.H.Freeman, New York, 1983.
  • D.Applegate, R.Bixby, V.Chvátal, and W.Cook, "On the solution of traveling salesman problems", Documenta Mathematica Special Volume: Proceedings of the International Congress of Mathematicians (1998),645-656.
  • D.Applegate, R.Bixby, V.Chvátal, and W.Cook, "TSP cuts which do not conform to the template paradigm", in Computational combinatorial optimization: optimal or provably near optimal colutions (Lecture Notes in Computer Science; 2241), Michael Jünger and Denis Naddef, eds., Springer, 2001, pp. 261--303.
  • D.Applegate, R.Bixby, V.Chvátal, and W.Cook, "Implementing the Dantzig-Fulkerson-Johnson Algorithm for Large Traveling Salesman Problems", Mathematical Programming 97 (2003) 91 - 153.
  • Traveling Salesman Problem", http://www.tsp.gatech.edu/