Optimisation for AI
Full course, CentraleSupelec, 2023
Optimisation for AI
Optimisation is at the heart of Machine Learning, indeed most practitioners of ML rely on sophisticated methods to learn models from data. Optimisation is also behind the scenes in reasoning, games, and many classical AI problems such as optimal assignment.
If you’ve ever wondered how to program a Sudoku solver for instance, and how complex it would be, this course will tell you exactly how to do it.
In this course, we begin with linear programming, which is a starting point for many discrete-based algorithms. We consider the contraints of adding integer and binary constraints, which allows us to formulate decision problems, in particular NP-complete problems.
We next consider specialized algorithms for which enumeration is fast and efficient, such as transport and flow problems.
All along the course we provide numerous examples and tutorial sessions.
Slack
Invitation to the Slack for the course: gbit.ly/2DMK9jf
Lectures
| Entry | Description | |
|---|---|---|
| 01 | Introduction | Introduction to optimisation |
| 02 | The Simplex algorithm | An algorithm for solving linear programs |
| 03 | Limit cases of the Simplex | The limiting cases for the simplex, like how to start it |
| 04 | Duality | LP and duality. Interpretation and algorithms |
| 05 | Integer Programming | Formulation and examples |
| 06 | IP resolution | Resolution of Integer Programs: Cuts and Branch & Bound |
| 07 | Transport Problems | Transport problems are a simpler case of LP/IP |
| 08 | Resolution of transport problems | Resolution of transport problems |
| 09 | Network problems | Network problems, including maxflow and the network simplex |
Tutorials
| Entry | Description | |
|---|---|---|
| 01 | Tutorial 1 text | Simplex algorithm, examples, formulations |
Solutions and code
| Entry | Description | |
|---|---|---|
| 01 | Tutorial 1 code | Code for assignment 1, to be completed |
Thanks
Special thank to Pr Iskandar Hammam; Pr. Maria Vakalopoulou and Pr. Fragkiskos Maillaros.