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]