NOPT059 Large-scale optimization: Exact methods

The course is taught bi-yearly (in odd-numbered years), alternating with the course NOPT061 Large-scale optimization: Metaheuristics.

The course will be scheduled in the beginning of the semester (probably during the first week). If you are interested, please email me your time constraints.

About this course

The aim of course is to introduce the main principles of various exact optimization methods based on linear programming and combinatorial optimization with emphasis on large-scale instances. Moreover, during the accompanying tutorial you will gain experience in applying these methods in practice.

We expect you to be somewhat familiar with linear programming. Although certainly not necessary, a recommended prerequisite is the course NOPT048 Linear programming and combinatorial optimization.

Tentative schedule

• Lecture 1: Introduction. Modeling using Integer programming.
• Lecture 2: Linear programming basics, the simplex method, duality, complementary slackness.
• Lecture 3: Branch and bound
• Lecture 4: Cutting plane algorithms, lazy constraint generation
• Lecture 5: Strong valid inequalities
• Lecture 6: Lagrangian duality 1
• Lecture 7: Lagrangian duality 2
• Lecture 8: Column generation 1
• Lecture 9: Column generation 2
• Lecture 10: Branch-cut-and-price
• Lecture 11: Multi-objective optimization

Resources

• Webpage of the tutorial (taught by Jirka Fink)
• This course in the SIS
• The book that covers a majority of the course material: Laurence Wolsey, Integer programming, 2nd edition. Wiley 2020.

Exam requirements

The exam is oral with written preparation. Requirements for the exam correspond to the syllabus of the course in the extent that has been covered in the lecture. Obtaining the credit from the tutorial is a necessary requirement for taking the exam.

Frequently asked questions (FAQ)

• I am interested in this course! — That’s not a question. But email me!
• Where and when is the first class? — The course will start in the second week of the semester. We will agree on the where and when by email during the first week.
• What should I do if I have a question? — Check the FAQ. If you don’t see the answer here email me putting “nopt059” in the subject.
• What if I want a consultation? — Talk to me after class, come to the scheduled office hours, or email me to arrange an appointment.