Course given at the Cambridge Centre for International Research
Nowadays, crucial modern infrastructures are operated by optimizing the decisions using what is called mixed integer linear programming (MILP). This includes smart electrical grids, planning of deliveries for online shopping, scheduling at hospitals, or the design of transportation networks.
In this research course, students will learn the mathematical foundation of MILP as well as its numerical aspects with practical applications. They will conduct research projects on MILP and learn how to solve complicated real-world problems by leveraging their knowledge in MILP.
The course will start with an introduction to linear programming. We first cover how to model a problem as a linear program and its numerous applications. We then review the different algorithms that can be used to solve it and the size of programs that can be handled by a computer. We learn how to write programs in Julia (a high-level, high-performance, dynamic programming language for technical computing) and then solve concrete problems by modelling them as linear programs using JuMP. In addition, we cover data manipulation, visualisation and analysis in order to integrate real data into the model to obtain interpretable results.
The course then will then focus on integer variables in the modelling, expanding into the topic into mixed-integer linear programs (MILPs). We will show how to formulate problems ranging from vehicle routing to machine learning as MILPs. Mixed-integer linear programs can be solved using a branch and bound algorithm that we detail in the course. The same problem can be formulated as different MILPs. However, while some formulations can be solved in a few seconds, some may take hours! We highlight the key aspects that are important for a formulation to be solved efficiently.
The course uses a hands on approach by illustrating all theoretical results with code using the JuMP framework in the Julia programming language.
In order to benefit from this, you will have to install the necessary in your computer. This can be achieved via the following steps:
Install Julia, VS code and the Julia extension for VS code as detailed here. For installing Julia, I recommend doing it through juliaup.
To download the course material, either follow the top badges to download the Jupyter notebooks or download the Julia files from my website. VS code provides similar interactive features with simple .jl Julia files than what is found in Jupyter notebooks so both option are equally good, you are free to choose the one you prefer.
You will find below the list of lectures and practical sessions in html format. You can find a link to the jupyter notebook versions from the top of the pages.
Lecture 1 – System of linear equations
Lecture 2 – Why derivatives matter
Lecture 3 – What is convexity and why does it matter
Lecture 4 – Mixed Integer Linear Programming and branching
Lecture 5 – Linear Programming duality and Branch and Bound
Lecture 6 – Max-Flow and Min-Cut
Lecture 7 – Traveling Salesman Problem
Practical 1 – Linear regressions
Practical 2 – Multiple linear regressions in Julia and introduction to JuMP
Practical 3 – Linear Programming in JuMP: The diet problem
Practical 4 – Mixed-Integer Linear Programming in JuMP: The facility location problem
Practical 5 – Sensitivity analysis of a linear program
Practical 6 – Sudoku
Practical 7 – Logic and Scheduling
Practical 8 – Statistics and optimization