Applied Optimization I
The DEADLINE for final individual assignments is October 21, 23:59
Lecture 7 on October 9 on request only ! Email Tatiana if you need help!
Course literature
Course literature
Textbook: Introduction to Algorithms, Third Edition, by Cormen, Leiserson, Rivest, and Stein.Video material: MIT OpenCourseware (MIT-OCW)
Lectures (room SP34)
Lecture 1: Mon August 28, 13:15 - 17:00 slides L01, slides L02 To prepare: read textbook Chapters 22, 24 ( in part IV Graph algorithms) + video material: MIT OCW Lect 13, Lect 14, Lect 17, + YT videos: graph theory application, complexity, topsort1, topsort2 , BFS, DFS1, DFS2, Dijkstra alg 1, Dijkstra alg 2 , Bellman FordLectures (room SP34)
Lecture 2: Mon September 4 , 13:15 - 17:00 slides L03, slides L04 To prepare: read textbook Chapters 23 (Minimum spanning trees), Section 6 (Heaps, priority queues), Section 21 (Disjoint Sets), Chapter 29 (LP) + reading material: LP review, IP formulation guide + video material: MIT OCW Lect 12, Lect 8, Lect 13, Lect 15 + YT videos: Prim’s algorithm, Kruskal’s algorithm, Binary Heap, Priority queue, Union Find, Union-Find operations on disjoint sets, Maximum flow 1, 2, Graphical method, Duality 1, 2, VRP example, Cutting plane method 1, 2, Separation problem, Branch and Bound 1, 2, 3
Lecture 3: Mon September 11 , 13:15 - 17:00 slides L05, slides L06To prepare: read textbook Chapters 35 (Approximation algorithms) + video material: MIT OCW Lect9 + YT videos: Approximation algorithms, Local search 1, 2, 3, Neighborhood Search 1, 2, Greedy for binary knapsack, 2-opt for TSP , Eulerian tour, Tabu search 1, 2, Simulated annealing, +with genetic algorithm, Genetic algorithms 1, 2, 3 , for TSP
Lecture 4: Mon September 18, 13:15 - 17:00 slides L07, slides L08To prepare: read LP relaxation, Lagrangian duality, Lagrangian relaxation Chapters 16 and 17 in the Network Flows book, Lagrangian duality and TSP relaxation slides + video lecture: Lagrangian relaxation + YT videos: duality (weak and strong), Lagrangian, Lagrangian duality, TSP Lower bound, Matchings, Subgradient
Lecture 5: Mon September 25, 13:15 - 17:00 slides L09, slides10To prepare: read textbook Chapters 34 (NP-completeness) + video material: MIT OCW Lect 16 + YT videos: Complexity theory, Big-O notation, Bipartite matchings, Satisfiability Problem
Lecture 6: Mon October 2, 13:15 - 17:00 Review session (slides), preparation for the final examination.
Lecture 7: Mon October 9 13:15 - 15:00 final meeting (on demand: please, email Tatiana or Anastasia to request their help).
Labs (room TP4003): lab instructor Anastasia Lemetti
Labs (room TP4003): lab instructor Anastasia Lemetti
Lab1: Fri September 1, 13:15 - 15:00, HW1 help session : submission deadline START of NEXT LAB: September 8, 13:15Lab2: Fri September 8, 13:15 - 15:00, HW2 help session : submission deadline START of NEXT LAB: September 15, 13:15Lab3: Fri September 15, 13:15 - 15:00, HW3 help session : submission deadline START of NEXT LAB: September 22, 13:15Lab4: Fri September 22, 13:15 - 15:00, HW4 help session : submission deadline START of NEXT LAB: September 29, 13:15Lab5: Fri September 29, 13:15 - 15:00 HW5 help session : submission deadline October 6, 13:15.