# Integer and Combinatorial Optimization

## 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,4,5 plus the midterm, for those who submitted all homeworks, out of 360:
348 345 340 329 320 315 314 311 310 304 303 300 297 294 279 279 256 237

### Midterm Exam:

Here are some old exams.

### Notes from 2021:

These are typed pdf files. The notes are available on LMS and rpi.app.box.com. Section numbers refer to the text by Conforti et al.
• 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)
• 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.
• Lecture 24 (April 19)
• 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 25 (April 22)
• Benders decomposition: 8.3
• Logical Benders for scheduling problems: (references in the handouts)
• Logical Benders for problems with complementarity constraints: (references in the handouts)
• Integer quadratic programs: (references in handouts)
• Not covered:
• Links to the lecture.
• Lecture 26 (April 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 (April 29)
• The Quadratic Assignment Problem: (references in the handouts)
• Mixed integer nonlinear programming:
• Mixed integer nonlinear programming algorithms:
• Links to the lecture.
• Lecture 28 (May 3). No lecture, just office hours at the usual time.

### Notes from 2019:

(Handwritten notes and the schedule from Spring 2017 are available here.)

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

### Papers and resources:

Most of these pointers do not lead to sites at RPI.

Back to John Mitchell's homepage | RPI Math | ISYE