Combinatorial Optimization and Integer
MATP6620 / ISYE6760
- Scores on the first five homeworks
and the midterm.
Some books are
in the library.
You can borrow the materials for up to an hour.
Further, you can borrow the books overnight
if you check them out less than an hour before
time and return them early the following day.
In class on Friday, April 19.
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 5.
Some old exams
Solutions to midterm.
The remaining presentations will take place on
Friday May 17, from 3-6pm, in Troy 2012.
The presentations should be no more than 12 minutes long.
There will be 13 presentations.
The order of the presentations will be determined on the day.
You should prepare 20 copies of your slides to hand out in advance.
Send me an electronic version of your slides.
- Please ask questions during the presentations.
I will award bonus points for good questions;
I will not deduct points for difficulties in answering questions from students.
Your writeup is due on May 15.
Your report should be about 5-10 pages long.
It must be typewritten: send me an electronic copy as a pdf file.
It should describe the problem you worked on,
what you did to solve the problem, and the significance of what you did.
You should also cite relevant references and state what was novel about
For group projects, also hand in one sheet from each group member
discussing his or her individual contribution.
(Handwritten notes, not the most legible in places.)
Polyhedral theory and cutting planes:
- Introduction to NP-completeness.
- Lecture 3, Jan 29: Pages 1-10.
- Lecture 4, Feb 1: Pages 11-14.
- NP-completeness reductions: Hamiltonian cycle.
For a nice presentation of the reduction of 3-SAT to Hamiltonian cycle,
this link (pdf).
- Lecture 4, Feb 1: Pages 1-10.
- Lecture 5, Feb 5: Page 11.
- NP-completeness: node packing, knapsack, linear programming.
- Lecture 4, Feb 1: Pages 1-3.
- Lecture 5, Feb 5: Pages 4-14.
- Polynomial equivalence of separation and optimization.
- Lecture 5, Feb 5: Pages 1-4.
Branch and bound:
Mixed integer nonlinear programming.
- Introduction to polyhedral theory.
(See also the four typewritten handouts from February 8.)
- Lecture 6, Feb 8: Pages 1-10.
- Lecture 6, Feb 8: Pages 1-3.
- Lecture 7, Feb 12: Pages 4-10.
- Chvatal-Gomory rounding.
- Gomory's cutting plane algorithm.
- Mixed integer programming, including Gomory's mixed integer cut.
- Lecture 9, Feb 22: Pages 2-3.
- Lecture 10, Feb 26: Pages 4-6.
- Lecture 15, Mar 22: Pages 1, 7-8.
- Maxcut problems and linear ordering problems.
See also the handout on the
for finding violated constraints for MAXCUT problems.
- Lecture 10, Feb 26: Pages 4-7.
- Lecture 11, Mar 1: Pages 1-3.
- Node packing. Lifting.
- Lecture 11, Mar 1: Pages 1-5.
- Lecture 12, Mar 5: Pages 6-9.
- Knapsack problems and satisfiability problems.
- Lecture 12, Mar 5: Pages 1-3.
- 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.
contains a discussion of approximation algorithms for the TSP.
- Lecture 13, Mar 8: Pages 1-10.
- Lift and project, and disjunctive cuts.
- Lecture 14, Mar 19: Pages 1-9.
- Lecture 15, Mar 22: Pages 10-11.
- Total unimodularity.
- Lecture 16, Mar 22: Pages 1, 3, and 4.
- Lecture 17, Mar 29: Pages 2 and 5.
- Perfect graphs.
- Lecture 17, Mar 29: both pages.
See also a handout on the
job shop scheduling OPL example
from an Interfaces paper by Lustig and Puget,
Trick's powerpoint presentation on
Other approaches using linear programming:
Papers and resources:
Most of these pointers do not lead to sites at RPI.
Two libraries of MINLP problems:
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.
Integrating SQP and branch-and-bound for mixed integer
Computational Optimization and Applications 18, 2001,
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,
Appeared in Interfaces
32(3), pages 30-61, 2002.
Can be downloaded via the library website.
- The P=NP conjecture is one of the
A problem based on
PRIMES is in
P; see also
columns by David S. Johnson.
Survey papers on
cutting plane algorithms,
regarding cutting plane methods for the TSP.
Here is a page on the
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
The website also includes the downloadable software
Two further references for this problem are
page on the TSP.
Instances of TSP can be obtained from the
Hamilton called the problem of finding a route through the vertices
of a icosahedron the
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
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.
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
Also available from the same site is
a library of linear descriptions of polytopes of small instances of
various integer programming problems.
Materials for Combinatorial Optimization, maintained by
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
It is capable of solving linear, nonlinear, and integer programs.
Here is local information about AMPL,
including information about using it on RCS.
You can download the
of the book.
A survey paper on
A survey paper on
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
algorithms (volume 9, number 3 of INFORMS Journal on Computing, by
A survey paper on
The semidefinite programming
homepage maintained by
A survey paper by
Mike Todd on
programming, with an emphasis on algorithms.
(Acta Numerica 10 (2001), pp. 515-560.)
A survey paper by
programming in combinatorial optimization.
(Mathematical Programming, 79 (1997), pages 143-161.)
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.
compendium of approximability results for NP optimization problems.
Some papers on the
approximation by Sanjeev Arora.
Back to John Mitchell's homepage