LEE & RAFFENSPERGER Using AMPL for teaching the TSP Using AMPL for teaching the TSP Jon Lee Ibm T.J. Watson Research Center P.O.Box 218, Yorktown Heights, NY10598 USA [email protected] John F. Raffensperger Dept. ofManagement, Private Bag 4800 University ofCanterbury, Christchurch, New Zealand [email protected] Abstract In this paper, we discuss the use of AMPL in teaching students about the traveling salesman problem (TSP). The paper gives suggestions for pedagogical devices, homework assignments and exams, PowerPoint presen- tations, and a convenient package of AMPL models and scripts. The AMPL files include different formulations for the TSP, its relaxations, scripts for its solution, and - particularly useful in class - scripts for visualization of those solutions using SVG. We have a special focus on visualization, to provide convenient ways for students to view and report their solutions. We observe that the TSP is such a classical O.R. problem, that it can play a central role in an undergraduate course about integer programming. 1. Why teach the TSP? provide convenient ways for students to view and re- port their solutions. The TSP lends itself well to graphical output, and students find this immensely This paper describes our experience in teaching O.R. helpful for learning and for model and algorithm de- students about the traveling salesman problem (TSP), bugging. Furthermore, the lecturer can require that as part of advanced courses in math programming, students turn in a graphical print-out of the tour, thus for third year, fourth year, and masters level courses. allowing some determination of solution quality at a The TSP remains a very important problem. Though glance. it is very well studied, it continues to tantalize re- searchers. Nothing humbles a graduate student so Computationally difficult problems are sometimes a quickly as a brutally difficult problem, and the TSP is source of pedagogical challenge. A model instance perhaps foremost in that category. that is too small does not give the right impression of computational complexity to a student. On the other The TSP leads into many other related areas of O.R., hand, student versions of solvers are usually too small including integer programming and cutting planes, to allow solution of large model instances. One solu- approximation algorithms, Lagrangean relaxation and tion to this dilemma is programming ability. Lecturers the subgradient method, and various heuristic ap- whose students have good programming skills have proaches (such as greedy and k-opt). The TSP and its an advantage in teaching the TSP. Unfortunately, un- variations, such as multiple vehicles, time windows, dergraduate students in business have a widespread tour length constraints, have enormous real-world lack of programming skills. Only recently has the applicability. Because of its importance, its ease in University of Canterbury added a modest program- description, its many applications, and its historical ming requirement for third-year courses in operations inspiration for countless algorithms, the TSP will research; it is still too early to see whether this new continue to be an important part of teaching integer requirement will pay off. The students' lack of program- programming and combinatorial optimization. ming skill puts a greater burden on the lecturer to ex- plain algorithms in more detail and to provide canned This paper's contributions include suggestions for tools. pedagogical devices, homework assignments and ex- ams, and a convenient package of AMPL models and scripts. We have a special focus on visualization, to INFORMS Transactions on Education 7:1(37-69) 37 © INFORMS ISSN: 1532-0545 LEE & RAFFENSPERGER Using AMPL for teaching the TSP Because it does not require programming and because a C++ class library), GAMS(4), Maple(5), Mathematica(6) many students already have some familiarity with it, , the optimization tools in Matlab(7), ZIMPL(8) (open the spreadsheet bears some consideration, especially source), and, of course, the standard programming to solve small problems in first or second year courses, languages. We have chosen AMPL primarily for its and in MBA programs. We use Excel and What'sBest(1) scripting ability, but also for its low cost, its easy links for such courses; students are required to solve a 30- to many solvers (including open-source solvers such city TSP, starting with the assignment problem, and as Cbc(9)), and its popularity. then manually add subtour-breaking constraints and binary integrality. This exercise is extremely effective Perhaps the most interesting AMPL alternative is the in conveying the problem's difficulty as well as hinting open-source Gnu LP Kit(10), with the useful LP_Solve at some of the key elements that can be effectively IDE(11)(see also Introduction to lp_solve 5.5.0.9(12)). In employed to solve large instances. fact, these are not really alternatives, but overlapping programs, because AMPL can call LP_Solve(13), and Unfortunately, the spreadsheet has several drawbacks because the Gnu LP Kit language is a subset of AMPL. for solving the TSP, and for teaching students about Though LP_Solve IDE cannot run AMPL scripts, it has it. The spreadsheet does not scale to larger problem a surprisingly nice interface and can solve many AMPL instances easily. Creating algorithms (such as adding models. LP_Solve IDE has the remarkable ability to subtour-breaking constraints) is unnatural, awkward, convert models into different formats (e.g. it can con- and time consuming, so the spreadsheet does not lend vert MPS(14)to LP-FML(15), among others). itself to exploring advanced techniques of integer programming. And Excel has no convenient tools to For editing AMPL, one alternative is AMPL Studio(16) display network graphs (not to be confused with , which we have not tested. Some popular text editors charts), as each arc must be a new series. We have have basic syntax highlighting, and this is the path we spent some time coding Visual Basic macros to pro- have taken, partly for its low cost. In this paper, we duce visualizations within Excel, only to find that these give directions and help files for using AMPL with the macros are difficult to write, clumsy, and unsatisfacto- open-source editor Scite(17). ry. In contrast to spreadsheets, algebraic modeling languages provide an easy means for making use of While using AMPL feels like programming to students, integer linear programming methods for combinatorial many AMPL models do not require scripts, and the optimization problems. programming overhead associated with AMPL scripts is less than with Visual Basic or Java. We have found We have chosen to use the proprietary modeling lan- that when students are given some reasonable initial guage AMPL, which has scripting capability. Useful help in AMPL in a workshop, including some scripts alternatives to AMPL(2)include FLOPC++ (3)(an open to get them started, the programming demands are source algebraic modeling language implemented as modest. We have no empirical data regarding the ef- (1) http://www.lindo.com/ (2) http://www.ampl.com/ (3) http://www.coin-or.org/ (4) http://www.gams.com/ (5) http://www.maplesoft.com/ (6) http://www.wolfram.com/ (7) http://www.mathworks.com/ (8) http://www.zib.de/koch/zimpl/ (9) http://www.coin-or.org/ (10)http://www.gnu.org/software/glpk/glpk.html (11)http://www.progdigy.com/ (12)http://lpsolve.sourceforge.net/5.5/Intro.htm (13)http://lpsolve.sourceforge.net/ (14)http://en.wikipedia.org/wiki/MPS_(format) (15)http://gsbkip.chicagogsb.edu/fml/fml.html (16)http://www.optirisk-systems.com/Default.aspx (17)http://www.scintilla.org/ INFORMS Transactions on Education 7:1(37-69) 38 © INFORMS ISSN: 1532-0545 LEE & RAFFENSPERGER Using AMPL for teaching the TSP fectiveness of our materials. However, based on stu- a couple pages. Wagner's (1975) classic text gives a dents' look of relief when they get their first AMPL branch and bound algorithm. Hillier & Lieberman model working, the speed with which they can get the (2001) has, surprisingly, nothing on the TSP. Ragsdale basic algorithms going, and on the overall quality of (2004) gives one example with the heuristic in Frontline their work, the workshop approach is clearly positive System's Premium Solver for Excel. Lawrence & and worthwhile. Students who cannot write AMPL Pasternack (1998) give a similarly brief example, with scripts can modify them and learn from that, while a branch and bound algorithm in a supplement on a learning about the TSP, and thereby eventually learn CD-ROM. Winston's (2004) discussion of the TSP in- to write their own AMPL models and scripts. Of cludes a dynamic program (aimed at very small in- course, AMPL models are the first step, but this natu- stances), a branch and bound example, a brief discus- rally leads to the harder step of writing AMPL scripts, sion about heuristics, and a loose integer programming and this can potentally lead to real programming. formulation. We currently use Winston's text, but lib- erally add to the material. The AMPL code that we provide does not usually in- corporate theoretically-efficient algorithms. Except for We feel that the TSP is such a classical problem, per- the minimum spanning tree and the 1-tree, the sub- haps theclassical O.R. integer program, that it can play problems are modeled as linear or integer linear pro- a central role in an undergraduate course about integer grams, and AMPL then accesses a general linear pro- programming, even in a school of business. Yet the gramming or integer linear programming code. undergraduate textbooks do not seem to do it justice. We have found just one article written specifically for The outline of this paper is as follows. First, we discuss teaching the TSP to undergraduates. Pataki's (2003) other teaching materials for the TSP. Second, we give excellent paper covers the relative tightness of different a syllabus, with suggested software, lectures and tuto- formulations, using Matlab. rials, a homework assignment, exam questions, and describe the relevant AMPL scripts and data. Third, Specifically for AMPL, Fourer, Gay & Kernighan (2003) we give some further ideas to expand the material is excellent and authoritative, but much more than beyond what we currently teach, along with additional students need for one course; by all means the book AMPL models and scripts. We conclude with a listing should be available to students as a reference. of internet resources for the TSP. 3. TSP Syllabus 2. Literature review Here, we describe the software required and give our Lawler et al (1985) and Reinelt (1994) are, of course, course material on the TSP. The course material is excellent texts on the TSP. These books thoroughly comprised of three lectures, two tutorials, homework cover branch and bound, cutting planes, subgradient problems, and exam problems. optimization, a thorough review of different relax- ations, and many important heuristics. Similarly, 3.1. Software required Nemhauser & Wolsey (1988) has quite rich material on the TSP, and encapsulates it well. Such textbooks The student version of AMPL with CPLEX may be are too advanced for our students in business, who do downloaded from AMPL website(18). In fact, we inten- not have advanced skills in math or computer program- tionally avoid making a more powerful solver available ming. to students, as we have found that the homework is more compelling with the limited version. Students Several classic textbooks that are currently used at the are still free to try to find a larger solver on their own, undergraduate level either do not mention the TSP at but few ever do so. all, or contain a shallow introduction to the subject. To mention a few, Dantzig's (1963) classic text on linear programming gives three different formulations over (18)http://www.ampl.com/ INFORMS Transactions on Education 7:1(37-69) 39 © INFORMS ISSN: 1532-0545 LEE & RAFFENSPERGER Using AMPL for teaching the TSP If you wish to solve models, but not use scripts, we • The user can start AMPL with the current run file, also suggest the LP_Solve IDE(19). It has a nice interface simply by pressing the F5 key. AMPL runs in a and can read a subset of AMPL's language. The solver side panel. is not limited in the number of variables or constraints, • Scite allows infinite undo, and many other features. but is much slower than CPLEX. More details on installing the files for Scite are provid- SVG viewer. To see the graphical output from the ed in section 4.2. scripts, you should install an SVG viewer, and we highly recommend this approach. You can get a free The amplhelp.html(29) file has roughly eight pages of viewer from Adobe.com(20). The graphical output is beginner-level and reference material for AMPL. It displayed in scalable vector graphics (SVG)(21). From includes a section on getting started with AMPL, basic the website of the World Wide Web Consortium, "SVG syntax, descriptions of some important AMPL words is a language for describing two-dimensional graphics and commands, commonly used options and functions, and graphical applications in XML." Almost all web and a list of frequently-asked questions. We recom- browsers can display SVG natively or with an add-in. mend that the lecturer using these materials modify The file format is plain text, and easy to create with a this help file for the local requirements as needed. script. For example, here is the minimum spanning tree for 1,000 random points(22)on the Euclidean plane, The included AMPL models and scripts. These are as intermediate output from the Christofides heuristic. organized in their own directories, with a separate directory for data. This encourages students to think Scite. For editing AMPL files, we prefer the open- about modeling in an object-oriented way, to keep the source cross-platform Scite, downloadable from the model as generic as possible, and separate from the Scintilla website(23). This editor is highly configurable data. for various languages via properties files. We discov- ered a rudimentary AMPL properties file for Scite in The scripts and models have, for the most part, uni- Italian(24), and have modified and extended it extensive- form data formats and uniform definitions for sets, ly (ampl.api(25), ampl.properties(26), SciTEGlobal. variables, and parameters. For example, "param N;" properties(27)). is used in all models to define the number of nodes, and "Tourlength" is the name of every objective, even • Scite shows syntax coloring, block indenting, block though some will not produce tours. This uniformity commenting, and section folding. has a couple of advantages, the primary one being that • Scite can recognize AMPL keywords for statement we can use a single script to produce the SVG output completion with the tab key. graph, and a secondary advantage being that students become accustomed to the notation more quickly. • Scite displays in-line pop-up help for AMPL functions such as "first(x)". 3.2. Lectures and tutorials • With our attached amplhelp.html(28) file, Scite provides context-sensitive help for AMPL. Lecture 1. Description & history of the TSP. Some formulations.PowerPoint presentation(30) (19)http://www.progdigy.com/ (20)http://www.adobe.com/svg (21)http://www.w3.org/Graphics/SVG/ (22)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/Christofides/1000points_mst.svg (23)http://scintilla.sourceforge.net/SciTEDownload.html (24)http://naufraghi.free.fr/informatica/ampl_scintilla.php (25)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/scite/ampl.api (26)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/scite/ampl.properties (27)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/scite/SciTEGlobal.properties (28)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/scite/amplhelp.html (29)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/scite/amplhelp.html (30)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/PowerPoint/01_Formulations_for_the_TSP_with_AMPL.ppt INFORMS Transactions on Education 7:1(37-69) 40 © INFORMS ISSN: 1532-0545 LEE & RAFFENSPERGER Using AMPL for teaching the TSP In the first lecture, we first describe the problem as lecture notes for testing. In some cases, we also show simply as possible: drive a car via ncities, minimizing the expanded model for further clarification. travel distance. We then follow this with some history, especially the seminal Dantzig, Fulkerson & Johnson Throughout, we follow a careful format for models, (1954) paper and formulation, with its key ideas of first giving the indices, the parameters, the decision branch and bound and IP cuts. We discuss the difficul- variables, the model, and an explanation of each con- ty of the TSP, touching on complexity theory. We also straint set using "NPS format" (Brown 2004), due to mention Concorde (Applegate, Bixby, Chvatal & Cook its invention and use at the O.R. Department of the 1998), so students realize how far the research has Naval Postgraduate School(39). (For a published exam- come. ple of NPS format, see Baker, Morton, Rosenthal, & Williams 2002.) To give students a mnemonic, we call Following this introduction, the remainder of the lec- this IPDME format (i.e., Indices, Parameters, Decision ture covers different formulations related to the TSP, variables, Model, Explanation of constraints). This most with their AMPL formulations and solutions. format has several advantages over a less formal ap- proach. The format requires the author to write out (Note: if the files do not open on click, consider setting formulations in a methodical and uniform way, mak- the ".mod" and ".run" file extensions to open with your ing sure that every term of the model is explained, and favorite text editor.) encouraging the use of a unique meaning for each term. The format gives the reader a convenient direc- • the assignment problem (assignment.mod(31), as- tory of all symbols. The format leads naturally to an signment.run(32)), algebraic modeling language, as indices become sets, and the rest follows analogously. We encourage edu- • the Miller-Tucker-Zemlin model (MTZ.mod(33), cators and editors to standardize on this format. MTZ.run(34)), • the symmetric TSP, For example, here is the classic Dantzig-Fulkerson- Johnson (DFJ) formulation, in IPDME format. • the Svestka flow formulation (Svestka.mod(35), Svestka.run(36)), Indices: i, jcity. • and the Danztig steps formulation with O(n3) variables (Dantzig-steps.mod(37), Dantzig- Parameters: n = number of cities; c = cost to travel ij steps.run(38)). from city ito city j. The algebraic formulations for these are in the Power- Decision variables: x = 1 if the salesman should travel ij Point presentation, and will not be repeated here. between cities iand j, else 0. Generally, we show the algebraic form and the AMPL model directly in the slides (which are printed and n 1. Model DFJ: min ∑ i ∑ c x , given to students), so the AMPL formulation itself is =1 j:j>i ij ij used in the lecture. This gets students accustomed to 2. ∑ (x + x ) = 2 for all i=1,...,n. seeing AMPL formulations, which helps them when j:j>i ij ji it comes time to write their own. It allows them to ask 3. ∑ ∈ x ≤ |S| - 1, for every subset S. i,j S ij questions in class about AMPL syntax. Further, if they wish, they can copy the examples straight from the 4. ∈ x {0, 1} for all i, j:j>i. ij (31)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/assignment/assignment.mod (32)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/assignment/assignment.run (33)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/MTZ/MTZ.mod (34)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/MTZ/MTZ.run (35)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/Svestka/Svestka.mod (36)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/Svestka/Svestka.run (37)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/Dantzig-steps/Dantzig-steps.mod (38)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/Dantzig-steps/Dantzig-steps.run (39)http://www.nps.navy.mil/or/ INFORMS Transactions on Education 7:1(37-69) 41 © INFORMS ISSN: 1532-0545 LEE & RAFFENSPERGER Using AMPL for teaching the TSP Explanation: as there are only n variables but O(n2) pairwise dis- tances. So it is a useful exercise in modeling, to work 1. Minimize total distance traveled. one's way to the inevitably fruitful idea of using binary variables to select edges for a tour. 2. Each city must have degree 2, i.e., must be entered and departed. Tutorial 1. Intro to AMPL, and two key relaxations 3. No subset of cities S consist of a tour, unless that of the TSP. subset has all the cities. The goal of this tutorial is to give students a quick 4. The salesman cannot split his travel between cities. hands-on success with AMPL, and to teach two key relaxations of the TSP, in a workshop approach. Please We write algebraic models in plain text (rather than note that we assume that the lecturer is familiar with Equation Editor or images from LaTeX) using text AMPL. Some instructions for running these files are fonts, subscripts, and superscripts carefully. This al- given here and further information is given in ampl- lows algebraic models to be copied more easily be- help.html(40)but the authoritative discussion on AMPL tween programs, animated in PowerPoint, and edited is Fourer, Gay & Kernighan (2003). in HTML. Before the tutorial starts: While familiar to the O.R. teacher and researcher, the summations in model DFJ can be quite a challenge to • students should be aware of the requirements for students. We suggest taking a little time to explain Homework 1, so they are thinking about how to how the summations work, and explain that the verti- solve it; cal bars on the set, |S|, mean the cardinality of the set, like a spreadsheet's Count() function. • the lab computers should have Scite, AMPL, CPLEX, and an SVG viewer installed. Part of understanding the model is understanding the solution. Students sometimes have difficulty making The lab should have a chalkboard. At the beginning sense of the model until they understand the form of of the tutorial, the algebraic and the AMPL formula- the decision variables. Thus, we use a uniform example tions for the assignment (assignment.mod(41), assign- for all formulations, and show the solution for each ment.run(42)), and 2-matching problems (2match- formulation. A tour can be encoded in different ways, ing.mod(43), 2matching.run(44)), are put on the board. and it is easy to forget that the IP edge formulation is Do not give the files on disk, but do give students the not immediate for a newcomer. Without any guidance, complete AMPL formulation either on paper or on the a student may suggest making a solution vector be chalkboard. Remind students to end commands with simply a permutation of the integers 1,...,n. It is instruc- a semicolon. By giving students an example straight tive to pursue this direction, exploring the difficulties off, they will start to catch on to AMPL's syntax. Give of trying to write down an IP formulation from these the model to students without integrality, and let stu- variables. The first issue that one encounters is the dents discover for themselves the need for integrality. difficulty of expressing the "all-different" constraint that the values of each of the n variables should be Students should copy the AMPL formulations into a distinct. For example, for n=3, we see that 1,2,3 and text editor, creating their own files, and running AMPL 3,2,1 are both valid solutions. Their midpoint 2,2,2 is as they are ready. By requiring students to type in two on the convex hull and is therefore feasible in any LP simple models, they are forced to engage with AMPL, formulation based on these variables. But it is infeasi- and make it work, at a time when they can get imme- ble to the IP. Furthermore, it is not possible to formu- diate help. The concept of the AMPL run file is taught, late the objective as a linear function in these variables, and students put it to use. Separation of model, script, (40)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/scite/amplhelp.html (41)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/assignment/assignment.mod (42)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/assignment/assignment.run (43)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/2matching/2matching.mod (44)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/2matching/2matching.run INFORMS Transactions on Education 7:1(37-69) 42 © INFORMS ISSN: 1532-0545 LEE & RAFFENSPERGER Using AMPL for teaching the TSP and data then begins to make sense, especially as they gressing, simply by refreshing the browser. Copying realize that changing from the tutorial example to the the image to a word processing program is convenient. homework set involves changing only the data file. The images are valuable for teaching, and are also This contrasts with the need to rewrite the entire conveniently copied to presentation software such as model, as would be required with Lindo. PowerPoint. The models can be run either through the Scite inter- Given sufficient time, students may be given AMPL face or at the AMPL command prompt. scripts for the minimum spanning tree (prims.run(46) or kruskal.run(47), originally developed by Olinick • To run a script in AMPL through the Scite inter- (2006). Alternatively, the minimum spanning tree may face, the user simply opens the script (usually a be covered in a later tutorial, after the material is pre- ".run" file) in Scite, and presses the F5 function key. sented during the lecture. AMPL then runs in a side panel. Note that if you have a model file open without a "solve" command, The workshop approach has multiple benefits, as im- AMPL will read the model, but not solve it because mediate help can be given to those students who have it has not received the "solve" command. difficulty starting and running AMPL. Points of syntax can be addressed immediately, and students get a • To run a script at the AMPL command prompt, quick positive result, with a problem that is easy click Start, Run, type ampl in the dialog and press computationally. Key AMPL commands, such as "re- enter. This opens an AMPL command window. set", "display", and "expand", are explained and imme- To run the 2matching.run script, at the "ampl:" diately put to use. Sometimes, students become suffi- prompt, type "run 2matching.run;", and press en- ciently confident and enthused that they want to at- ter. In the command window, they will need to tempt the homework assignment immediately. enter the resetcommand to clear AMPL's memory. ("Reset" is not needed if they use Scite as the inter- Provision of this one-hour workshop has alleviated a face.) Remind them notto reset before using "dis- host of problems in using AMPL. Students come up play" to see results. Explain that when they are to speed much more quickly compared to simply being frequently rerunning a script, they may want to given a sheet of instructions. put "reset;" at the end of the script. Lecture 2. Relaxations and solution methods.Power- After students get the two models running, they are Point presentation(48) given access to the script (makesvg.run(45)) which produces the SVG graphical output, and shown how Following Lecture 1's introduction to TSP formula- to call the script from their existing run files. This visu- tions, Lecture 2 introduces some solution methods. alization gives them a powerful and immediate indi- We first present the assignment problem with branch cation as to whether their model is correct, and how and bound, using an example from Winston (2003, pp. it is related to the TSP. This would be the time to ex- 530-534), then give the 1-tree, with Prim's and plain the commands filenamecommand, which is used Kruskal's algorithms. This information is easy to ex- to give AMPL a list of commands from a file. plain, and tends to be understood easily, partly be- cause of the highly graphical nature of the information, SVG can be viewed in a web browser with a free add- and as it is given just a few weeks following more in (such as Adobe's SVG Viewer, general IP cuts and branch and bound. http://www.adobe.com/svg). We have carefully written all models and scripts to have uniform variable and The final section of this lecture covers the Held & Karp set definitions, so they all will work with makesvg.run. 1-tree subgradient optimization algorithm. Many stu- For algorithms such as the 1-tree subgradient optimiza- dents get completely thrown at this point, as the lecture tion, the graph can be viewed as the algorithm is pro- has moved from tree, to 1-tree, to an entirely new al- (45)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/makesvg.run (46)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/Prims/prims.run (47)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/kruskal/kruskal.run (48)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/PowerPoint/02_Solution_methods_for_the_TSP.ppt INFORMS Transactions on Education 7:1(37-69) 43 © INFORMS ISSN: 1532-0545 LEE & RAFFENSPERGER Using AMPL for teaching the TSP gorithm. Considerable patience is required. The sub- The presentation does not cover all the various AMPL gradient optimization material is presented in more scripts we have for the DFJ model, but the lecturer detail in Tutorial 2. may want to discuss them with students. These in- clude, in increasing order of sophistication: Tutorial 2. Subgradient optimization. PowerPoint presentation(49) • DFJ_all_subtours.mod(54) and DFJ_all_sub- tours.run(55) (modified from AMPL website(56) ). n In this tutorial, the subgradient optimization algorithm This script explicitly uses the model with all O(2 ) is presented in detail. subtour constraints. This is meant only for very small instances. With sufficient time for a computer lab, students may • DFJ-simple.mod(57) and DFJ-simple.run(58) . This be given the relevant AMPL scripts, including those script starts with the model consisting of just the for Prim's (prims.run(50)), Kruskal's (kruskal.run(51) , simple bounds and the degree constraints. At each originally developed by Olinick (2006), and subgradi- stage the current integer linear programming for- ent optimization (HeldKarp.run(52)). Students should mulation is solved, and then a single violated be challenged to match up the steps of the algorithm subtour inequality is appended to the formulation. from the notes with lines of code in AMPL. The script stops when there is no violated subtour constraint. These scripts do not use separate model files. Since these do not call the IP solver, AMPL's script processor • DFJ.mod(59) and DFJ.run(60). This script also starts can solve larger spanning trees than would be solvable with the model consisting of just the simple bounds through calls to the student-version IP solver. Of and the degree constraints. The scripts executes a course, this depends on the commands employed. If sequence of stages, repeating until a substage finds you modify the script and find that AMPL complains an optimal tour. At each stage we do the following: about the number of variables, try using parameters 1. Repeatedly solve the current linear program; instead of variables. identify a violated subtour constraints by solving further (max-flow/min-cut) linear Lecture 3. More solution methods for the TSP.Pow- programs, and append it to the current formu- erPoint presentation(53) lation; this sub-stage terminates when there are no further violated subtour constraints; if The majority of Lecture 3 presents the DFJ subtour cut the resulting solution is integer, then we have generation algorithm. We use a simple 6-city example an optimal tour, and we terminate the script. from Winston (2003), an example which produces subtours with the 2-matching relaxation. The max-flow 2. Solve the current formulation as an integerlin- algorithm is then developed as a method to find sub- ear program. Identify a violated subtour con- tours. The presentation shows the output from AMPL straint and append it to the current formula- running, so students see the iterative nature of the al- tion. If there is no violated subtour constraint, gorithm. then we have an optimal tour, and we termi- (49)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/PowerPoint/03_Tutorial_TSP-MST_Lagrangean_relaxation.ppt (50)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/Prims/prims.run (51)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/kruskal/kruskal.run (52)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/HeldKarp/HeldKarp.run (53)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/PowerPoint/04_More_solution_methods_for_the_TSP.ppt (54)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/DFJ/All_subtours/DFJ_all_subtours.mod (55)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/DFJ/All_subtours/DFJ_all_subtours.run (56)http://www.ampl.com/FAQ/tsp.mod (57)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/DFJ/1_subtour_at_a_time/DFJ-simple.mod (58)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/DFJ/1_subtour_at_a_time/DFJ-simple.run (59)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/DFJ/subtours_by_maxflow/DFJ.mod (60)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/DFJ/subtours_by_maxflow/DFJ.run INFORMS Transactions on Education 7:1(37-69) 44 © INFORMS ISSN: 1532-0545 LEE & RAFFENSPERGER Using AMPL for teaching the TSP nate the script; otherwise, we initiate a new tor_for_TSP_50_points.xls(68)".) Students are required stage. to give valid upper & lower bounds on the tour length, with a description of their procedures for finding these DFJ_restricted_arcs.mod(61) and DFJ_restrict- bounds. ed_arcs.run(62). This script executes roughly as DFJ.mod/run, but initially the number of arcs is The use of the restricted student version of CPLEX restricted to the shorter ones. Then, as described requires students to omit rows andvariables. The lim- at the end of the PowerPoint presentation, new itation on the student solver should be used to empha- arcs are added if they might improve on the solu- size that one's computer is never fast enough, and that tion of the linear programming relaxation. Arcs one's solver is never powerful enough. Real world with sufficiently large reduced cost can be omitted problems can be extremely demanding, and the re- from the model. In our experience, the 300-variable sourcefulness of the operations researcher is therefore limit in the student version of AMPL/CPLEX has put to the test. This invites students to use creativity been sufficient to prove optimality for 50-city (e.g., learn to use the NEOS server (see 5.1 below) or problems. Note that the restricted arcs versions other software, such as the open source COIN-OR Cbc, can be used to solve the homework directly, so the GNU LP Kit, or LP_Solve). scripts probably should not be given to students before the homework is due. As mentioned above, the solutionis to use DFJ_restrict- ed_arcs.mod(69)and DFJ_restricted_arcs.run(70), which The max-flow algorithm is then developed further into should not be given to students before the homework a new formulation. Martin (1991) gave an LP formula- is due. tion for the MST, which is best understood in this context. From this formulation for the MST, we then The most common error is to claim optimality when develop a formulation for the TSP with O(n3) variables. they cannot. Students realize that they must follow The relevant AMPL files are martin_tree_lp.mod(63), the common practice of eliminating unlikely variables and martin_tree_lp.run(64), which can be used to solve (e.g. long edges) from consideration, but then they for a minimum spanning tree, a 1-tree, or the TSP. make claims about optimality that they should not. The lecture concludes with hints for the homework, Students may gain nearly full marks without an opti- which we describe next. mal solution, but their approach must be reasonable. Minimal nonzero marks would be given for a tour 3.3. Homework. found visually for the upper bound and an ordinary 1-tree for the lower bound. Good answers should in- We assign a 50-city problem, which is too big to solve clude a good feasible solution, and at least a few itera- directly in the student version of AMPL with CPLEX(65) tions of the Held-Karp subgradient optimization algo- . (We have included a script which will generate a rithm. The lecturer can choose whether or not to give data file with random x,y coordinates, get_random_co- the students our included script (HeldKarp.run(71)). ordinates.run(66). This script calls another script, makesvg_points.run(67), which creates an SVG graph of the points. Alternatively, the lecturer can use a spreadsheet "Random_data_genera- (61)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/DFJ/Restricted_arcs/DFJ_restricted_arcs.mod (62)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/DFJ/Restricted_arcs/DFJ_restricted_arcs.run (63)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/MartinLP/martin_tree_lp.mod (64)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/MartinLP/martin_tree_lp.run (65)http://www.cplex.com/ (66)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/data/get_random_coordinates.run (67)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/makesvg_points.run (68)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/data/Random_data_generator_for_TSP_50_points.xls (69)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/DFJ/Restricted_arcs/DFJ_restricted_arcs.mod (70)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/DFJ/Restricted_arcs/DFJ_restricted_arcs.run (71)http://ite.pubs.informs.org/Vol7No1/LeeRaffensperger/AMPL_files/HeldKarp/HeldKarp.run INFORMS Transactions on Education 7:1(37-69) 45 © INFORMS ISSN: 1532-0545 LEE & RAFFENSPERGER Using AMPL for teaching the TSP 3.4. Exam problems • "b. (2 points) Write the new penalized distances in the table above." 3.4.1. A minimum spanning tree. • "c. (7 points) With the new penalized distances, draw the new 1-tree below." To write the problem: 3.4.3. Subtour cut generation. 1. Create a random problem. A 20-node problem is reasonable. Because new problems are easy to To write the problem, create a random problem. generate, students cannot memorize a given solu- Modify the DFJ AMPL script to stop with subtours. tion from a previous year's exam paper. Copy the graph into the exam paper, and ask students 2. For this random problem, print the graph and the to write constraints that break the displayed subtours. matrix of distances on the exam paper. 3.4.4. Understanding of specific algorithms. • Ask students to find the MST by hand, using Prim's or Kruskal's algorithm. Show students an AMPL script that they have studied. • Ask the students to draw the solution on the exam Ask them to explain several lines in the script, and paper, and show the order in which the arcs were how the algorithm requires those lines of script. For added. example, the Kruskal.run script early on contains the line, "let Best_Edges := {(i,j) in Unscanned: length[i,j] • To mark the question, find the correct solution = min{(u,v) in Unscanned} length[u,v]};" For a short with AMPL, and create the graph. Then simply answer question, you can ask students to explain in compare the student's answer to the correct an- two or three sentences the purpose of this line. A valid swer. answer would be something like, "This line initializes an iteration for one arc. The line finds the shortest 3.4.2. One step of subgradient optimization. unconnected arc among the set Unscanned, and adds this arc to the set Best_Edges. The algorithm then To write the problem: connects this arc to a component of the still-disconnect- ed tree." 1. Create a random problem. A ten-node problem is reasonable. 3.4.5. Short answer question. 2. Create the initial 1-tree with AMPL. "Describe two ways to get a good lower bound on the 3. Print the 1-tree and the matrix of distance on the traveling salesman problem." Answer: Method 1. Solve exam paper. the assignment or 2-matching problem, then add sub- 4. Include a table of the current arcs, labeled with tour breaking constraints. Every solution is a valid From node, To node, Distance, and Penalized distance. lower bound, and the lower bound improves with each added constraint. Method 2: Use Held & Karp 5. Provide a line or two of space for students to write subgradient optimization for the 1-tree relaxation. node penalties, for question a. Method 3: Solve any other TSP formulation as an LP. 6. Fill in all the entries except the Penalized distance column, for question b. 3.4.6. Short answer question. 7. Print a graph of the nodes without arcs, for ques- "Give two reasons why a lower bound would be tion c. helpful in solving the traveling salesman problem to optimality." Answer: First, if we find a tour that is Questions could be as follows: equal to the lower bound, then we know it is optimal. Second, during branch and bound, we can prune off • "a. (1 point) Starting with initial penalties of zero subproblems that have a worse lower bound than the and a step size of 30, calculate the new node current best lower bound. Third, with both an upper penalties. Write them here." (Provide space.) bound Uand a lower bound L, we can delete variables INFORMS Transactions on Education 7:1(37-69) 46 © INFORMS ISSN: 1532-0545