Vendedor Viajero

SIAM REVIEW Vol. 45, No. 1, pp. 116–123

c 2003 Society for Industrial and Applied Mathematics

Teaching Integer Programming Formulations Using the Traveling Salesman Problem∗
G´ bor Pataki† a
Abstract. We designed a simple computational exercise to compare weak and strong integer programming formulations of the traveling salesman problem. Using commercial IP software, and a short (60 linelong) MATLAB code, students can optimally solve instances with up to 70 cities in a few minutes by adding cuts from the stronger formulation to the weaker, but simpler one. Key words. integer programming, traveling salesman problem, subtour elimination constraints, cutting planes AMS subject classifications. 90C10, 90C11, 90C27, 90C57, 90-01, 97D40 PII. S0036144502368551

1. Introduction. 1.1.Integer Programs and Their Formulations. An integer program (IP) is an optimization problem of the form min cT x s.t. x ∈ X, where X = Zn ∩ { x ∈ Rn | Ax ≤ b }, with some matrix A, vector b, and the symbols Zn and Rn denoting the set of integer and real n-vectors, respectively. The polyhedron { x ∈ Rn | Ax ≤ b } is a formulation of the set X. An IP has many formulations; for instance, in Figure 1the solid and dashed lines enclose the same integer points; i.e., the corresponding polyhedra are both formulations of the same set. Given two such polyhedra, P and Q (i.e., P ∩ Zn = Q ∩ Zn ), we say that P is a better, or stronger, formulation, if P Q. (The definitions here are from [9].) One of the most important skills that a practitioner of integer programming must acquire is that of designing astrong formulation for a particular problem. The main component of all commercial IP solvers is a branch-and-bound algorithm that uses the linear programming (LP) relaxation of an IP (i.e., the problem obtained from an IP by discarding the integrality constraints). Hence, a stronger formulation usually can be solved with fewer branch-and-bound nodes; if the tighter LPs are not “much” moretime-consuming, this translates into a smaller overall solution time. Even if the
∗ Received by the editors May 2, 2001; accepted for publication (in revised form) May 28, 2002; published electronically February 3, 2003. Part of this work was done while the author was affiliated with the Department of IE/OR at Columbia University, and was supported by NSF grant DMS 95-27124.http://www.siam.org/journals/sirev/45-1/36855.html † Department of Operations Research, University of North Carolina at Chapel Hill, 212 Smith Building, Chapel Hill, NC 27599-3180 (gabor@unc.edu).

116

TEACHING INTEGER PROGRAMMING USING THE TSP

117

Fig. 1 Two formulations of the same set.

problem cannot be solved to optimality within the available time, a strong formulation provides a good bound on the optimalvalue of the problem. Hence it can also serve as a counterpoint to an effective heuristic, by proving that a solution provided by the latter is close enough to being optimal. 1.2. Exercises to Compare Formulations in Practice. A classroom lecture on comparing weak and strong formulations is best accompanied by an assignment asking students to do a computational comparison. Such a comparison cansimply consist of feeding a strong and a weak formulation of the same problem to an IP solver and comparing the number of branch-and-bound nodes and times required to solve them to optimality. A problem is well suited for the purpose of a comparison if (1) it is relevant in practice, interesting, and easy to understand; (2) the advantages of the strong formulation are not immediately apparent, for someof the following reasons: • the strong formulation uses many more variables and/or constraints; • the weak one can accommodate more versatile objective functions; (3) the weak and strong formulations are easy to generate. Several such problems are (see, e.g., [9]) • facility location problems (with their weak, i.e., the aggregated, and the strong, i.e., the disaggregated formulation); •...