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