TAOP24 Lectures

To successfully follow the course, some extra efforts are required from the students on reading the book and solving problems beyond the scheduled class hours. Below one can find which book chapters to read and problems to solve for each lecture. During the tutorial sessions, one can learn how to solve some of these problems. The rest are supposed to be solved by the students themselves, either during the tutorial sessions, or at home. There are much more problems in the book that can help to understand better the course topics. The old exam  assignments (see Exams in the menu) are strongly recommended  as good exercises.

Lecture 1. Linear programming and LP duality (rept.), simplex method for bounded variables, introduction to networks and LP formulation with shortest path problem as a special case. Ch. 4, 6, 7.1, 8.1-2, 8.4, 8.6.
Exercises: 8.2-8.6

Lecture 2. Min-cost flow problem, network simplex method. Ch. 8.7, slides.
Exercises: 8.26-8.36, exams.

Lecture 3. Maximum flow problem. Lecture notes, slides.
Exercises: here, exams.

Lecture 4. Dynamic programming. Ch. 18, slides.
Exercises: 18.1-7, exams.

Lecture 5. Integer programming models, nondifferentiable optimization, subgradients, subdifferentials. Ch. 13.1-10, 14.3, 17.1-3, slides.
Exercises: 13.1-12, exams.

Lecture 6. Complexity, traveling salesman problem,  heuristics. Ch. 13.10, 16.1-16.3.1.
Exercises: 16.2 (consider only nearest neighbor, nearest addition, nearest insertion, cheapest insertion, farthest insertion).

Lecture 7. Conjugate-gradient, Newton, quasi-Newton methods. Ch. 10.1-3, slides.
Exercises: exams.

Lecture 8. Quadratic programming. Ch. 12.2.
Exercises: 12.10-12, exams.

Lecture 9. Penalty, barrier, interior point methods. Ch. 7.5, 12.3-4, slides.
Exercises: exams.

Sidansvarig: webmaster@mai.liu.se
Senast uppdaterad: 2019-11-29