ADM III: Computational Mixed Integer Programming - WS 2007/08
|
|---|
"This optimization problem is NP-hard, so we cannot solve it!"
How often did I hear that sentence, and how often did I ask myself the
question why people think this could be true?!"
It is one
of the aims of this course to convince you that NP-hard
optimization problems
have to be solved, and more importantly, they can be
solved!
This course is a third in the algorithmic discrete
mathematics (ADM) series (for Bachelor/Master students, this
is a "Vertiefende Lehrveranstaltung Algorithmische Diskrete
Mathematik" module). We are concerned with how to actually solve
large-scale mixed integer programming problems to optimality or proven
near-optimality. Problems considered will be from industrial practice
as well as from within discrete mathematics and computer science.
Contents include (as of Febraury 2008, suggestions very welcome!):
- modeling power of binary and integer variables
- modeling languages such as zimpl and gams
- MIPs from theory and practice
- branch-and-bound, branch-and-cut, branch-and-price, branch-and-...
- MIP solvers: preprocessing, branching, primal heuristics,
parameters, etc.
- decomposition approaches like Lagrangian relaxation, column generation
- pitfalls (and how to avoid them)
- ...
You need to have participated in a "linear and integer programming"
course (ADM2) [there is such a
course given by Martin Skutella
in winter term 07/08!]. We will have accompanying
computer exercises; Timo
Berthold will share his experience with us. Familarity with Java, or (much!) better C/C++ is
recommended.
This ADM3 course takes place as a two week block course: March
25, 2008 - April 4, 2008 (whole days, 9.15-18.00, excluding the weekend, equivalent
to 3 hours lecture, and 1 hour exercises).
If requested the lectures will be given in English.
Termine für Rücksprachen sind 23./24. April 2008, jeweils
13-16h; bitte mit Timo Termine ausmachen.
A forum for quick communication is up and running. Please register.
Just show up on
March 25, in MA005 at 9.15. No registration needed.
You may wish to bring your own laptop, if you own one. Some people
asked me, how to best prepare for the course. You may
install (and play a little bit with) SCIP and gams; you will find
documentation and free downloads on these pages. This is not mandatory,
but may be helpful to get started. We will use this software in
the course. You should not need any further reading, except an
ADM2.
If you have questions relating the installation of the ZIB
optimization suite, please email Timo
Berthold.
Several people asked about credit points. As most of you are the first
Bachelor students, we are still in the process of writing e.g.,
an official Modulbeschreibung (soon). At this time, we
cannot say anything definitive about credit points.
Dates and lecture hall are fixed:
March 25, 2008 - April 4, 2008 in MA005, 9.15 - 18.00?.
The date for the kickoff meeting is fixed now: October 18, 2007,
18.00h in room MA645.
There is a forum to exchange comments, problems,
solutions, ... Feel free to register and contribute.
| Echalk Lecture Notes and Further Material |
|---|
Here is our "reduced" version of ZIB's OptSuite: zibsuboptsuite-1.00.tgz.
Unpack the gezipped tar with tar zxf zibsuboptsuite-1.00.tgz;
change into the directory zibsuboptsuite-1.00, and
simply say make. If your kid is complete, the compilation
runs without any error messages. Then type make test to
verify that everything is correct.
Lecture Notes:
weekend... :-)
- 31.3.08: lecture (relaxations, simplex, column generation) color, b/w; programming exercise
(presolve)
- 1.4.08: lecture (Lagrange relaxation, Dantzig-Wolfe
decomposition, branch-and-price) color, b/w; programming exercise
(column generation for bin packing)
Here is binpacking.tgz.
- 2.4.08: lecture (anatomy of column generation) color, b/w;
example;
exercise (ZIMPL) color, b/w; programming exercise
(ZIMPL)
- 3.4.08: lecture (cutting planes) color, b/w; exercise: on paper
and blackboard!
- 4.4.08: lecture (current research topics, conclusions, outlook)
color, b/w; summary
color, b/w
Articles (in chronological order of interest for the course)
general interest, branching rules, node selection (also cutting
planes):
- A. Fügenschuh and A. Martin.
Computational Integer Programming and Cutting Planes.
In: Handbooks in Operations Research and Management Science,
12. North-Holland, 2005.
PDF
- J.T. Linderoth and
M.W.P. Savelsbergh.
A computational study of search strategies for mixed integer
programming.
INFORMS Journal on Computing: 11(2), 173-187, 1999.
PDF
- T. Achterberg, T. Koch, and A. Martin.
Branching rules revisited.
Operations Research Letters: 33, 42-54, 2005.
PDF
- T. Achterberg.
Constraint Integer Programming.
Ph.D. thesis, TU Berlin, 2007.
PDF
primal heuristics:
- M.Fischetti, F.Glover, and A.Lodi.
The feasibility pump.
Mathematical Programming: 104(1), 91-104, 2005.
PDF
- T.Achterberg and T.Berthold.
Improving the feasibility pump.
Discrete Optimization: 4(1), 77-86, 2007.
PDF
- M.Fischetti and A.Lodi.
Local branching.
Mathematical Programming: 98(1-3), 23-47, 2003.
PDF
- E. Danna, E. Rothberg, and C. Le Pape.
Exploring relaxation induced neighborhoods to improve MIP
solutions.
Mathematical Programming: 102(1), 71-90, 2005.
PDF
- T. Berthold.
Primal Heuristics for Mixed Integer Programs.
Diploma thesis, TU Berlin, 2006.
PDF
presolving:
- A.L. Brearley, G. Mitra, and H.P. Williams.
Analysis of mathematical programming problems prior to applying the
simplex algorithm.
Mathematical Programming: 8(1), 54-83, 1975.
PDF
- M.W.P. Savelsbergh.
Preprocessing and probing techniques for mixed
integer programming problems.
ORSA Journal on Computing: 6,
445-454, 1994.
PDF
relaxations; Lagrangean relaxation, Dantzig-Wolfe decomposition,
column generation:
- A.M. Geoffrion.
Lagrangean relaxation for integer programming.
Mathematical Programming Study: 2, 82--114, 1974.
PDF
- J.Desrosiers and M.E.Lübbecke.
A primer in column generation.
In Column Generation, G.Desaulniers,
J.Desrosiers, and M.M.Solomon (Eds.), Springer, 2005, pp.1-32.
PDF
- M.E.Lübbecke and J.Desrosiers.
Selected topics in column generation.
Operations Research 53(6): 1007-1023, 2005.
PDF
- C.Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P.Savelsbergh, and P.H.Vance.
Branch-and-price: Column generation for solving huge
integer programs.
Operations Research 46(3): 316-329, 1998.
PDF
-
O. du Merle, D. Villeneuve, J. Desrosiers, and P.Hansen.
Stabilized column generation.
Discrete Mathematics: 194(1), 229-237, 1999.
PDF
cutting planes:
- E.Balas, S.Ceria, G.Cornuéjols, and N.Natraj.
Gomory cuts revisited.
Operations Research Letters: 19(1), 1-9, 1996.
PDF
current and future research topics:
Books
- Integer and Combinatorial Optimization.
L.A. Wolsey and G.L. Nemhauser.
Wiley, 1988.
- Optimization Theory for Large Systems.
L.S. Lasdon.
Dover Publications, 2002.
- Column Generation.
G.Desaulniers,
J.Desrosiers, and M.M.Solomon (Eds.), Springer, 2005.
- The Traveling Salesman Problem:
A Computational Study.
D.L. Applegate, R.E. Bixby, V. Chvátal, and W.J. Cook, Princeton University Press, 2006.
- Computational Combinatorial Optimization.
M.Jünger and D. Naddef,
Lecture Notes in Computer Science 2241, Springer, 2001.
Software
- SCIP, MIP solver available in
source code, see in particular the SCIP Workshop
2007
- CPLEX and XPRESS-MP,
state-of-the-art commercial MIP solvers
- GAMS, a general
algebraic modeling system
- Zimpl, an open source modeling language
Last modified: Mon Apr 7 18:12:04 CEST 2008
Marco Lübbecke <m.luebbecke@math.TU-Berlin.DE>
|