Linear Optimization and Methods

Course guarantor:

Dušan Knop

Lecturer:

Dušan Knop

Tutor:

Dušan Knop

Supervisor:

Department of Theoretical Computer Science

Synopsis:

Students will gain an overview of applications of optimization methods in computer science, economics and industrial practice. They will be introduced to the practical importance of linear and integer programming. They will be able to work with optimization software and to master the languages used in its programming. They will be able to formalise optimisation problems in the areas of computer science (e.g. task allocation to processors, network flow analysis), resource distribution and allocation (traffic problems, business traveller problem, etc.). Gain an overview of computational complexity issues in optimization. Gain a good understanding of linear programming algorithms and selected integer linear programming algorithms.

Requirements:

Syllabus of lectures:

1. Classification of optimization problems: linear and integer programming, nonlinear optimization, continuous optimization, special types of linear problems, general convex optimization problems, multi-criteria optimization, heuristics.

2. Basics of linear and integer programming theory and its geometry, forms of linear programs.

3. Simplex algorithm.

4. The duality of linear programming.

5. Using duality in combinatorics and algorithm design.

6. Ellipsoid algorithm - description of the algorithm and the beginning of the analysis.

7. Ellipsoid algorithm - completion of analysis.

8. Totally unimodular matrices, their characterization and significance for integer optimization.

9. Integer programming in bounded dimension (Lenstra’s algorithm).

10. Integer Programming with Equality and Hermitian Matrix Decompositions.

11. Algorithms for integer programming based on Steinitz lemma - I.

12. Algorithms for integer programming based on Steinitz lemma - II.

13. Implementation issues (numerical stability, sparse matrices, approximate and exact solutions, data structures).

Syllabus of tutorials:

1. Formulation of optimization problems.

2. Formulation of optimization problems.

3. Syntax of optimization languages: CPLEX.

4. Solution of particular problems in CPLEX.

5. Sensitivity; applications of duality.

6. The Simplex Algorithm.

7. Bonus

Study Objective:

The aim of the module is to familiarize students with methods and algorithms for optimization and mathematical programming. It is focused on linear and integer optimization and its applications in distribution and allocation problems, data analysis, network design, modelling of conflicts using the game theory. Within seminars students work with professional optimization software and their programming languages.

Study materials:

1. Jiří Matoušek, Bernd Gärtner : Understanding and Using Linear Programming (Universitext). Springer, 2006. ISBN 978-3540306979.

2. Michael Jünger, Thomas M. Liebling, Denis Naddef, George L. Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, Laurence A. Wolsey (Eds.) : 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer, 2009. ISBN 978-3540682745.

3. Christos H. Papadimitriou, Kenneth Steiglitz : Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998. ISBN 978-0486402581.

4. Robert J. Vanderbei : Linear Programming: Foundations and Extensions. Springer, 2020. ISBN 9783030394172.

Note:

Further information:

https://courses.fit.cvut.cz/NIE-LOM/

Time-table for winter semester 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue	roomTH:A-1247 Knop D. 11:00–12:30 (lecture parallel1) Thákurova 7 (budova FSv)
Wed
Thu
Fri

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans:

• Master specialization Computer Science, in English, 2024 (PS)