Refresh to update time/temperature in Philadelphia, click for forecast:
back to the top
HOME Course Description Prof. Monique Guignard-Spielberg
General -- New this week -- Syllabus -- Textbook -- Class Notes -- Homework -- Grading-- Exam-- Handouts -- Projects -- Links -- Historical perspectives
Department of OPIM
OPIM-916: Advanced Integer Programming
Spring 2016, WED 3:00-6:00 PM, JMHH F88
Professor Monique Guignard-Spielberg
Many optimization models include either integer or 0-1 decision variables. The integrality requirements make the problems much harder to solve than the corresponding continuous optimization problems. The course will provide students with a variety of analytical and algorithmic tools for approaching such hard problems. Emphasis will be on modeling, as well as on approximate (heuristic), and exact (iterative and enumerative) methods.
Office: 569 JMHH
Email: guignard_monique at yahoo.fr
Office Hours: By appointment
back to the top
Prof. Monique Guignard-Spielberg
The textbook used is “Integer Programming”, by L. Wolsey, Wiley, 1998.
Additional reading material will be distributed during the semester.
List of topics to be covered:
Course overview. Examples of problems with large integrality gaps, and with feasible rounded solutions yielding large relative gaps (?????)
Review of LP duality, and of the primal and dual simplex methods, with emphasis on re-optimization after the addition of violated cuts. The dual simplex method for LPs with upper bounds. Reading another reading (please don't hesitate to click on "short description"! (????)
Branch-and-bound and enumeration. Driebeck penalties. (?????)
0-1 knapsack problems. Their LP solutions. BB. Cover inequalities.(???????)
For this section, download the following tutorial. Primal relaxation and Lagrangean relaxation, geometric interpretation, integrality property. Integer linearization property, application to the capacitated p-median problem. Analysis of Lagrangean relaxation schemes and quality of bounds from the viewpoint of the geometric interpretation. Application to the GAP and review of all possible constraint dualizations. Integer linearization property for the capacitated facility location problem when the demand constraint is dualized. The bi-knapsack problem. Construction of the Lagrangean function for the total Lagrangean relaxation. Integrality property. Properties of the Lagrangean function. Examples. Contours, subgradient method. Convex nondifferentiable functions and subgradients. (??????)
Dantzig-and-Wolfe decomposition algorithm, solution of the Lagrangean dual by column generation: example of the multi-item capacitated lotsizing problem and the GAP. Extensions of Lagrangean relaxation: Lagrangean decomposition and substitutions. Examples. (???????)
Valid inequalities. Chvatal-Gomory procedure. (???????)
Linear programming relaxation and Gomory cuts for pure and mixed-integer problems. (Pure: ???????)
Lifting, covers, lifted covers. (???????)
Modeling integer programming problems: choice of decision variables and of constraints, simple strengthening techniques. Examples: SPLP, CPLP, lotsizing, with and without disaggregation. Integrality gaps. Model tightening (see paper ). (throughout the semester)
Variable fixing, cliques and implication tables, probing. see paper (reading)
Total unimodularity. Relationship with integer feasible solutions for integer programming problems. Special cases of network flow problems. (???????)
Benders partitioning for mixed-integer problems. Examples. Initialization. Gams coverage of Benders. Benders inequalities of types I and II, obtained from simplex tableau and their use outside of the partitioning algorithm. Special examples with and without dual extreme rays. (???????).
Relaxations. Surrogate relaxation and surrogate duals (???????).
Applications: airline crew scheduling, lotsizing, facility location, production scheduling... (throughout the semester).