Integer and Combinatorial Optimization

Spring 2023

MATP6620 / ISYE6760

Course basics:

• Course outline.
• Grades, software, notes, and other material will be posted on LMS.
• We will be using piazza this semester to answer questions. The signup page for piazza is here: MATP 6620 piazza signup.
• Office hours: Tuesday 2-4pm in AE 325. Thursday 3-4pm, See updated office hours here: office hours. On webex, https://rensselaer.webex.com/meet/mitchj

Midterm Exam:

Here are some old exams.

Projects

• Some past projects.

Homeworks:

• Homework 1, due January 24. 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.
• Homework 2, now due February 8.
• Homework 3, due February 21. Some past projects.
• Homework 4, now due March 17.

Notes from 2021:

• Lecture 1
  • 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
  • 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; follow the link to Box to get the notes.
• Lecture 3
  • Duality theorems: 3.3
  • Multiple optimal solutions:
  • Links to the lecture.
  • For more background on simplex and linear programming, see the course MATP 4700; follow the link to Box to get the notes.
• Lecture 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
  • Algorithm complexity: 1.3
  • NP: 1.3
  • Node packing
  • Links to the lecture.
• Lecture 6
  • Hamiltonian cycles, Hamiltonian paths, TSP
  • The ellipsoid algorithm: 7.5
  • Links to the lecture.
• Lecture 7
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • Branching: 1.2
  • Branch-and-bound: 1.2.1
  • Branch-and-cut: 1.2.3
  • Links to the lecture.
• Lecture 17
  • 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.
• Lecture 18
  • 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 20
  • SDP duality: (Conforti, Cornuejols, Zambelli, 10.1)
  • Examples of SDP duals: (Conforti, Cornuejols, Zambelli, 10.1)
  • CVX.
  • Links to the lecture.
• Lecture 21
  • Conic optimization: (Conforti, Cornuejols, Zambelli, 10.1)
  • SDP relaxations of quadratic binary programs
  • Completely positive programs
  • Links to the lecture.
• Lecture 22
  • Lagrangian relaxation: 8.1
  • The Held-Karp relaxation for the TSP: 8.1.1
  • Links to the lecture.
• Lecture 23
  • Notes on Lagrangian relaxations: 8.1
  • An example of a cutting plane algorithm to solve a Lagrangian dual: 8.1.2
  • Two examples of Lagrangian relaxation: 8.1 (references in the handouts)
  • Links to the lecture.
• Lecture 24
  • Benders decomposition: 8.3
  • Logical Benders for scheduling problems: (references in the handouts)
  • Logical Benders for problems with complementarity constraints: (references in the handouts)
  • Not covered:
    • 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.
  • Links to the lecture.
• Lecture 25
  • Integer quadratic programs: (references in handouts)
  • The Quadratic Assignment Problem: (references in the handouts)
  • Links to the lecture for the first part.
  • Links to the lecture for the second part.
• Lecture 26
  • Crew scheduling problems: (Conforti, Cornuejols, Zambelli, 2.4.5)
  • Branch-and-price: (Conforti, Cornuejols, Zambelli, 8.2.3)
  • The cutting stock problem: (Conforti, Cornuejols, Zambelli, 2.3, 8.2.1)
  • Integer solutions to the cutting stock problem: (Conforti, Cornuejols, Zambelli, 2.3, 8.2.1)
  • Links to the lecture.
• Lecture 27
  • Mixed integer nonlinear programming:
  • Mixed integer nonlinear programming algorithms:
  • Links to the lecture.
• Lecture 28
  • 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.