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
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.
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
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
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