Elif Garajová

Integer Programming

The tutorial is scheduled on Thursday at 10:40 in S221 (corridor on the 2nd floor). If you have any questions, you can reach me via e-mail at elif@kam.mff.cuni.cz.

Homework

• Credit for the tutorial will be awarded for obtaining at least 50 % of the points in each set of homework problems.
• There will be 5 sets of problems on:
• The art of formulating integer programs [deadline: 16. 3.]
• Theory: Integer polyhedra, unimodularity, complexity [deadline: 6. 4.]
• Methods for solving integer programs [deadline: 20. 4.]
• Heuristics, decompositions and software [deadline: 4. 5., extended deadline: 18. 5. for Problem 4.2]
• Special cases: Knapsack, TSP and others [deadline: 18. 5.]

Schedule of the Tutorials

02.03.2023

Formulating integer linear programs.

• Exercises and Solutions [in Czech]

16.03.2023

Integer polyhedra. (Totally) unimodular matrices. Complexity of integer programming.

• Exercises and Solutions [in Czech]

06.04.2023

Methods for solving integer programs: Cutting planes and Branch-and-bound.

• Exercises and Solutions [in Czech]

20.04.2023

Heuristics, decompositions and column generation methods. Software for solving integer programs.

• Exercises and Solutions [in Czech]
• Integer programming software: Gurobi, SCIP (and the ZIMPL language), CPLEX, GLPK, COIN-OR, GAMS, NEOS (online) and other options

04.05.2023

Special cases of integer programs: Knapsack, TSP and others.

• Exercises and Solutions [in Czech]

18.05.2023 [optional]

Review and consultations.

Resources and Study Materials

• Lecture notes by M. Hladík (in Czech)
• Integer Programming (L. Wolsey)
• Theory of Linear and Integer Programming (A. Schrijver)
• Applied Integer Programming (D. Chen et al.)
• Integer Programming (M. Conforti et al.)

Typesetting mathematical texts:

• The Not So Short Introduction to LaTeX (eng, cz)
• LaTeX Wikibook