|
|
The lecture is scheduled on Tuesday at 9:00 in S5. The first lecture is on Feb 25th.
The tutorial is conducted by Elif Garajová.
Lecture notes (in Czech): Integer programming
| 25.2. | Classification of integer programs, integer polyhedron and Meyer's theorem. |
| 4.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. |
| 11.3. | Complexity of integer programs in detail - NP-completeness. Size of input entries and size of solutions of linear systems. Boundedness of the integer polyhedron. Related complexity results. |
| 18.3. | Dual simplex method and ℓ-method for linear programming, lexicographical order. Cutting-plane methods: The first Gomory algorithm for pure integer problem. |
| 25.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. |
| 1.4. | Branch & bound methods: Variable selection, exploring the branch & bound tree, preprocessing, branch & cut, current trends. |
| 8.4. | Heuristics. Column generation. Knapsack problem: formulation and computational complexity, pseudopolynomial algorithms, approximation scheme. |
| 15.4. | Knapsack problem: relaxations, branch & cut and cutting planes. TSP - Travelling salesman problem: applications, complexity, heuristics and local improvements (k-exchange). |
| 22.4. | TSP - Travelling salesman problem: formulation as an integer linear program, cutting planes, relaxations and lower bounds. |
| 29.4. | Lagrange relaxation: formulation, its strength and comparison with integer relaxation, subgradient algorithm. Application in TSP. |
| 6.5. | Benders decomposition and its application in (uncapacitated) facility location problem. |
| 20.5. | The reformulation-linearization technique and the hierarchy of LP relaxations. |
