2024/2025
Дискретная оптимизация и целочисленное линейное программирование
Статус:
Дисциплина общефакультетского пула
Кто читает:
Факультет математики
Где читается:
Факультет математики
Когда читается:
1, 2 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Преподаватели:
Клименко Алексей Владимирович
Язык:
английский
Кредиты:
3
Course Syllabus
Abstract
Each of us constantly makes schedules. We optimize our time: make plans for the weekend, choose the best route to get from one metro station to another. Is it difficult to create a schedule for a faculty or a sports league, given the many requirements and wishes? And what about optimization of the data center with thousands of servers, a seaport or a railway network of a large country? In this course we will formulate what challenges mathematicians face in the modern world, when the size of data that influences decision-making is growing faster than computing capabilities. After completing the course you will learn how to build mathematical models of optimization problems of varying complexity and solve them using solvers based on integer and linear programming methods. The course is not limited to the practice of problem solving, you will get acquainted with the basic concepts and classical algorithms of optimization methods, as well as the main aspects of the theory underlying the software that helps to make decisions in the modern world.
Course Contents
- Problems of unconditional and conditional optimization. Method of Lagrange multipliers
- Numerical optimization methods. Gradient descent. Newton’s method
- Basics of complexity theory. Relation of classes P and NP.
- Linear programming. Simplex method
- Theory of duality. Optimality Conditions and Duality in Problems of Linear Programming.
- Integer points of polyhedra. Integer linear programming. Unimodular matrices. The branch and bound method. Cutting-plane method.
- Statement and solution of problems using MILP-solvers.
- Efficiency of MILP-solvers for some graph theory problems. Shortest path problem. Minimum spanning tree.
- Constraint programming.
Interim Assessment
- 2024/2025 2nd module0.5𝐻 + 0.5𝐸, where 𝐻 and 𝐸 are marks on a 10-point scale for homework and an exam respectively.
Bibliography
Recommended Core Bibliography
- Combinatorial Optimization, Theory and Algorithms, 5th edition, XX, 659 p., Korte, B., Vygen, J., 2012
Recommended Additional Bibliography
- Combinatorial optimization. Vol.A: Paths, flows, matchings : chapters 1-38, Schrijver, A., 2003
- Combinatorial optimization. Vol.B: Matroids, trees, stable sets : chapters 39-69, Schrijver, A., 2003
- Combinatorial optimization. Vol.C: Disjoint paths, hypergraphs : chapters 70-83, Schrijver, A., 2003