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

 EntryDescription
01IntroductionIntroduction to optimisation
02The Simplex algorithmAn algorithm for solving linear programs
03Limit cases of the SimplexThe limiting cases for the simplex, like how to start it
04DualityLP and duality. Interpretation and algorithms
05Integer ProgrammingFormulation and examples
06IP resolutionResolution of Integer Programs: Cuts and Branch & Bound
07Transport ProblemsTransport problems are a simpler case of LP/IP
08Resolution of transport problemsResolution of transport problems
09Network problemsNetwork problems, including maxflow and the network simplex

Tutorials

 EntryDescription
01Tutorial 1 textSimplex algorithm, examples, formulations
02Tutorial 2 textSolving LP problems with spreadsheets. Duality
03Tutorial 3 textThis tutorial is on integer programming
04Tutorial 4 textThis tutorial is assignment 1
05solving the TSPSolving the TSP. This is assignment 2

Solutions and code

 EntryDescription
01Tutorial 1 solutionSolution to the first tutorial
02a Python Simplex solverBasic, commented Simplex solver
03Sudoku solverThis 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.