TNK104

Applied Optimization I

Teachers:

Tatiana Polishchuk, tatiana.polishchuk@liu.se Anastasia Lemetti, anastasia.lemetti@liu.se

The next HW3 deadline is Friday September 26, 13:15 (start of the lab)

Next lecture on Monday 29 in TP31. Teacher: Valentin

Please fill in the Mid-term evaluation form!

Course literature

Textbooks: Introduction to Algorithms, Third Edition, by Cormen, Leiserson, Rivest, and Stein. Network Flows Ahuja, Magnanti, and Orlin, J.B., 1988. Video material: MIT OpenCourseware (MIT-OCW)

Lectures

Lecture 1: Mon September 1, 13:15 - 17:00 (TP301) 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 Ford
Lecture 2: Mon September 8, 13:15 - 17:00 (TP31) 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 15 , 13:15 - 17:00 (TP31) 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 22, 13:15 - 17:00 (TP32) 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 +Example 2d Knapsack
Lecture 5: Lecturer Valentin Polishchuk. Mon September 29, 13:15 - 17:00(TP31) 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: ATTN: TIME CHANGED! Mon October 6, 15:15 - 17:00 (TP32) Review session (slides), preparation for the final examination.
Lecture 7 (Optional!): Mon October 13 13:15 - 15:00 (TP31) final meeting (on demand: please, email Tatiana or Anastasia to request their help).

Labs (room TP4003): lab instructor Anastasia Lemetti

Lab1: Fri September 5, 13:15 - 15:00, HW1 help session : submission deadline START of NEXT LAB: September 12, 13:15Lab2: Fri September 12, 13:15 - 15:00, HW2 help session : submission deadline START of NEXT LAB: September 19, 13:15Lab3: Fri September 19, 13:15 - 15:00, HW3 help session : submission deadline START of NEXT LAB: September 26, 13:15Lab4: Fri September 26, 8:15 - 10:00, HW4 help session : submission deadline START of NEXT LAB: October 3, 13:15Lab5: Fri October 3, 13:15 - 15:00 HW5 help session : submission deadline October 10, 13:15. Knapsack.demo code (Matlab)

Applied Optimization I

Course literature

Lectures

Labs (room TP4003): lab instructor Anastasia Lemetti

Individual take-home final assignments due October 21, 23:55