Combinatorial Optimization and Integer Programming

Spring 2013

MATP6620 / ISYE6760

Course basics:

• Course outline.
• Scores on the first five homeworks and the midterm.
• Some books are on reserve in the library. You can borrow the materials for up to an hour. Further, you can borrow the books overnight if you check them out less than an hour before closing time and return them early the following day.

Midterm Exam:

Some old exams

Solutions to midterm.

Projects

• The remaining presentations will take place on Friday May 17, from 3-6pm, in Troy 2012. The presentations should be no more than 12 minutes long. There will be 13 presentations. The order of the presentations will be determined on the day.
• You should prepare 20 copies of your slides to hand out in advance. Send me an electronic version of your slides.
• Please ask questions during the presentations. I will award bonus points for good questions; I will not deduct points for difficulties in answering questions from students.
• Your writeup is due on May 15. Your report should be about 5-10 pages long. It must be typewritten: send me an electronic copy as a pdf file. It should describe the problem you worked on, what you did to solve the problem, and the significance of what you did. You should also cite relevant references and state what was novel about your approach. For group projects, also hand in one sheet from each group member discussing his or her individual contribution.

Homeworks:

• Homework 1. Here are the solutions.
• Homework 2. Here are the solutions.
• Homework 3. Here are the solutions.
• Homework 4. Here are the solutions. Here is some more information about a facet-defining family of constraints.
• Homework 5. (See this brief note on solving continuous knapsack problems.) Here are the solutions.
• Homework 6. Here are the solutions.

Notes:

Introduction:

• Introduction: example problems, linear programming.
  • Lecture 1, Jan 22: Pages 1-7.
  • Lecture 2, Jan 25: Pages 8-15, including the typewritten handouts on the simplex algorithm and an iteration of it.
• Graph theory: introduction, max flow.
  • Lecture 1, Jan 22: Pages 1-6, via the typewritten handout on graph theory.
  • Lecture 2, Jan 25: Pages 14-20, 24
• Graph theory: minimum spanning trees, matchings. Most of this material is not covered in class.
  • Lecture 3, Jan 29: Pages 1-3, 6-8 (skimmed).

• Introduction to NP-completeness.
  • Lecture 3, Jan 29: Pages 1-10.
  • Lecture 4, Feb 1: Pages 11-14.
• NP-completeness reductions: Hamiltonian cycle. For a nice presentation of the reduction of 3-SAT to Hamiltonian cycle, see this link (pdf).
  • Lecture 4, Feb 1: Pages 1-10.
  • Lecture 5, Feb 5: Page 11.
• NP-completeness: node packing, knapsack, linear programming.
  • Lecture 4, Feb 1: Pages 1-3.
  • Lecture 5, Feb 5: Pages 4-14.
• Polynomial equivalence of separation and optimization.
  • Lecture 5, Feb 5: Pages 1-4.

• Introduction to polyhedral theory. (See also the four typewritten handouts from February 8.)
  • Lecture 6, Feb 8: Pages 1-10.
• Facets.
  • Lecture 6, Feb 8: Pages 1-3.
  • Lecture 7, Feb 12: Pages 4-10.
• Chvatal-Gomory rounding.
  • Lecture 7, Feb 12: Pages 1-5, 13 (skip 6-12).
  • Lecture 8, Feb 15: Pages 14-19. See also this method for showing the Chvatal rank is at least 2.
• Gomory's cutting plane algorithm.
  • Lecture 8, Feb 15: Pages 1-11. See also the recent paper by Fischetti et al. (pdf).
• Mixed integer programming, including Gomory's mixed integer cut.
  • Lecture 9, Feb 22: Pages 2-3.
  • Lecture 10, Feb 26: Pages 4-6.
  • Lecture 15, Mar 22: Pages 1, 7-8.
• Maxcut problems and linear ordering problems.
  • Lecture 10, Feb 26: Pages 4-7.
  • Lecture 11, Mar 1: Pages 1-3.
  See also the handout on the Barahona-Mahjoub routine for finding violated constraints for MAXCUT problems.
• Node packing. Lifting.
  • Lecture 11, Mar 1: Pages 1-5.
  • Lecture 12, Mar 5: Pages 6-9.
• Knapsack problems and satisfiability problems.
  • Lecture 12, Mar 5: Pages 1-3.
• The traveling salesman problem. The Concorde TSP solver is available from this TSP website at Georgia Tech. The website also includes images of TSPs and information about the history of the TSP. Optima 90 contains a discussion of approximation algorithms for the TSP.
  • Lecture 13, Mar 8: Pages 1-10.
• Lift and project, and disjunctive cuts.
  • Lecture 14, Mar 19: Pages 1-9.
  • Lecture 15, Mar 22: Pages 10-11.
• Total unimodularity.
  • Lecture 16, Mar 22: Pages 1, 3, and 4.
  • Lecture 17, Mar 29: Pages 2 and 5.
• Perfect graphs.
  • Lecture 17, Mar 29: both pages.

• Part 1
  • Lecture 18, Apr 2: Pages 1-6.
  • Lecture 19, Apr 5: Page 7.
• Part 2.
  • Lecture 19, Apr 5: Pages 1-8.
• See also the handouts of an example of branch-and-bound (lecture 17), an example of branch-and-cut, and the branch-and-cut algorithm. Also handed out were some computational results from a paper by Achterberg, Koch, and Martin (see here for more tables of results).

• MaxCut, Lovasz Theta number, node packing, completely positive programs.
  • Lecture 20, Apr 9: Pages 1-6, 10, 12-14.
  • Lecture 21, Apr 12: Pages 7, 9, 17-23.

