Lecture: Mondays 10:40 to 12:10 in S9
Tutorial: Mondays 16:30 to 18:00 in S1
By email appointment.
Discrete Optimization
Introduction
Shortest paths
Minimum spanning trees
Maximum flows
Minimum cuts
Matchings
T-joins
Travelling Salesman problem
Continuous Optimization
Introduction to mathematical optimization
Unconstrained optimization
Convexity of sets and functions
Convex Optimization: quadratic programming, cone programming, semidefinite programming
Ellipsoid method
Karush-Kuhn-Tucker optimality conditions
18.2.2019: basic graph theory, random access machines, polynomial-time solvability, NP-hardness, integer linear programs and their relaxations
25.2.2019: shortest paths: Dijkstra vs Bellman-Ford, spanning trees: Kruskal and the partitioning LP
4.3.2019: primal-dual algorithm for MST, total unimodularity and max flows, path decomposition of flows and the dual of the flow LP
11.3.2019: min st-cuts from dual of flow LP, global min cuts via Karger's algorithm, bipartite matchings via the rank lemma and iterative rounding
18.3.2019: integrality of the perfect matching polytope, the Chinese Postman problem, T-joins
25.3.2019: computing T-joins, applications of T-joins, the T-join polyhedron, Subset Path TSP, parameterized algorithms
1.4.2019: Christofides' algorithm for TSP, Hoogeveen's algorithm for Path TSP, basic notions of continuous optimization
8.4.2019: unconstrained optimization: 1st and 2nd order optimality conditions, application: least square method, convex sets: characterizations and separability
15.4.2019: convex functions, first and second order characterizations
29.4.2019: convex optimization, quadratic programs, cone programs, weak duality of cone programs
6.5.2019: strong duality of cone programs, semidefinite programming, ellipsoid method, copositive programming
20.5.2019: KKT conditions for equality constraints, general constraints, and convex optimization using Slater's condition
B. Korte and J. Vygen. Combinatorial Optimization. Springer, 4th edition, 2008.
B. Guenin, J. Könemann, and L. Tunçel. A Gentle Introduction to Optimization. Cambridge University Press, 2014.
L. C. Lau, R. Ravi, and M. Singh. Iterative Methods in Combinatorial Optimization. Cambridge University Press, 2011.
S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
D. Luenberger and Ye. Linear and Nonlinear Programming. Springer, 3rd edition, 2008.
M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. Nonlinear Programming. Theory and Algorithms. 3rd ed. John Wiley & Sons., 2006.
F. Augugliaro, A.P. Schoellig, and R. D’Andrea, Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach, EEE/RSJ International Conference on Intelligent Robots and Systems, 2012: pp. 1917–1922. [Youtube video]