back to the top
back to the top
back to the top
back to the top
back to the top
back to the top
back to the top
back to the top
Review
of primal and dual simplex methods, with emphasis on re-optimization after the
addition of violated cuts. Course Description
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. Branch-and-bound
and enumeration. Driebeck penalties.
0-1 knapsack problems. Their LP solutions. BB. Cover inequalities.(-------X------)
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. (-------X------)
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.
Lifting, covers, lifted covers.
(----X----) 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
(--------------)
Total unimodularity. Relationship with integer feasible solutions for integer programming problems. Special cases of network flow problems.
(----X----) 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. (----X----). Relaxations. Surrogate
relaxation and surrogate duals (----X----).
Applications:
airline crew scheduling, lotsizing, facility location, production scheduling... (throughout the semester). ~~~~~~~~~ 
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 2009, Wednesdays 4:30-7:30 PM, 1203, SHDH
Professor Monique Guignard-Spielberg
New this week: (27 April 2009)
We will finish looking at Gomory's mixed-integer cuts.
We will look at
the RLT applied to the GQAP.
We will also have a look at
Branch-and-Cut and
probing.
New this week: (20 April 2009)
We will continue our study of Dantzig and Wolfe decomposition.
We will then look at Gomory cuts, and modeling of SPLP, CPLP and lotsizing.
New this week: (13 April 2009)
Suggested readings
1. (an interesting use of IP!):
look at the following
webpage
and the associated
paper.
Notice:
this could also serve as a project topic.
2. useful advice (even for the non-military!)
look at the following
paper.
3. Finally this is a 1973
paper by Chvatal republished in 2006, dealing with the "Gomory-Chvatal" algorithm.
Course material.
Monday's class.
We first study a real application to tile manufacturing that uses Lagrangean relaxation and makes use of the integer linearization property, even though there is more than one 0-1 variable in each equation. You can find information in the
TOP paper, on p. 163-166.
We will study surrogate duality.
Suggested reading (an alternate method when the subgradient algorithm does not work well):
the
paper by Barahona and Anbil describes the volume algorithm.
Wednesday's class.
We will look at column generation. Files to download:
file 1 and
file 2.
Later on, we will look at
branch-and-cut and
probing.
New this week: (7 April 2009)
We will go back over valid inequalities, in particular covers, extended covers and lifted covers, and facets.
We will then start looking at surrogate constraints.
New this week: (30 March 2009)
Classnotes.
(1)
Benders partitioning by Erwin Kalvelagen.
(2)
Chvatal-Gomory approach to valid inequalities.
Readings.
Geoffrion's paper on Lagrangean relaxation.
on Balas .
on Gomory .
Possible projects.
(1) chapter 5 of the thesis of Absi, in French, with a
description in English.
(2) survey of noncommercial MIP software.
(3) Johnson, L., M. Kostreva, U. Suhl, (1985), "Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models",
Operations Research 33, 803-819.
(4) Fischetti, M., A. Lodi (2003), "Local Branching", Math. Pr. 98, pp. 23-47.
If you like the topic, please read the section under study,
and send me a short proposal for research based on the paper.
Homework 3:
1.
Write a program to check total unimodularity of an arbitrary (mxn) matrix A in the programming language of your choice.
Apply it to the two examples treated in class.
2.
Explain why it is legitimate to add that the sum over i of the u(i) must remain less than or equal to M in Benders partitioning method.
3. In the textbook "Integer Programming" by Garfinkel and Nemhauser, do problem 24 on p. 151.
If you do not have access to the texbook,
p.210 # 22,
and
p.207 #2
are necessary for having the whole contents of HW 3.
New this week: (23 March 2009)
We will start studying Benders partitioning, as discussed in Garfinkel and Nemhauser.
New this week: (17 March 2009)
We will cover the total unimodularity of constraint matrices as presented in Garfinkel and Nemhauser.
New this week: (2 March 2009)
Homework:
1. show that the subdifferential of f at x, f convex, is convex.
2. show that the subdifferential of f at x, f convex, is closed.
3. show that b-Ax(k) is a subgradient of z(lambda) for lambda=lambda(k).
New this week: (15 January 2009)
General Information
back to the top
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
Phone: 215-898-8235
Email: guignard_monique at yahoo.fr
URL: http://opim.wharton.upenn.edu/~guignard
Office Hours: By appointmentTextbook
back to the top
Course Syllabus
Class Notes
back to the top
Grading Policy
back to the top
Homework
Homework #1, due -----.
Homework #2, due -----.
Homework #3, due -----.
Homework #4, due -----.
Homework #5, due -----.
back to the top
Term Projects
You may also look at the following link.
back to the top