Course - Global Optimization of Mixed-Integer and Non-Convex Problems - EP8199
EP8199 - Global Optimization of Mixed-Integer and Non-Convex Problems
Examination arrangement: Assignment
Grade: Passed / Not Passed
|Evaluation||Weighting||Duration||Grade deviation||Examination aids|
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.
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
- 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
- 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
- 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
Credits: 7.5 SP
Study level: Doctoral degree level
Term no.: 1
Teaching semester: AUTUMN 2023
Language of instruction: English
- Industrial Process Technology
- Design Methodology
- Energy and Process Engineering
Examination arrangement: Assignment
- Term Status code Evaluation Weighting Examination aids Date Time Examination system Room *
- Autumn ORD Assignment 100/100
Room Building Number of candidates
- * The location (room) for a written examination is published 3 days before examination date. If more than one room is listed, you will find your room at Studentweb.
For more information regarding registration for examination and examination procedures, see "Innsida - Exams"