Linear Optimization and Methods

Garant předmětu:

Dušan Knop

Přednášející:

Dušan Knop

Cvičící:

Dušan Knop

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

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.

Požadavky:

Osnova přednášek:

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

Osnova cvičení:

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

Cíle studia:

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.

Studijní materiály:

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.

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/NIE-LOM

Další informace:

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

Rozvrh na zimní semestr 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
Po
Út	místnost TH:A-1247 Knop D. 11:00–12:30 (přednášková par. 1) Thákurova 7 (budova FSv) seminární místnost
St
Čt
Pá

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

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