Syllabus
Fundamentals of discrete optimization:
- Introduction, examples of optimization and examples of techniques. Analysis of algorithms, implementation and complexity.
- Shortest paths and minimum spanning trees and relations.
- Maximum matching and applications, relation to flows in networks. Algorithms for matchings. Postman problem.
- Traveling salesman problem (TSP): heuristics, applications and relations.
- Comparisons of hard and polynomial problems.
Fundamentals of continuous optimization:
- Convex functions and sets
- Convex optimization
- Quadratic programming
- Cone programming and duality
- Karush-Kuhn-Tucker optimality conditions
- Basic methods
- Programming with uncertain data, robust optimization
Annotation
Review course covering fundamental fields of optimization, incl. computational methods. There are countless examples from almost all branches of human doing leading to problems coming under this discipline. Introduction to several other courses specialized in the solution of particular classes of optimization problems.
Previous knowledge of linear programming, e.g. from NOPT048 Linear Programming and Combinatorial
Optimization (formerly Optimization Methods) is advisable (but not required).