|
Computational Discrete Optimization CO 759, Winter 2015 Class meets in MC 6486, Tues-Thurs 10:00--11: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, assignment-problem branch-and-bound, Held-Karp 1-trees, 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 (Held-Karp 1-Trees): What is a good choice for a spanning-tree method to implement the Held-Karp 1-tree algorithm for the TSP, where a sequence of similar MST instances must be solved? Time Estimate = 3. The traveling-salesman problem and minimum spanning trees: part II Michael and Richard Karp. Mathematical Programming 1 (1971). The original Held-Karp paper. Solves a 64-city instance with branch-and-bound, using 1 trees as the bounding device. Asymptotic experimental analysis for the Held-Karp 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 Held-Karp 1-tree algorithm. Solving the traveling salesman problem with a parallel branch-and-bound 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 318-city TSPLIB instance with parallel Held-Karp. HW1: Build an implementation of Kruskal's algorithm suitable for large-scale 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: K-d Trees -- January 20/22 K-d trees for semidynamic point sets Jon Bentley, Proceedings of the Sixth Annual Symposium on Computational Geometry, ACM, 1990. K-d Tree Codes from Concorde Here are Concorde's K-d tree codes we discussed in class. Q4 (K-d Trees for Spheres): Implement a version of K-d 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 well-solved 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 b-matching. 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 large-scale traveling-salesman problem Dantzig, Fulkerson, and Johnson (1954). This is the paper that started the modern study of LP methods for discrete optimization problems. Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems Applegate, Bixby, Chvatal, and Cook (2003). Computing an LP-based lower bound for TSP instances have 1,000,000 or more cities. HW2: Build a branch-and-cut algorithm for the TSP, using subtour constraints and depth-first-search branching. Model Code for HW2 Here is a sample code and a several small test instances. Q6 (Combs): Design and implement heuristic-search algorithms for comb seperation for use in a cutting-plane 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 2-connected components. Solution of large-scale 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). Polynomial-time 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 100-city 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 column-generation approach within a branch-and-bound search. Maximum-weight stable sets and safe lower bounds for graph coloringg Held, Cook, and Sewell (2012). Describes how to apply the Mehrotra-Trick algorithm when using a possibly inaccurate LP solver. Graph Coloring Benchmarks List of best-known lower and upper bounds for test instances of the graph-coloring problem. The table NP-? gives a list of instances for which no optimal solution has been reported. exactcolors Held, Cook, and Sewell. A C-implementation of the Mehrotra-Trick algorithm. Q8 (Cutting Planes for Matchings): Design and implement a cutting-plane 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 1-factor and 2-factor problems. Solving matching problems with linear programming Groetschel and Holland, Mathematical Programming 33 (1985). This paper describes a 1-factor (that is, perfect matching) cutting-plane 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 2-matchings Groetschel and Holland, Computing 39 (1987). Here is a description of their 2-factor cutting-plane 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. Large-step Markov chains for the TSP incorporating local search heuristics Martin, Otto, Felten (1991) Introduced chained local search. Q9 (Edge Elimination in the TSP): Use local-search 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 2-opt-based method for edge elimination. Edge elimination in TSP instances Stefan Hougardy and Rasmus Schroeder (2014). Uses a deep search tree to eliminate edges with k-opt moves. Q10 (LP Pre-Solve): Develop and implement pre-solve techniques for linear-programming 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 pre-solve 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 branch-decomposition methods. Tour merging via branch-decomposition Cook and Seymour. INFORMS Journal on Computing 15 (2003). Describes a heuristic algorithm for computing low-order 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 large-scale 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 Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems Applegate, Bixby, Chvatal, Cook. Mathematical Programming 97 (2003) COIN_OR -- Includes a number of fraweworks for implementing branch-and-cut 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 Held-Karp 1-tree algorithm 2. Team: Steely Glint General b-matching via reduction and cutting planes; applied to data from the design of automobile engines 3. Team: Lacking that Small Match Temperamant General b-matching 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 modest-sized 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 |
|