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.
Invitation to the Slack for the course: gbit.ly/2DMK9jf
|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|
|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
|01||Tutorial 1 solution||Solution to the first tutorial|
|02||a Python Simplex solver||Basic, commented Simplex solver|
|03||Sudoku solver||This code requires cvxopt.|
Here you will find verbose, straightforward, numpy-based code for the simplex.
I recommend you try the Python Notebook version. Here is the online rendering of this notebook.
Special thank to Dr. Maria Vakalopoulou and Pr. Fragkiskos Maillaros.
Peg Solitaire project
A interesting project is to implement a peg-solitaire solver.
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.
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.