Integer and Combinatorial Optimization
Spring 2023
MATP6620 / ISYE6760
Course basics:
Midterm Exam:
Here are some
old exams.
Projects
Homeworks:
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
 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 ChvatalGomory rounding: 5.2
 Another example of Gomory cutting planes: 5.2.4
 ChvatalGomory 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: 121160, 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, 11951220, 1984.)
 Clustering:
(references in handouts)
 Links to the
lecture.
 Lecture 13
 Christofides heuristic for the traveling salesman problem:
(Papadimitriou and Steiglitz, 17.2)
 kchange 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 129154, 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
 Branchandbound:
1.2.1
 Branchandcut:
1.2.3
 Links to the
lecture.
 Lecture 17
 Lecture 18
 SDP formulation of MaxCut:
10.2.1
 GoemansWilliamson 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 HeldKarp 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:
 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)
 Branchandprice:
(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
Handouts:
Papers and resources:
Most of these pointers do not lead to sites at RPI.

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

I. E. Grossmann, Review of Nonlinear Mixed Integer
and Disjunctive Programming Techniques,
Optimization and Engineering 3(3), 2002, pages 227252.

S. Leyffer,
Integrating SQP and branchandbound for mixed integer
nonlinear programming,
Computational Optimization and Applications 18, 2001,
pages 295309.

M. Tawarmalani and N. V. Sahinidis,
Global optimization of mixed integer nonlinear programs:
a theoretical and computational study,
Mathematical Programming 99, 2004, pages 563591.

Tutorial on Computational Complexity,
by
Craig Tovey.
Appeared in Interfaces
32(3), pages 3061, 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 NPcomplete.

PRIMES is in
P; see also
here.
 NPCompleteness
columns by David S. Johnson.

Survey papers on
cutting plane algorithms,
branchandbound,
and
branchandcut.

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. 515560.)

A survey paper by
Michel Goemans
on
semidefinite
programming in combinatorial optimization.
(Mathematical Programming, 79 (1997), pages 143161.)
 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.
Back to John Mitchell's homepage

RPI Math

ISYE