The lecture is scheduled on Tuesday at 14:00 in S4. The tutorial is scheduled on Tuesday at 10:40 in S321 (corridor 3rd floor) and conducted by Elif Garajová.

The lecture starts on February 28, and the tutorial starts on March 7.

28.2. | Classification of integer programs, integer polyhedron and Meyer's theorem. |

7.3. | Unimodular and totally unimodular matrices. Hoffman-Kruskal theorem for integer programs with unimodular matrices. Examples: Incidence matrices of bipartite graphs and directed graphs - transportation problem and network flows. |

14.3. | Complexity of integer programs in detail - NP-completeness. Size of input entries. Boundedness of the integer polyhedron. Related complexity results. |

21.3. | Dual simplex method and ℓ-method for linear programming, lexicographical order. Cutting-plane methods: The first Gomory algorithm for pure integer problem. |

28.3. | Finiteness of the first Gomory algorithm. The second Gomory algorithm for mixed integer problem. A note on Chvátal theorem and Chvátal rank. |

4.4. | Matej Moravcik and Martin Schmid: Artificial intelligence goes all-in: Computers playing poker, room S5 |

11.4. | Branch & bound methods. Variable selection, exploring the branch & bound tree, preprocessing, branch & cut, current trends. |

18.4. | Heuristics. Knapsack problem: formulation and computational complexity, pseudopolynomial algorithms, approximation scheme. |

25.4. |
Knapsack problem: relaxations, branch & cut and cutting planes. TSP - Travelling salesman problem: applications, complexity, heuristics and local improvements (k-exchange). |

2.5. | TSP - Travelling salesman problem: formulation as an integer linear program, cutting planes, relaxations and lower bounds. Column generation. |

9.5. | Benders decomposition and application in (uncapacitated) facility location problem. |

16.5. (plan) | Lagrange decomposition and application in facility location problem and TSP. |

23.5. (plan) | Set covering. |