Course content

The course presents the theory and practice of deterministic algorithms for locating the global solution of NP-hard optimization problems. Recurring themes and methods are convex relaxations, branch-and-bound, cutting planes, outer approximation and primal-dual approaches. Emphasis is placed on the connection between methods. As the course progresses, these methods will be applied and illustrated in the development of algorithms for mixed-integer linear programs, mixed-integer convex programs, nonconvex programs, and mixed-integer nonconvex programs. The broad range of engineering applications for these optimization formulations will also be emphasized.

Learning outcome

Knowledge:

The course provides a presentation of the following topics:

• Introduction to the different classes of optimization (Linear Programming - LP, Mixed-Integer Linear Programming - MILP, Convex Nonlinear Programming, Mixed-Integer Convex Programming - MICP, Nonconvex Nonlinear Programming - NLP, and Nonconvex Mixed-Integer Programming - MINLP
• Motivation for Global Optimization
• Background concepts: Convex Optimization, Optimality Criteria for NLPs, Duality Theory and Computational Complexity
• Attaining Global Information: Interval Analysis, Convex and Concave Relaxations
• MILPs - Problem formulation and Branch-and Bound based solution algorithms
• NLPs - Solution using spatial Branch-and-Bound algorithms
• MICPs - Solution using Outer Approximation and Generalized Benders Decomposition
• MINLPs - Solution using Branch-and-Bound based algorithms, Nonconvex Generalized Benders Decomposition and Nonconvex Outer Approximation

Skills:

• Have an understanding of how to formulate and solve optimization problems appropriately using commercial software (e.g. JuMP in Julia, or GAMS)
• Have an overview of the workings behind several state-of-the-art algorithms for various problem classes. Know which algorithms are appropriate for what types of problems

General Competence:

• Learning how to use computational tools to support decision-making for a variety of engineering problems

Learning methods and activities

A hybrid teaching form will be used, where a considerable degree of Self-learning is combined with Q&A Colloquiums with one or more lecturers and the students of this course. As mentioned below, videos from a similar course at MIT will also be made available together with a text book and a considerable set of slides explaining some of the details of the curriculum. The course will also have assignments with solutions.

The course is given every two years, starting autumn 2025.

Further on evaluation

The course is taught every other year, next time autumn 2025.

The exam will take the form of a written report based on a project chosen by the student that s related to the PhD research of the candidate, and where the tools and methods provided in this course are utilized.

The grading of the exam will be pass / no pass, where 70 points (of 100) score is required to pass.

Recommended previous knowledge

An introductory course in linear optimization and a similar course in non-linear optimization will give the students a good start. An introductory course in real analysis would be even better, but not expected by the average student in this course.

Required previous knowledge

None

Course materials

• Paul I. Barton: Mixed-Integer and Nonconvex Optimization, Department of Chemical Engineering, Massachusetts Institute of Technology (MIT), Cambridge, MA 02139, USA, 2011 (Textbook)
• Paul I. Barton: Videos from lectures at MIT, Spring 2021
• Set of slides related to details in the textbook