# Integer and Combinatorial Optimization

## MATP6620 / ISYE6760

### Midterm Exam:

Here are some old exams.

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

These are typed pdf files. The notes are available on LMS. Section numbers refer to the text by Conforti et al.
• Lecture 1
• Introduction: 1.1, 1.2
• The traveling salesman problem: 2.7
• Knapsack problems: 2.1
• Facility location problems: 2.10.1
• Lecture 2
• Basic feasible solutions: 3.3
• The simplex algorithm
• An example of simplex
• Motivation for the dual problem
• Constructing the dual problem
• 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:
• 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
• Lecture 5
• Algorithm complexity: 1.3
• NP: 1.3
• Node packing
• Lecture 6
• Hamiltonian cycles, Hamiltonian paths, TSP
• The ellipsoid algorithm: 7.5
• 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
• 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
• 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
• 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
• 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
• 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)
• 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
• 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)
• 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
• Lecture 16
• Branching: 1.2
• Branch-and-bound: 1.2.1
• Branch-and-cut: 1.2.3
• Lecture 17
• 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
• Lecture 20
• SDP duality: (Conforti, Cornuejols, Zambelli, 10.1)
• Examples of SDP duals: (Conforti, Cornuejols, Zambelli, 10.1)
• CVX.
• Lecture 21
• Conic optimization: (Conforti, Cornuejols, Zambelli, 10.1)
• SDP relaxations of quadratic binary programs
• Completely positive programs
• Lecture 22
• Lagrangian relaxation: 8.1
• The Held-Karp relaxation for the TSP: 8.1.1
• 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)
• 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:
• 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)