Integer and Combinatorial Optimization
Spring 2021
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.
Projects
Homeworks:
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.
- Lecture 23
- Notes on Lagrangian relaxations:
handout,
slides,
ipad
(second proof of convexity corrected)
(II.5.4)
- An example of a cutting plane algorithm to solve a Lagrangian dual:
handout,
slides,
ipad
- Two examples of Lagrangian relaxation:
handout,
slides,
ipad
(references in the handouts)
- Benders decomposition:
handout,
slides,
ipad
(II.3.7, III.5.4)
- An example of Benders decomposition:
handout,
slides,
ipad
(II.3.7, III.5.4)
- Lecture 24
- Logical Benders for scheduling problems:
handout,
slides,
ipad
(references in the handouts)
- Logical Benders for problems with complementarity constraints:
handout,
slides,
ipad
(references in the handouts)
- The Quadratic Assignment Problem:
handout,
slides,
ipad
(references in the handouts)
- 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.
- Lecture 25
- Crew scheduling problems:
handout,
slides,
ipad
(Conforti, Cornuejols, Zambelli, 2.4.5)
- Branch-and-price:
handout,
slides,
ipad
(Conforti, Cornuejols, Zambelli, 8.2.3)
- The cutting stock problem:
handout,
slides,
ipad
(Conforti, Cornuejols, Zambelli, 2.3, 8.2.1)
- Integer solutions to the cutting stock problem:
handout,
slides,
ipad
(Conforti, Cornuejols, Zambelli, 2.3, 8.2.1)
- Lecture 26
- Lecture 27
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 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.
Back to John Mitchell's homepage
|
RPI Math
|
ISYE