• Lagrangian relaxation.
  • Lecture 22, Apr 16: Pages 1-5
  • Lecture 24, Apr 23: Pages 6-11.
• Cutting plane and bundle methods for solving Lagrangian relaxations.
  • Lecture 24, Apr 23: Pages 2-7. (Skimmed.)
• Benders decomposition.
  • Lecture 25, Apr 26: all pages.
• Branch and price.
  • Lecture 25, Apr 26: all pages.

• Lecture 26, April 30.

• GRASP.
  • Lecture 27, May 3: Pages 1-3.
• Simulated annealing.
• Tabu search.
  • Lecture 27, May 3.
• Feasibility pump.
  • Lecture 27, May 3.

Constraint programming. See also a handout on the job shop scheduling OPL example from an Interfaces paper by Lustig and Puget, and Michael Trick's powerpoint presentation on constraint programming.

• Lecture 27, May 3.

• Approximation algorithms.
  • Lecture 28, May 7: Pages 13-15.
• The primal-dual method.
  • Lecture 28, May 7: Pages 1-4.
• Matroids.
  • Lecture 28, May 7.

Handouts:

• Graph theory. (Handed out on January 22.)
• The simplex algorithm and an iteration of it. (Handed out on January 25.)
• Linear algebra. (Handed out on February 8.)
• Affine spaces. (Handed out on February 8.)
• Dimension, polyhedra, and faces. (Handed out on February 8.)
• Extreme points and extreme rays of polyhedra. (Handed out on February 8.)
• The Barahona-Mahjoub routine for finding violated constraints for MAXCUT problems. (Handed out on Feb 26.)
• A brief note on solving continuous knapsack problems. (Handed out on March 29.)
• An example of branch-and-bound. (Handed out on March 29.)
• The branch-and-cut example and algorithm were taken from this paper. (Handed out on April 2.)
• Computational results with various branching rules, from a paper by Achterberg, Koch, and Martin. (Handed out on April 2.)

Papers and resources:

• Two libraries of MINLP problems: MINLPlib and MacMINLP.
• MINLP references:
  • J.-P. Goux and S. Leyffer, Solving large MINLPs on computational grids, Optimization and Engineering 3(3), 2002, pages 327-346.
  • I. E. Grossmann, Review of Nonlinear Mixed Integer and Disjunctive Programming Techniques, Optimization and Engineering 3(3), 2002, pages 227-252.
  • S. Leyffer, Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Computational Optimization and Applications 18, 2001, pages 295-309.
  • M. Tawarmalani and N. V. Sahinidis, Global optimization of mixed integer nonlinear programs: a theoretical and computational study, Mathematical Programming 99, 2004, pages 563-591.
• Tutorial on Computational Complexity, by Craig Tovey. Appeared in Interfaces 32(3), pages 30-61, 2002. Can be downloaded via the library website.
• The P=NP conjecture is one of the Millennium Prize Problems. A problem based on Minesweeper is NP-complete.
• PRIMES is in P; see also here.
• NP-Completeness columns by David S. Johnson.
• Survey papers on cutting plane algorithms, branch-and-bound, and branch-and-cut.
• An amusing interview with Vasek Chvatal regarding cutting plane methods for the TSP.
• Here is a page on the history of the TSP, with pictures (including one involving Car 54 and one of the optimal tour for a graph with 13,509 cities). This is part of a larger site at Georgia Tech on the TSP. The website also includes the downloadable software Concorde. Two further references for this problem are TSPBIB and Vasek Chvatal's page on the TSP. Instances of TSP can be obtained from the TSPLIB. Hamilton called the problem of finding a route through the vertices of a icosahedron the Icosian game. A similar problem was posed by Euler: Is it possible for a knight to visit every square of a chessboard without visiting any square twice?
• A list of selected textbooks and articles in combinatorial optimization, compiled by Brian Borchers. (Postscript file.) Updated Feb 9, 1999.
• A. Zanette, M. Fischetti, E. Balas. Lexicography and degeneracy: can a pure cutting plane algorithm work?, Mathematical Programming A, 2009, online first. (pdf).
• PORTA, a polyhedral representation algorithm. If you provide the algorithm with an integer programming problem, it will return a list of all the extreme points and information about the facets. Also available from the same site is SMAPO, a library of linear descriptions of polytopes of small instances of various integer programming problems.
• Computational Materials for Combinatorial Optimization, maintained by Jon Lee.
• AMPL is a mathematical programming and optimization modeling language. You can input your model into AMPL in a reasonably intuitive way and it will use a solver (such as MINOS or CPLEX) for solving the problem. It is capable of solving linear, nonlinear, and integer programs. Here is local information about AMPL, including information about using it on RCS. You can download the first chapter of the book.
• A survey paper on GRASP.
• A survey paper on metaheuristics for the TSP (scroll down to the last couple of papers on the TSP, since the papers are in chronological order).
• A survey paper on genetic algorithms (volume 9, number 3 of INFORMS Journal on Computing, by Colin Reeves).
• A survey paper on tabu search.
• The semidefinite programming homepage maintained by Christof Helmberg.
• A survey paper by Mike Todd on semidefinite programming, with an emphasis on algorithms. (Acta Numerica 10 (2001), pp. 515-560.)
• A survey paper by Michel Goemans on semidefinite programming in combinatorial optimization. (Mathematical Programming, 79 (1997), pages 143-161.)
• Myths and counterexamples in optimization. This site shows that you have to be careful about your assumptions when you state some things that are "obvious" in optimization.
• A list of operations research sites.
• A compendium of approximability results for NP optimization problems.
• Some papers on the hardness of approximation by Sanjeev Arora.