Combinatorial Optimization and Integer Programming

Spring 2017

MATP6620 / ISYE6760

Course basics:

• Course outline.
• LMS.
• Aggregate scores on the six homeworks plus the midterm, out of 420: 401 394 386 381 379 370 365 363 358 357 355 354 352 339 312 286
• Some books are on reserve in the library. You can borrow the materials for up to an hour.

Midterm Exam:

Scores on the midterm: 98 95 84 84 81 80 78 76 75 69 67 67 66 65 59 58 44

In class on Friday, March 31. You can bring one sheet of handwritten notes. (You can write on both sides, the paper can be no larger than 8.5x11 inches.) The exam will cover everything in class up to March 28.

Here are some old exams.

Projects

Homeworks:

• Homework 1. Here are the solutions.
• Homework 2. Here are the solutions.
• Homework 3. Here are the solutions.
• Homework 4. Here is an example for questions 3 and 4 to illustrate the notation in question 4. Here are the solutions.
• Homework 5. Here are the solutions.
• Homework 6. Question 4 is based on this article. Here are the solutions.

Notes:

Introduction:

• Introduction: example problems, linear programming.
  • Lecture 1: Pages 1-7.
  • Lecture 2: Pages 8-15, including the typewritten handouts on the simplex algorithm and an iteration of it.
• Graph theory: introduction, max flow.
  • Lecture 1: Pages 1-6, via the typewritten handout on graph theory (also available as a pdf with more pictures but more page breaks).
  • Lecture 2: Pages 14-20, 24
• Graph theory: minimum spanning trees, matchings. Most of this material is not covered in class.
  • Lecture 3: Pages 1-3, 6-8 (skimmed).

• Introduction to NP-completeness. See also some typewritten notes.
  • Lecture 3: Pages 1-10.
  • Lecture 4: Pages 11-14.
• NP-completeness reductions: Hamiltonian cycle. For a nice presentation of the reduction of 3-SAT to Hamiltonian cycle, see this link from Carl Kingsford.
  • Lecture 4: Pages 1-10.
  • Lecture 5: Page 11.
  • Lecture 7: Reduction of Hamiltonian Cycle to Hamiltonian Path in two separate ways: (i) duplicate a node, add leaves to each copy, (ii) remove an edge, add leaves to each endpoint, check all edges. Reduction of Hamiltonian Cycle to TSP with upper bound, in the general case and in the case where the weights obey the triangle inequality.
• NP-completeness: node packing, knapsack, linear programming.
  • Lecture 4: Pages 1-3.
  • Lecture 5: Pages 4-14.
• Polynomial equivalence of separation and optimization.
  • Lecture 5: Pages 1-4.

• Introduction to polyhedral theory. There is a typewritten html version of most of these notes, as well as a typewritten pdf version with more examples but more pagebreaks.
  (See also the four typewritten handouts from February 13.)
  • Lecture 6: Pages 1-10.
• Facets.
  • Lecture 6: Pages 1-3.
  • Lecture 7: Pages 4-10. See also these typewritten notes for some of the definitions.
• Chvatal-Gomory rounding. See also these typewritten notes for some of the definitions.
  • Lecture 7: Pages 1-5, 13 (skip 6-12).
  • Lecture 8: Pages 14-19. See also this method for showing the Chvatal rank is at least 2 (typewritten).
• Gomory's cutting plane algorithm.
  • Lecture 8: Pages 1-11. Here is an example of Gomory's cutting plane method (typed). See also the recent paper by Fischetti et al. (pdf).
• Mixed integer programming, including Gomory's mixed integer cut.
  • Lecture 9: Pages 1-6. See also the typewritten derivation of the Gomory mixed integer cut.
  • Lecture 16: Pages 1, 7-8. See also this example of a flow cover constraint.
• Node packing. Lifting. See also this typewritten handout on proving a face is a facet.
  • Lecture 10: Pages 1-2.
  • Lecture 11: Pages 3-9.
• Knapsack problems and satisfiability problems.
  • Lecture 12: Pages 1-3.
• Maxcut problems and linear ordering problems.
  • Lecture 12: Pages 4-5.
  • Lecture 12: Pages 6-7. See also the handout on the Barahona-Mahjoub routine for finding violated constraints for MAXCUT problems.
  • Lecture 12: Pages 1-3. Also available in typewritten form (although the symbol for "not in" was not converted quite correctly from the latex). The details of the proof that a chordless odd cutset inequality defines a facet were skipped.
• The traveling salesman problem. The Concorde TSP solver is available from this TSP website at the University of Waterloo 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: Pages 1-10.
• Lift and project, and disjunctive cuts. Notes slightly updated on March 21, 2017.
  • Lecture 14: Pages 1-8.
  • Lecture 15: Pages 9-14. Here is the ampl code for the linear program with complementarity constraint examples.
• Total unimodularity.
  • Lecture 16. See also typewritten notes for part of this material.
• Perfect graphs.
  • Lecture 16: all pages.

• Part 1
  • Lecture 16: all pages. See also the handout of an example of branch-and-bound.
• Part 2.
  • Lecture 17: Pages 1-8. Notes updated to include material on variable fixing on 2015-04-17.
• See also the handouts of 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 19: Pages 1-6, 10, 12-14.
  • Lecture 20: Pages 7, 9, 17-23.

• Lagrangian relaxation.
  • Lecture 20: Pages 3-4.
  • Lecture 21: Pages 1-2, 5-9. See also typewritten notes for the theorems.
  • Lecture 22: Pages 10-11.
  • Two examples of Lagrangian relaxation: Lecture 21.
• Cutting plane and bundle methods for solving Lagrangian relaxations.
  • Lecture 22: Pages 2-7. (Skimmed.)
• Benders decomposition (typewritten).
  • Lecture 22.
    See also
    • a typewritten example,
    • and an ampl implementation for a facility location problem, with a model file, data file, and run file. You can run the example by typing "model benders.run;" in response to an AMPL prompt. This is the resulting output.
• Logical Benders decomposition for scheduling problems.
  • Lecture 23: all pages.
• Logical Benders decomposition for linear programs with complementarity constraints (typewritten). (Updated April 18, 2017 to make subproblem notation consistent and to correct the solution to the first subproblem in the example.)
  • Lecture 23: all pages.
• Branch and price. (Updated April 28, 2017.)
  • Lecture 26: all pages.

• Lecture 24: pages 1-3, 7, 8.
• See also typewritten notes on McCormick inequalities.
• Lecture 25: pages 4-6, 9, 10.

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

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

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

Handouts:

• Graph theory. (Handed out in Lecture 1.)
• The simplex algorithm and an iteration of it. (Handed out in Lecture 3.)
• Linear algebra. (Handed out in Lecture 3.)
• Affine spaces. (Handed out in Lecture 6.)
• Dimension, polyhedra, and faces. (Handed out in Lecture 6.)
• Extreme points and extreme rays of polyhedra. (Handed out in Lecture 6.)
• The Barahona-Mahjoub routine for finding violated constraints for MAXCUT problems. (Handed out in Lecture 12.)
• A brief note on solving continuous knapsack problems. (Handed out on Apr 3.)
• An example of branch-and-bound. (Handed out in Lecture 16.)
• The branch-and-cut example and algorithm were taken from this paper. (Handed out in Lecture 17.)
• Computational results with various branching rules, from a paper by Achterberg, Koch, and Martin. (Handed out in Lecture 17.)

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.
• 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. It is available from the LMS page for the course. Here is local information about AMPL, including information about using it on RCS. You can download the the whole of the book, chapter by chapter.
• 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.