Computational Discrete Optimization CO 759, Winter 2015 Class meets in MC 6486, TuesThurs 10:0011:20. Tentative Outline of Topics Computation: Tiny Traveling Salesman Problems  January 6/8 The Setting D. Applegate, W. Cook, S. Dash, D. Johnson, Draft of Chapter 1 for the planned book A Practical Guide to Discrete Optimization. Tiny TSP Codes These are the C codes presented in class and described in the The Setting. Faster and faster and faster yet Jon Bentley, Unix Review 1997 (web.archive.org). xkcd TSP comic Q1 (TSP Enumeration with a GPU): Is the enumeration algorithm suitable for a parallel implementation on a graphics processing unit (GPU)? This would only increase by several cities the size of instances that can be handled, but it would be an interesting test case for GPU computing. Time Estimate = 2. Q2 (Solving Small TSPs): There are a number of efficient algorithms for solving small instances of the TSP: tour emumeration, dynamic programming, assignmentproblem branchandbound, HeldKarp 1trees, and others. The best choice in practice will depend on the problem size and structure. Make a study of the various algorithms to determine break points where one method becomes more effective than another. Time Estimate = 3. Graphs I: Minimum Spanning Trees  January 13/15 Data Structures and Network Algorithms Robert Endre Tarjan, SIAM, 1983. The above Google Books link gives a preview of Chapter 2 on Disjoint Sets, covering the union and find, and Chapter 6 on Minimum Spanning Trees. Q3 (HeldKarp 1Trees): What is a good choice for a spanningtree method to implement the HeldKarp 1tree algorithm for the TSP, where a sequence of similar MST instances must be solved? Time Estimate = 3. The travelingsalesman problem and minimum spanning trees: part II Michael and Richard Karp. Mathematical Programming 1 (1971). The original HeldKarp paper. Solves a 64city instance with branchandbound, using 1 trees as the bounding device. Asymptotic experimental analysis for the HeldKarp TSP bound Johnson, McGeoch, Rothberg (1996). Contains statistics on the value of the subtour bound for the TSP. See the reference list for many computational papers on the HeldKarp 1tree algorithm. Solving the traveling salesman problem with a parallel branchandbound algorithm on a 1024 processor network S. Tschoeke, M. Raecke, R. Lueling, B. Monien. University of Paderborn, Mathematics and Computer Science, Research Report, 1995. Solves a 318city TSPLIB instance with parallel HeldKarp. HW1: Build an implementation of Kruskal's algorithm suitable for largescale sparse graphs. Model Code for HW1 Here is a sample code and a set of test instances, the largest having 10,000,000 vertices and 29,999,959 edges. Geometric Data: Kd Trees  January 20/22 Kd trees for semidynamic point sets Jon Bentley, Proceedings of the Sixth Annual Symposium on Computational Geometry, ACM, 1990. Kd Tree Codes from Concorde Here are Concorde's Kd tree codes we discussed in class. Q4 (Kd Trees for Spheres): Implement a version of Kd trees suitable for handling data sets with points on the sphere, such as the World TSP. Time Estimate = 1. Q5 (General Blossom Algorithm): The blossom algorithm for solving optimal matching problems can be extended, via a sequence of reductions, to a method for solving matching problems on general bidirected graphs. A working code (in FORTRAN) for this general algorithm was described in a 1969 technical report by Edmonds, Johnson, and Lockhart. An excellent (but difficult) project would be to attempt to create a new implementation. Time Estimate = 5. Matching: A wellsolved class of integer linear programs Very brief report by Edmonds and Johnson, where they mention the FORTRAN code written together with Scott C. Lockhart. A Computer Implementation of the Blossom Algorithm William Pulleyblank, Chapter 7, PhD Thesis, Waterloo, 1973. Contains a listing of his PL1 code for uncapciated bmatching. This is a good starting point for work on a bidirected matching code. Linear Programming I: Traveling Salesman Problem  January 27/29 Solution of a largescale travelingsalesman problem Dantzig, Fulkerson, and Johnson (1954). This is the paper that started the modern study of LP methods for discrete optimization problems. Implementing the DantzigFulkersonJohnson algorithm for large traveling salesman problems Applegate, Bixby, Chvatal, and Cook (2003). Computing an LPbased lower bound for TSP instances have 1,000,000 or more cities. HW2: Build a branchandcut algorithm for the TSP, using subtour constraints and depthfirstsearch branching. Model Code for HW2 Here is a sample code and a several small test instances. Q6 (Combs): Design and implement heuristicsearch algorithms for comb seperation for use in a cuttingplane algorithm for the TSP. Facet identification for the symmetric traveling salesman polytope Padberg and Rinaldi. Mathematical Programming 47 (1990). Section 5 describes a heuristic algoirthm for comb separation, based on decompositions into 2connected components. Solution of largescale symmetric travelling salesman problems Groetschel and Holland. Mathematical Programming 51 (1991). Section 4.3 describes shrinking heuristics for comb separation. Efficient separation routines for the symmetric traveling salesman problem I: general tools and comb separation Denis Naddef and Stefan Thienel (1999). Greedy heuristics for finding violated comb inequalities for the TSP. Separating maximally violated comb inequalities in planar graphs Fleischer and Tardos. Mathematics of Operations Research 24 (1999). Polynomialtime algorithm to either find a violated comb inequality or determine that no combs are violated by 1. Works only if the LP graph is planar. Q7 (Exact Combs): Implement an exact comb separation algorithm, targeting TSP instances with 100 cities. Separting clique trees and bipartition inequalities having a fixed number of handles and teeth in polynomial time Robert Carr, Mathematics of Operations Research 22 (1997). Describes an algorithm for exact comb separation. The running time grows exponentially with the number of teeth in the comb, so it is a challenge to develop a variant suitable for a 100city TSP. Linear Programming II: Graph Coloring  February 3/5 A column generation approach for graph coloring Mehrotra and Trick (1996). Uses a nice branching rule to embed a columngeneration approach within a branchandbound search. Maximumweight stable sets and safe lower bounds for graph coloringg Held, Cook, and Sewell (2012). Describes how to apply the MehrotraTrick algorithm when using a possibly inaccurate LP solver. Graph Coloring Benchmarks List of bestknown lower and upper bounds for test instances of the graphcoloring problem. The table NP? gives a list of instances for which no optimal solution has been reported. exactcolors Held, Cook, and Sewell. A Cimplementation of the MehrotraTrick algorithm. Q8 (Cutting Planes for Matchings): Design and implement a cuttingplane algorithm for solving matching problems on bidirected graphs. In the 1980s, successful codes of this type were created by Martin Groetschel and Olaf Holland for 1factor and 2factor problems. Solving matching problems with linear programming Groetschel and Holland, Mathematical Programming 33 (1985). This paper describes a 1factor (that is, perfect matching) cuttingplane code.It was tested on instances with up to 1,000 points, a very large size at the time. A cutting plane algorithm for minimum perfect 2matchings Groetschel and Holland, Computing 39 (1987). Here is a description of their 2factor cuttingplane code. It is tested on a set of TSP instances having up to 1,000 cities. Heuristic Search  February 10/12 11th Metaheuristics International Conference Experimental analysis of heuristics for the STSP David Johnson and Lyle McGeoch (2002) See page 14 for a table plotting tour quality versus running time for a wide variety of heuristic methods for the TSP. Optimization by simulated annealing Kirkpatrick, Gelatt, Vecchi. Science 220 (1983) Introduced the simulated annealing technique, using as examples the TSP and several problems arising in computer design. This paper has over 32,000 citations in Google Scholar Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning Johnson, Aragon, McGeoch, Schevon. Operations Research 39 (1991). Test several schemes for finding good coloring of graphs. Largestep Markov chains for the TSP incorporating local search heuristics Martin, Otto, Felten (1991) Introduced chained local search. Q9 (Edge Elimination in the TSP): Use localsearch methods to prove that some edges cannot be in any optimal tour in a given instance of the TSP. Nonoptimal edges for the symmetric traveling salesman problem Jonker and Volgenant. Operations Research 32 (1984). Fast 2optbased method for edge elimination. Edge elimination in TSP instances Stefan Hougardy and Rasmus Schroeder (2014). Uses a deep search tree to eliminate edges with kopt moves. Q10 (LP PreSolve): Develop and implement presolve techniques for linearprogramming models: identifying duplicate columns and redundant rows, primal and dual variable fixing, etc. Presolving in linear programming Andersen and Andersen. Mathematical Programming 71 (1995). Very nice survey of LP presolve techniques. Graphs II: Branch Decompositon  March 3/5 Algorithms (Chapter 6) S. Dasgupta, C. Papadimitriou, U. Vazirani. 2006 Section 6.7 describes the algorithmn for stable sets in trees that we covered in class. Branch and tree decomposition techniques for discrete optimization Illya Hicks, Arie Koster, Elif Kolotoglu. INFORMS TutORials in Operations Research (2005). Contains a survey of branchdecomposition methods. Tour merging via branchdecomposition Cook and Seymour. INFORMS Journal on Computing 15 (2003). Describes a heuristic algorithm for computing loworder branch decompositions and and an application to the TSP. Q11 (Heuristic Algorithms for Branch Decomposition): Implement a heuristic algorithm to build a branch decompositions for largescale graphs, aiming at instances having 100K nodes. Dynamic Programming  March 10/12 Dynamic Programming D. Applegate, W. Cook, S. Dash, D. Johnson, Draft of dynamic programming chapter for the planned book A Practical Guide to Discrete Optimization. Cutting Planes for Large Problems  March 17/19 Implementing the DantzigFulkersonJohnson algorithm for large traveling salesman problems Applegate, Bixby, Chvatal, Cook. Mathematical Programming 97 (2003) COIN_OR  Includes a number of fraweworks for implementing branchandcut algorithms. Computational Testing  March 24/26 A theoretician's guide to the experimental analysis of algorithms David S. Johnson (2001). Experimental analysis of algorithms Catherine McGeoch. Notices of the AMS, March 2001. Performance profiles at GAMS  background on performance profiles. Benchmarking optimization software with performace profiles Elizabeth Dolan and Jorge More. Mathematical Programming 91 (2002) Constraint Integer Programming Tobias Achterberg, Ph. D. Thesis, Berlin 2009. Contains beautiful examples of careful computational testing. Here are some tools for the final projects. Final Projects  March 31 1. Team: Tactical Grace Optimizing the HeldKarp 1tree algorithm 2. Team: Steely Glint General bmatching via reduction and cutting planes; applied to data from the design of automobile engines 3. Team: Lacking that Small Match Temperamant General bmatching via cutting planes 4. Team: Contents May Differ Facility location; applied to network design 5. Team: Killing Time Geometry for set separation Final Projects  April 2 1. Team: Don't Try this at Home TSP edge elimination 2. Team: Now We Try it My Way Comb separation 3. Team: You'll Clean that Up Before You Leave Algorithms for modestsized TSP instances 4. Team: All the Same, I Saw it First Heuristics for comb separation 5. Team: Never Talk to Strangers TSP edge elimination 6. Team: Well, I was in the Neighborhood Exact algorithm for generalized TSP 
