Integer and Combinatorial Optimization

Spring 2021

MATP6620 / ISYE6760

Course basics:

• Course outline. The slides for the outline along with the discussion of the outline are available on rpi.app.box.com. The discussion is also available here.
• Grades, software, notes, and other material will be posted on LMS.
• Lecture notes are available on rpi.app.box.com. Instructions to set up your box account are here: RPI Box account information.
• We will be using piazza this semester to answer questions. The signup page for piazza is here: MATP 6620 piazza signup.
• Office hours: Monday, Thursday 1-2pm or by appointment, on webex, https://rensselaer.webex.com/meet/mitchj
• Aggregate scores on homeworks 1,2,3, for those who submitted all homeworks, out of 160:
  159 155 150 145 144 144 143 142 142 141 140 140 138 137 133 132 128 122 118 108

Midterm Exam:

Here are some old exams.

Projects

• Some past projects.

Homeworks:

• Homework 1, due February 4. AMPL is available on LMS. If you are installing it on a Mac, you will also need to download the amplide.app.tgz. Installation instructions are here: ampl installation instructions. More instructions are available on LMS and Box. The ampl book is available to download here. Here is a screenshot showing the commands you need to enter in the AMPL IDE to solve question 1.

  Here are the solutions to homework 1.

• Homework 2, due February 18.

  Here are the solutions to homework 2.

• Homework 3, due March 4. Some past projects.

  Here are the solutions to homework 3.

• Homework 4, due March 18.

  Here are the solutions to homework 4.

• Homework 5, due April 15.

Notes from 2021:

• Lecture 1 (January 25)
  • Introduction: 1.1, 1.2
  • The traveling salesman problem: 2.7
  • Knapsack problems: 2.1
  • Facility location problems: 2.10.1
  • Links to the lecture.
• Lecture 2 (January 28)
  • Basic feasible solutions: 3.3
  • The simplex algorithm
  • An example of simplex
  • Motivation for the dual problem
  • Constructing the dual problem
  • Links to the lecture.
  • For more background on simplex and linear programming, see the course MATP 4700.
• Lecture 3 (February 1)
  • Duality theorems: 3.3
  • Multiple optimal solutions:
  • Links to the lecture.
  • For more background on simplex and linear programming, see the course MATP 4700.
• Lecture 4 (February 4)
  • Graph theory definitions:
  • Network flow problems: 4.3
  • The minimum spanning tree problem: 4.5
  • Matching problems: 4.4
  • Links to the lecture.
• Lecture 5 (February 8)
  • Algorithm complexity: 1.3
  • NP: 1.3
  • Node packing
  • Links to the lecture.
• Lecture 6 (February 11)
  • Hamiltonian cycles, Hamiltonian paths, TSP
  • The ellipsoid algorithm: 7.5
  • Links to the lecture.
• Lecture 7 (February 18)
  • Four handouts of mostly definitions:
    • Linear algebra
    • Affine spaces: 3.4
    • Dimension, polyhedra, and faces: 3.7
    • Extreme points and extreme rays of polyhedra: 3.5
  • LP relaxations of integer optimization problems: 3.8, 3.9, 3.10, 3.11
  • Links to the lecture.
• Lecture 8 (February 22)
  • Gomory cutting planes, an example: 5.2.4
  • Valid inequalities and Chvatal-Gomory rounding: 5.2
  • Another example of Gomory cutting planes: 5.2.4
  • Chvatal-Gomory rank: 5.2.2
  • Links to the lecture.
• Lecture 9 (February 25)
  • Gomory cutting planes for matching: 5.2.4
  • Gomory's cutting plane algorithm: 5.2.5
  • Cuts for mixed integer programs: 7.3
  • The Gomory mixed integer cut: 5.1.4
  • An example of a flow cover constraint: 7.3
  • Links to the lecture.
• Lecture 10 (March 1)
  • Node packing problems: 2.4.1, 2.4.2
  • Proving dimension of faces: 3.9, especially example 3.28
  • Odd hole constraints for node packing
  • Lifting inequalities: 7.2
  • Links to the lecture.
• Lecture 11 (March 4)
  • The MaxCut problem: 2.4.4
  • Facet defining inequalities for MaxCut: (Deza & Laurent, Facets for the cut cone I, Mathematical Programming 56: 121-160, 1992)
  • Separation routine for MaxCut
  • Links to the lecture.
• Lecture 12 (March 8)
  • Satisfiability: 2.5 (see, for example, ppt by Bram van Heuveln)
  • Knapsack: 7.1.
  • Linear ordering: (Grötschel, Jünger, Reinelt, A cutting plane algorithm for the linear ordering problem, Operations Research, 32, 1195-1220, 1984.)
  • Clustering: (references in handouts)
  • Links to the lecture.
