Integer Programming (NOPT016), summer semester 2022/2023 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.

### Schedule (updated)

 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.

### Literature

lecture notes (in Czech).

"The Good Lord made all the integers; the rest is man's doing." [Leopold Kronecker]