Examination arrangement

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.

Further on evaluation

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