• Lecture 13 (March 11)
  • Christofides heuristic for the traveling salesman problem: (Papadimitriou and Steiglitz, 17.2)
  • k-change for the TSP: (Papadimitriou and Steiglitz, 19.2)
  • Polyhedral theory for the TSP: 7.4
  • Links to the lecture.
• Lecture 14 (March 15)
  • Disjunctive cuts: 2.11, 4.9, 5.4
  • Cut generation LP for binary case: 5.1
  • Cut generation LP in general case: 5.1 ( Balas and Perregaard, Discrete Applied Math 123, pages 129-154, 2002)
  • Links to the lecture.
• Lecture 15 (March 18)
  • Simple cuts
  • Sequential convexification: 5.4, 10.2.3 (references in the handouts)
  • Total unimodularity: 4.2, 4.6
  • Perfect graphs 2.4, Chapter 4
  • Links to the lecture.
• Lecture 16 (March 22)
  • Branching: 1.2
  • Branch-and-bound: 1.2.1
  • Branch-and-cut: 1.2.3
  • Links to the lecture.
• Lecture 17 (March 25)
  • Options in branch and bound: 9.2. Also handed out were some computational results from a paper by Achterberg, Koch, and Martin.
  • Primal heuristics: 9.2
  • Symmetry: 9.3
  • Links to the lecture.
• Lectures 18 and 20 (March 29 and April 5)
  • SDP formulation of MaxCut: 10.2.1
  • Goemans-Williamson heuristic for MaxCut: 10.2.1
  • SDP for node packing (Lovasz theta): 10.2.2
  • Links to the lecture.
• Lecture 21 (April 8)
  • SDP duality: (Conforti, Cornuejols, Zambelli, 10.1)
  • Examples of SDP duals: (Conforti, Cornuejols, Zambelli, 10.1)
  • Conic optimization: (Conforti, Cornuejols, Zambelli, 10.1)
  • CVX.
  • Links to the lecture.
• Lecture 22 (April 12)
  • SDP relaxations of quadratic binary programs
  • Completely positive programs
  • Links to the lecture.
• Lecture 23 (April 15)
  • Lagrangian relaxation: 8.1
  • The Held-Karp relaxation for the TSP: 8.1.1
  • Links to the lecture.

Notes from 2019:

These are typed pdf files. The notes are also available on LMS. Section numbers refer to the text Nemhauser and Wolsey.

• Lecture 23
  • Notes on Lagrangian relaxations: handout, slides, ipad (second proof of convexity corrected) (II.5.4)
  • An example of a cutting plane algorithm to solve a Lagrangian dual: handout, slides, ipad
  • Two examples of Lagrangian relaxation: handout, slides, ipad (references in the handouts)
  • Benders decomposition: handout, slides, ipad (II.3.7, III.5.4)
  • An example of Benders decomposition: handout, slides, ipad (II.3.7, III.5.4)
• Lecture 24
  • Logical Benders for scheduling problems: handout, slides, ipad (references in the handouts)
  • Logical Benders for problems with complementarity constraints: handout, slides, ipad (references in the handouts)
  • The Quadratic Assignment Problem: handout, slides, ipad (references in the handouts)
  • AMPL code for a Benders example: model file, data file, run file, output.
  • Slides from a 2017 talk on logical Benders for problems with complementarity constraints, based on this paper.
• Lecture 25
  • Crew scheduling problems: handout, slides, ipad (Conforti, Cornuejols, Zambelli, 2.4.5)
  • Branch-and-price: handout, slides, ipad (Conforti, Cornuejols, Zambelli, 8.2.3)
  • The cutting stock problem: handout, slides, ipad (Conforti, Cornuejols, Zambelli, 2.3, 8.2.1)
  • Integer solutions to the cutting stock problem: handout, slides, ipad (Conforti, Cornuejols, Zambelli, 2.3, 8.2.1)
• Lecture 26
  • Integer quadratic programs: handout, slides, ipad (references in handouts}
  • Mixed integer nonlinear programming: handout, slides, ipad
  • Mixed integer nonlinear programming algorithms: handout, slides, ipad
• Lecture 27
  • Introduction to stochastic integer programs: handout, slides, ipad (references in handouts}
  • AMPL files for stochastic server location problem: model file, data file, run file
  • The L-shaped method: handout, slides, ipad
  • Alternatives to expectation: handout, slides, ipad

Handouts:

• Linear algebra. (Handed out in Lecture 7.)
• Affine spaces. (Handed out in Lecture 7.)
• Dimension, polyhedra, and faces. (Handed out in Lecture 7.)
• Extreme points and extreme rays of polyhedra. (Handed out in Lecture 7.)

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.