Elif Garajová

Integer Programming

The tutorial is scheduled on Tuesday at 12:20 in room S10. 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: 11. 3.]
• Theory: Integer polyhedra, unimodularity, complexity [deadline: 1. 4. 12:20]
• Methods for solving integer programs [deadline: 15. 4. 12:20]
• Special cases: Knapsack and TSP [deadline: 6. 5. 12:20]
• Heuristics, decompositions and software [deadline: 20. 5. 12:20]

Preliminary Schedule of the Tutorials

25. 2. 2025

Formulating integer linear programs.

• Exercises and Solutions [in Czech]

11. 3. 2025

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

• Exercises and Solutions [in Czech]

1. 4. 2025

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

• Exercises and Solutions [in Czech]

15. 4. 2025

Special cases of integer programs: Knapsack, TSP and facility location.

• Exercises and Solutions [in Czech]

6. 5. 2025

Heuristics, Lagrangian decomposition and column generation methods.

• Exercises and Solutions [in Czech]
• Integer programming software: Gurobi, SCIP (and the ZIMPL language), GLPK, HiGHS, GAMS, CPLEX, NEOS (online) and other options. Academic licenses available.
• Examples for GLPK, Gurobi and GAMS (in Czech).

20. 5. 2025 (plan)

Benders decomposition. 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