Combinatorial Optimization and Integer
Programming
Spring 2015
MATP6620 / ISYE6760
Course basics:
Midterm Exam:
In class on Friday, April 24.
You can bring one sheet of handwritten notes.
(You can write on both sides, the paper can be no larger than 8.5x11 inches).
The exam will cover everything in class up to April 14.
Projects
More information about the final
report and the presentation.
Note: the presentations will now take place in Amos Eaton 214,
from 36pm on March 21.
Homeworks:
Notes:
(Handwritten notes, not the most legible in places.)
Introduction:
Computational complexity
 Introduction to NPcompleteness.
See also some typewritten notes.
 Lecture 3, Feb 3: Pages 110.
 Lecture 4, Feb 6: Pages 1114.
 NPcompleteness reductions: Hamiltonian cycle.
For a nice presentation of the reduction of 3SAT to Hamiltonian cycle,
see
this link
from
Carl Kingsford.
 Lecture 4, Feb 6: Pages 110.
 Lecture 5, Feb 10: Page 11.
 NPcompleteness: node packing, knapsack, linear programming.
 Lecture 4, Feb 6: Pages 13.
 Lecture 5, Feb 10: Pages 414.
 Polynomial equivalence of separation and optimization.
 Lecture 5, Feb 10: Pages 14.
Polyhedral theory and cutting planes:
 Introduction to polyhedral theory.
There is a typewritten version
of most of these notes.
(See also the four typewritten handouts from February 13.)
 Lecture 6, Feb 13: Pages 110.
 Facets.
 Lecture 6, Feb 13: Pages 13.
 Lecture 7, Feb 20: Pages 410.
See also these
typewritten notes
for some of the definitions.
 ChvatalGomory rounding.
See also these
typewritten notes
for some of the definitions.
 Gomory's cutting plane algorithm.
 Mixed integer programming, including Gomory's mixed integer cut.
 Lecture 9, Feb 27: Pages 16.
 Lecture 15, Mar 20: Pages 1, 78.
See also this example of a
flow cover constraint.
 Maxcut problems and linear ordering problems.
 Lecture 9, Feb 27: Pages 45.
 Lecture 10, Mar 3: Pages 67.
See also the handout on the
BarahonaMahjoub routine
for finding violated constraints for MAXCUT problems.
 Lecture 11, Mar 6: Pages 13.
Also available in typewritten form
(although the symbol for "not in" was not converted quite correctly
from the latex).
 Node packing. Lifting.
 Lecture 10, Mar 3: Pages 12.
 Lecture 11, Mar 6: Pages 37.
 Lecture 12, Mar 10: Pages 89.
 Knapsack problems and satisfiability problems.
 Lecture 12, Mar 10: Pages 13.
 The traveling salesman problem.
The Concorde TSP solver is available from
this TSP website
at Georgia Tech.
The website also includes images of TSPs and information about
the history of the TSP.
Optima 90
contains a discussion of approximation algorithms for the TSP.
 Lecture 13, Mar 13: Pages 110.
 Lift and project, and disjunctive cuts.
 Lecture 14, Mar 17: Pages 19.
 Lecture 15, Mar 20: Pages 1011.
 Total unimodularity.
 Perfect graphs.
 Lecture 16, Mar 31: all pages.
Branch and bound:
Semidefinite programming:
Decomposition approaches:
Mixed integer nonlinear programming.
Metaheuristic approaches:
Constraint programming.
See also a handout on the
job shop scheduling OPL example
from an Interfaces paper by Lustig and Puget,
and
Michael
Trick's powerpoint presentation on
constraint programming.
Other approaches using linear programming:
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