Week | Topics and Slides | Resources |
---|---|---|
14 | Introduction. | [GRB], |
LP Practical Guidelines, Interior Point Methods, Sifting | [KN1], [HL, sc 8.4], [BGLMS, sc 3] | |
Practice | Sheet 1; Sol | |
15 | MILP Practical Guidelines, Modeling, Presolving | [KN2], [ABGRW], [Wi, ch7,9,10] or [GRB modeling] |
MILP Formulations for Traveling Salesman Problem, Cutting Planes for TSP | [P] or [DFJ] or [MTZ] or [A] or [ABCC] or [OAL] | |
Practice TSP | Sheet 2; [GIT] | |
16 | More on TSP | Sheet3; Sol |
Lagrangian Relaxation for MILP | ||
Implementation, LR for TSP | ||
17 | Vehicle Scheduling | |
Exercises | ||
Dantzig Wolfe decomposition | ||
18 | Vehicle Routing: Compact models; Set Partitioning formulation and CG | |
Vehicle Routing: Cutting and Branching | ||
Exercises on Column Generation | ||
19 | Crew Scheduling; RCSP | |
Benders Decomposition | ||
20 | Cut-and-Solve | |
21 | Timetabling | |
Timetabling | ||
[KN1] Ed Klotz, Alexandra M. Newman. Practical guidelines for solving difficult linear programs Surveys in Operations Research and Management Science, 18 (1–2) (2013), pp. 1-17
[HL] Frederick S Hillier and Gerald J Lieberman, Introduction to Operations Research, 9th edition, 2010. ISBN: 0073376299
[BGLMS] Bixby, R. E., Gregory, J. W., Lustig, I. J., Marsten, R. E., & Shanno, D. F. (1992). Very large-scale linear programming: A case study in combining interior point and simplex methods. Technical Report 91-11 (Also in Operations Research, 40(5), 885.)
[KN2] Ed Klotz Alexandra M. Newman. Practical guidelines for solving difficult mixed integer linear programs Surveys in Operations Research and Management Science Volume 18, Issues 1–2, October 2013, Pages 18-32
[ABGRW] Tobias Achterberg, Robert E. Bixby, Zonghao Gu, Edward Rothberg, Dieter Weninger Presolve Reductions in Mixed Integer Programming INFORMS Journal on Computing, 32(2), 2020 (preprint available as ZIB-Report 16-44)
[Wi] H.P. Williams. Model building in mathematical programming. John Wiley & Sons, Chichester, Fifth Edition, 2013
[A] David L. L. Applegate, Robert E. E. Bixby, Vasek Chvátal, William J. J. Cook. The traveling salesman problem: a computational study. 2006
[ABCC] David Applegate, Robert Bixby, Vasek Chvatal, William Cook. Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems. Mathematical Programming, Series B. 97. 2003
[DFJ] G. Dantzig, R. Fulkerson and S. Johnson. Solution of a Large-Scale Traveling-Salesman Problem. Journal of the Operations Research Society of America, Vol. 2, No. 4 (Nov., 1954), pp. 393-410
[P] Gabor Pataki. Teaching Integer Programming Formulations Using the Traveling Salesman Problem SIAM Review 45(1), 2003
[MTZ] C. E. Miller, A. W. Tucker, R. A. Zemlin Integer Programming Formulation of Traveling Salesman Problems Journal of the ACM. 7(4), 1960
[OAL] Temel Öncana, I. Kuban Altınelb, Gilbert Laporte. A comparative analysis of several asymmetric traveling salesman problem formulations Computers & Operations Research 36 (2009)
[RM] PySCIPOpt: Python Interface to the SCIP Optimization Suite. Reference Manual; SCIP Parameters