# 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, 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.

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

### 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