Integer Programming (NOPT016), summer semester 2016/2017

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.

### Schedule

 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.

### Literature

lecture notes (in Czech).

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