Integer Programming and Combinatorial Optimization 2025-26

Orario del corso:

• Lunedì 10-13 Aula A7

• Giovedì 15-19 Aula A4

• Venerdì 14-17 Aula A4

Ricevimento: Il ricevimento si terrà ogni mercoledì alle 14:30  previa prenotazione via email nell'ufficio del docente, sito in A109 presso il DIAG, via Ariosto 25.

Link al corso su classroom: https://classroom.google.com/u/4/c/MTYyMzQ2Njc4NDIy

Diario delle lezioni

1. 09/04/2026 (4hrs) Introduction to the second part of the course. Introduction to complexity of algorithms and problems. Orders of magnitude. Example of interesting functions g(n). Moderate exponential growth, exponential growth, alphabet, string, Language. Problem

2. 10/04/2026 (3hrs) Decision problem, evaluation problem, Language associated to a problem, Deterministic Turing Machine: examples

3. 13/04/2026 (3hrs) Further examples of Turing Machines, Temporal complexity, Tractable problems, Class P, Strongly polynomial Problems. Non-deterministic Turing Machine (NDTM), class NP

4. 16/04/2026 (4hrs) Temporal complexity of a NDTM, class NP, Polynomial Reduction between Problems, NP complete problems (SAT)

5. 17/04/2026 (3hrs) Knapsack Problem: definition (and variations), mathematical formulation, first LP relaxation

6. 20/04/2026 (3hrs) Upper Bounds on the Knapsack Problem: split item, solution of the LP relaxation, quality of the LP relaxation, Dantzig UB

7. 23/04/2026 (4hrs) Martello Toth UB, Cover, Cover closure, Separation Problem for the Cover Inequalities, Separation problem as a Knapsack problem, examples. Exercises on Knapsack

8. 24/04/2026 (3hrs)  Extended Cover Inequalities Approximation Algorithms. Greedy Algorithm for Knapsack

9. 27/04/2026 (3hrs) Extended Greedy Algorithm, Two items guessing heuristic

10. 30/04/2026 (4hrs) Exercises on the two items guessing heuristic. Complexity of the Knapsack problem, Introduction to Dynamic Programming: Rod Cutting Problem

11. 4/05/2026 (3hrs) Dynamic Programming for Knapsack, examples

12. 7/05/2026 (4hrs) Facility Location: definition of the problem and formulation. Cost Sharing problem: allocation of the cost between clients. LP relaxation and its dual. Examples

13. 8/05/2026 (3hrs) Cooperative gamet theory: Airport game. Connection between the cost allocation problem and the dual of the facility location LP relaxation.

14. 11/05/2026 (3hrs) Primal Dual Algorithm for Facility Location. 

15. 14/05/2026 (4hrs) Exercises on Facility Location: show that without the cleaning phase the gap can be unbounded. Show that the approximation factor can be tight.

16. 15/05/2026 (3hrs) Examples of dynamic programming applications. Bin Packing problem: definition and formulation. LP relaxation and its dual.

17. 21/05/2026 (4hrs) Optimal solution of the LP relaxation and of the dual. Quality of the relaxation. Approximation algorithm: Next Fit,  First Fit, Best Fit. Approximation factor and half full property. Example of modeling of a  Scheduling Problem 

18. 22/05/2026 (3hrs) Example of heuristic and upper and lower bound computation on a scheduling problem and on a facility location problem.

19. 25/05/2026 (3hrs) Further examples of modeling exercises

20.  28/05/2026 (4hrs) Exam simulation