Discrete Optimisation
Full course, Centrale Supelec, 2018
Discrete Optimisation
Discrete optimisation is a very large topic, that includes in particular ways to formulate and solve combinatorial search and enumeration problem, which are ubiquitous in Computer Science, Applied Mathematics, Operational Research, Machine Learning, and more.
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 |
| 02 | Tutorial 2 text | Solving LP problems with spreadsheets. Duality |
| 03 | Tutorial 3 text | This tutorial is on integer programming |
| 04 | Tutorial 4 text | This tutorial is assignment 1 |
| 05 | solving the TSP | Solving the TSP. This is assignment 2 |
Solutions and code
| Entry | Description | |
|---|---|---|
| 01 | Tutorial 1 solution | Solution to the first tutorial |
| 02 | a Python Simplex solver | Basic, commented Simplex solver |
| 03 | Excel Couple | Solution Doors and Couple |
| 04 | Sudoku solver | This code requires cvxopt. |
Code 1
Here you will find verbose, straightforward, numpy-based code for the simplex.
Here is the basic code, a Python Simplex solver, with no claim with respect to efficiency. Here is a Python Notebook, with worked out examples.
I recommend you try the Python Notebook version. Here is the online rendering of this notebook.
Thanks
Special thank to Dr. Maria Vakalopoulou and Pr. Fragkiskos Maillaros.
Sudoku solver
Here is a nice Sudoku solver written in Python. It requires cvxopt.
Peg Solitaire project
A interesting project is to implement a peg-solitaire solver.
Here are a couple of articles on how this might be done Article 1 ; Article 2.
Signal, image processing project
A second project (choose only one) is to use transport problems (max-flow problems) to solve signal and image processing problems.
Here are two useful articles Interactive graph cuts and energies minimizable by graph cuts to get started. Here is a book chapter which is better illustrated Graph cuts in vision.
Challenges
Students can elect to participate to a relevant Kaggle challenge. I recommend this new particle tracking challenge. The top prize is 12,000$ !
Other relevant challenges will be posted here.