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