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 learn the applications of optimization methods in computer science, economics, and industry. They are aware of practical importance of linear and integer programming. They are able to work with optimization software and are familiar with languages used in programming of that software. They get skills in formalization of optimization problems in computer science (such as scheduling of tasks to processors, analysis of network flows), distribution and allocation of resources (transportation problems, travelling salesman problems, etc.), issues from economics, and modelling of conflicts via the game theory. They get an overview of computational complexity of optimization problems. They get orientation in algorithms in linear programming.

Requirements:

Syllabus of lectures:

1. Classification of optimization techniques: linear and integer programming, nonlinear optimization, continuous optimization, special forms of linear programs, general convex programming, multicriteria optimization.

2. Mathematical formulation of optimization problems (optimization and combinatorics, distribution, allocation, network, statistical problems, etc.).

3. Models of conflicting situations, introduction to the game theory.

4. Linear algebra: matrices and linear mappings, eigenvalues and eigenvectors, basic bounds, positive (semi)definiteness, $L_k$-norms, matrix norms.

5. Fundamentals of theory of linear and integer programming and their geometry, forms of linear programs.

6. The simplex algorithm.

7. Duality in linear programming.

8. Applications of duality in combinatorics and algorithmic design.

9. Classifications of optimization problems using the complexity theory.

10. The ellipsoid algorithm.

11. Interior point algorithms.

12. Algorithms for integer programming.

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

Syllabus of tutorials:

1. Formulation of optimization problems.

2. Formulation of optimization problems --- continued.

3. Syntax of optimization languages: LINGO.

4. Solution of particular problems in v LINGO.

5. Syntax of optimization languages: CPLEX.

6. Solution of particular problems in CPLEX.

7. Syntax of optimization languages: MatLab.

8. Solution of particular problems in MatLab.

9. Sensitivity; applications of duality.

10. The Simplex Algorithm.

11. Complexity of the Simplex Algorithm; average and exponential case.

12. Multicriteria problems reducible to linear programming I.

13. Multicriteria problems reducible to linear programming II.

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. Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., Schrijver, A. ''Combinatorial Optimization''. Wiley-Interscience, 1997. ISBN 047155894X.

2. Chvatal, V. ''Linear Programming''. W. H. Freeman, 1983. ISBN 0716715872.

3. Matousek, J., Gärtner, B. ''Understanding and Using Linear Programming''. Springer, 2006. ISBN 3540306978.

4. Roos, C., Terlaky, T., Vial, J. P. ''Interior Point Methods for Linear Optimization''. Springer, 2005. ISBN 0387263780.

5. Schrijver, A. ''Theory of Linear and Integer Programming''. Wiley, 1998. ISBN 0471982326.

6. Thie, P. R., Keough, G. E. ''An Introduction to Linear Programming and Game Theory''. Wiley-Interscience, 2008. ISBN 0470232862.

7. Venkataraman, P. ''Applied Optimization with MATLAB Programming''. Wiley, 2009. ISBN 047008488X.

Note:

Further information:

http://mi-lom.polyedr.cz/

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 Security, in Czech, 2020 (elective course)
• Master specialization Design and Programming of Embedded Systems, in Czech, 2020 (elective course)
• Master specialization Computer Systems and Networks, in Czech, 202 (elective course)
• Master specialization Management Informatics, in Czech, 2020 (elective course)
• Master specialization Software Engineering, in Czech, 2020 (elective course)
• Master specialization System Programming, in Czech, version from 2020 (elective course)
• Master specialization Web Engineering, in Czech, 2020 (elective course)
• Master specialization Knowledge Engineering, in Czech, 2020 (elective course)
• Master specialization Computer Science, in Czech, 2020 (elective course)
• Mgr. programme, for the phase of study without specialisation, ver. for 2020 and higher (elective course)
• Study plan for Ukrainian refugees (elective course)
• Master specialization System Programming, in Czech, version from 2023 (elective course)
• Master specialization Computer Science, in Czech, 2023 (PS, elective course)