Combinatorial Optimization and Integer Programming

Spring 2011

MATP6620 / DSES6760

Course basics:

• Course outline.
• Some books will be placed 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.
• Grades through the midterm, for people who've handed in all 5 homeworks.

Midterm Exam:

Here are the solutions.

Some old exams

Projects

• Presentation schedule

Homeworks:

• Homework 1. The AMPL FAQ describes a way to express all the subtour elimination constraints using just one AMPL constraint. Here is the solution to question 5.
• Homework 2. Here are the solutions to questions 2-5.
• Homework 3. Here are the solutions to questions 1-4.
• Homework 4. Here are the solutions.
• Homework 5. (See this brief note on solving continuous knapsack problems to help with problem 3.) Here are the solutions.
• Homework 6. Here are the solutions.
• Homework 7.

Notes:

Introduction:

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

• Introduction to NP-completeness.
  • Lecture 3, Feb 1: Pages 1-10.
  • Lecture 4, Feb 4: Pages 11-14.
• NP-completeness reductions: Hamiltonian cycle.
  • Lecture 4, Feb 4: Pages 1-10.
  • Lecture 5, Feb 8: Page 11.
• NP-completeness: node packing, knapsack, linear programming.
  • Lecture 4, Feb 4: Pages 1-3.
  • Lecture 5, Feb 8: Pages 4-14.
• Polynomial equivalence of separation and optimization.
  • Lecture 5, Feb 8: Pages 1-4.

• Introduction to polyhedral theory. (See also the four typewritten handouts from February 11.)
  • Lecture 6, Feb 11: Pages 1-10.
• Facets.
  • Lecture 6, Feb 11: Pages 1-3.
  • Lecture 7, Feb 15: Pages 4-10.
• Chvatal-Gomory rounding.
  • Lecture 7, Feb 15: Pages 1-5, 13 (skip 6-12).
  • Lecture 8, Feb 18: Pages 14-19.
• Gomory's cutting plane algorithm.
  • Lecture 8, Feb 18: 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 1-6.
  • Lecture 17, Mar 29: Pages 7-8.
• Node packing. Lifting.
  • Lecture 10, Feb 25: Pages 1-5.
  • Lecture 11, Mar 1: Pages 6-9.
• Knapsack problems and satisfiability problems.
  • Lecture 11, Mar 1: Pages 1-3.
  • Lecture 12, Mar 4: Pages 4-6.
• Maxcut problems and linear ordering problems.
  • Lecture 12, Mar 4: Pages 1-4.
  • Lecture 13, Mar 8: Pages 5-13.
  See also the handout on the Barahona-Mahjoub routine for finding violated constraints for MAXCUT problems.
• The traveling salesman problem. The Concorde TSP solver is available from this website at Georgia Tech.
  • Lecture 14, Mar 11: Pages 1-10.
• Lift and project, and disjunctive cuts.
  • Lecture 15, Mar 22: Pages 1-10.
  • Lecture 16, Mar 25: Page 11.
• Total unimodularity.
  • Lecture 16, Mar 25: Pages 1-3.
  • Lecture 17, Mar 29: Pages 4-5.
• Perfect graphs.
  • Lecture 16, Mar 25: both pages.

• Part 1
  • Lecture 17, Mar 29: Pages 1-6.
  • Lecture 18, Apr 1: Page 7.
• Part 2.
  • Lecture 18, Apr 1: Pages 1-8.
• See also the handouts of an example of branch-and-bound, 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.

• MaxCut, Lovasz Theta number, node packing, completely positive programs. (Updated April 8.)
  • Lecture 19, Apr 5: Pages 1-6, 10, 12-14.
  • Lecture 20, Apr 8: Pages 7, 9, 17-23.

• Lagrangian relaxation.
  • Lecture 21, Apr 15: Pages 1-9
  • Lecture 23, Apr 22: Pages 10-11.
• Cutting plane and bundle methods for solving Lagrangian relaxations.
  • Lecture 23, Apr 22: Pages 2-7.
• Benders decomposition.
  • Lecture 24, Apr 26: all pages.
• Branch and price.
  • Lecture 25, Apr 29: all pages.

• GRASP.
  • Lecture 24, Apr 26: Pages 1-3.
• Simulated annealing.
• Tabu search.
  • Lecture 25, Apr 29.

Mixed integer nonlinear programming.

• Lecture 26, May 3.

• Lecture 27, May 6.

• Approximation algorithms.
  • Lecture 27, May 6: Pages 13-15.
• The primal-dual method.
  • Lecture 27, May 6: Pages 1-4.

Handouts:

• The simplex algorithm and an iteration of it. (Handed out on January 25.)
• Graph theory. (Handed out on January 25.)
• Linear algebra. (Handed out on February 11.)
• Affine spaces. (Handed out on February 11.)
• Dimension, polyhedra, and faces. (Handed out on February 11.)
• Extreme points and extreme rays of polyhedra. (Handed out on February 11.)
• The Barahona-Mahjoub routine for finding violated constraints for MAXCUT problems. (Handed out on March 4, covered on March 8.)
• A brief note on solving continuous knapsack problems.
• 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 1.)
• Computational results with various branching rules, from a paper by Achterberg, Koch, and Martin. (Handed out on April 1.)

Papers and resources:

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

RPI Math