|
Computational Discrete Optimization ISyE 8803, Fall 2009 Class meets in Groseclose 403, Tues-Thurs 1:35--2:55. Twitter feed at isye8803. Algorithm Engineering -- August 18, 2009 Klaus Truemper's Leibniz System A link to the SAT system we mentioned in class. Chair of Algorithm Engineering University of Dortmund's Petra Mutzel leads an Algorithm Engineering group. xkcd file-copy comic Tiny Traveling Salesman Problems -- August 20, 2009 Faster and faster and faster yet Jon Bentley, Unix Review 1997 (web.archive.org). Codes for tiny TSPs by complete enumeration. TSP Maps Google-map implementation of tiny TSP solver. xkcd TSP comic Q1: How should one avoid repeated spanning tree computations in computing a bound to prune the search? Q2: Is the enumeration algorithm suitable for a parallel implementation on a graphics processing unit (GPU) using CUDA or OpenCL? 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. Minimum Spanning Trees -- September 1, 2009 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 material discussed in class. "An optimal minimum spanning tree algorithm" S. Pettie and V. Ramachandran, J. ACM. 49(1) 16--34, 2002. Available on the home page of Seth Pettie. Q3: In practice Kruskal works better on sparse graphs and Prim on dense graphs. What edge densitity is a practical point for switching from one algorithm to the other? Dynamic Programming for Small TSPs -- September 3, 2009 "A dynamic programming approach to sequencing problems" M. Held and R. M. Karp, Journal of the Society for Industrial and Applied Mathematics 10 (1962) 196--210. This 1962 paper describes the current record holder for the best worst-case complexity for the TSP. It can be downloaded from our Georgia Tech Library. Exact algorithms for NP-hard problems: A survey Gerhard Woeginger, LNCS 2570, Springer, 2003, pp. 185--207. A nice survey, including a description of the Held-Karp DP algorithm and some related open problems. 2009 Iron Butt Rally A prize-collecting TSP called ``the world's toughest motorcycle rally.'' 48 States--10 Days A variant of the TSP that asks for the shortest route to visit the 48 continental states. Q4: How can one save memory in a practical implementation of the Held-Karp DP algorithm? Is there a range of problem sizes for which this DP algorithm can defeat a good implementation of the complete enumeration approach in practice? Q5: Try to set a record for a shortest 48 States tour. This would likely involve a combination of the TSP and integer programming. Geometric algorithms via K-d trees -- September 8, 2009 K-d trees for semidynamic point sets J. Bentley. Symposium on Computational Geometry, ACM, 1990, pp. 187--197. Allows for the deletion and undeletion of data points. KD-Tree -- a YouTube video. Evaluating the strength of cutting planes -- September 10, 2009 Embedding cuts in a branch-and-cut framework: A computational study with 0-1/2 cuts G. Andreello, A. Caprara, M. Fischetti. INFORMS Journal on Computing 19 (2007) 229--238. Q6: Is there a good geometric criterion for selecting candidate cutting planes from a pool of possiblities? Is the volume of the cut-off region an indicator of the effectiveness of a cutting plane? TSP Subtour Relaxation -- September 15, 2009 Finding the exact integrality gap for small traveling salesman problems G. Benoit and S. Boyd, Mathematics of Operations Research (2008) 921--931. When is the assignment bound tight for the asymmetric traveling-salesman problem? A. Frieze, R. M. Karp, B. Reed, SIAM Journal on Computing (1995) 484--493. Q7: A well-known open is problem is to find a combinatorial (non-ellipsoid) algorithm for optimizing over the subtour polytope. Another is the 4/3rds conjecture and its strengthening by Benoit and Boyd. Held-Karp and Branching -- September 17, 2009 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. Graph Coloring -- October 20, 2009 COLOR04: Graph Coloring and its Generalizations Web page set up by Mike Trick, including test instancs and links. Graph Coloring Benchmarks A googlesites page with up-to-date results on various test instances. References and results for difficult DIMACS instances Site run by Daniel Porumbel. Includes many recent refernces on graph-coloring heuristics. The Gurobi Solver -- October 27, 2009 Makefile Use to compile and build the test code. color.c Version 0.0 of the coloring code. The just shows how to parse a command line and link to the Gurobi library. The Coloring LP -- October 29, 2009 Makefile Use to compile and build the test code. color.c Version 0.1 of the coloring code. Creates an initial LP based on greeding coloring. color.h Version 0.1 of the coloring code. Definitions for the coloring functions. greedy.c Version 0.1 of the coloring code. Build greedy coloring. Exact Computations with Branch-and-Price -- November 3, 2009 color091102.tgz Current coloring code (gzipped tar file). Includes a max-weight stable-set algorithm via a Gurobi MIP call, implemented by Stephan Held. Using this in column generation obtains good (but approximate, due to floating-point errors) lower bounds for coloring. Exact Graph Coloring Project -- November 5, 2009 A strong cutting plane/branch-and-bound algorithm for node packing G. L. Nemhauser and G. Sigismondi, J. Opl. Res. Soc. Vol. 43, pp. 443--457, 1992. Cliquer--routines for clique searching Max-weight clique code by S. Niskanen and P. Ostergard. Google Code: Exactcolors exactcolors Project page. Send a mail to bico@isye.gatech.edu to join the project. |
|