The lecture is *preliminary* scheduled on Thursday at 14:00 in S221 (the corridor in 2nd floor).

The tutorial is conducted by Elif Garajová.

The lecture starts the second week of the semester.

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

2.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. |

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

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

23.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. |

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

6.4. | The Travelling Salesman Problem (colloquium by W. Cook, in the Hall on 1st floor). |

13.4. | Heuristics. Column generation. Knapsack problem: formulation and computational complexity, pseudopolynomial algorithms, approximation scheme. |

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

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

4.5. | Lagrange relaxation: formulation, its strength and comparison with integer relaxation, subgradient algorithm. Application in TSP. |

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

18.5. [plan] | The reformulation-linearization technique and the hierarchy of LP relaxations. |