Discrete Optimisation (MATH0462), 2015-2016

General information

Professor: Q. Louveaux.

Course page.

Lab accounts (MS800).

The practical part of this course is two-fold: first, exercise sessions to help you understand the theory; second, projects, to give you some experience about the real-world practice of optimisation. Indeed, these projects focus on modelling and implementing models, which are the most important skills to get from this course; only the first one is evaluated during the exam.

Publicly available slides for the theoretical course



For the resit, the written exam has the same modalities as the first session. It will take place on September 2nd, 8:30. For those who did not present the projects, only the second one must be handed in, with only one report for the two parts. An oral presentation is also required; contact me to organise the schedule. The project must be sent by email for September 5th at the latest; oral presentations will not happen after this date.

Exercise sessions

# Date Agenda Statement Other files
1 18th September 2015 MILP modelling, JuMP installation and first examples PDF Data files (Julia), spoons example
2 25th September 2015 Branch-and-bound, presentation of the first project, modelling PDF Data file for the teams
3 2nd October 2015 Q&A about the project, branch-and-bound implementation PDF Branch-and-bound skeleton and implementation
4 9th October 2015 Modelling, formulation comparison PDF
11th October 2015 Danger Deadline for the first project
5 16th October 2015 Correction of the first project, formulation comparison PDF
6 23rd October 2015 Nothing
7 30th October 2015 Cuts and valid inequalities PDF
8 13th November 2015 Cuts and valid inequalities PDF Prize-collecting travelling salesman problem implementation and knapsack base problem
9 20th November 2015 Dynamic programming PDF
22nd November 2015 Danger Deadline for the second project, first part
10 27th November 2015 Project correction; flow algorithms PDF
11 4th December 2015 Matching and assignment algorithms PDF
12 11th December 2015 Constraint programming, project Q&A PDF ECLiPSe Windows x64, ECLiPSe Linux x64
skeleton for the sudokus, solution for the sudokus, solution for the magic squares, solution for the n queens
13th December 2015 Danger Deadline for the second project, second part
18th December 2015 Project presentations

Those exercises come in large part from Sébastien Mathieu’s work, and have been modified with his consent.


Project 1: modelling

This first project is about lorry dispatching. Available files:

Updated: 30th September. Slightly clarified statement, modified data structures and stub to provide solution for the bonus; provided files are now compatible with both 32- and 64-bit Julia.

The project must be submitted on the submission platform. Submissions will be accepted till 11th October, 2015, 23:59.

Project 2: Car on the Hill

This second project is about carsharing. Available files:

The project must be submitted on the submission platform. Submissions will be accepted till 22nd November, 2015, 23:59 for the first part, and 13th December, 2015, 23:59 for the second part.

Your program should take as input three file names: the nodes, the edges, then the users, using the previous format. For users, drivers and passengers are mixed in the same file, with a bit to distinguish them. The missing information for passengers is filled with -1s. To read the files with Julia, you can use the readdlm function:

readdlm("….csv", ',')

You should test your program on larger graphs with more users than the provided test case. If you write code to generate those files (for example, by accessing OpenStreetMap or Google Maps), you should include it as well as the generated instances on which you tested your code.

General comments

When asking for help with your code: give a meaningful snippet, allowing easy testing; precise whether the tests were carried out on the MS800 machines or your own (with platform and bitness, if relevant).

Don’t assume knowledge about your model, only use names defined in the given files: I don’t have access to your code before you submit it, I can only guess what is the meaning of all those nice symbols.

Interesting link: How NOT to go about a programming assignment.

Modelling tricks: Applications of optimization with Xpress-MP, Formulating Integer Linear Programs: A Rogues’ Gallery.

Debugging a MIP model: Detecting the Sources of Model Infeasibility using Gurobi.


How to install Julia and JuMP?

Julia is a technical computing programming language, completely free and open-source. Its syntax should be very familiar to MATLAB users. Its environment includes a strong mathematical optimisation community, JuliaOpt.

Hint: a working version of Julia is available on the MS800 machines. It is not necessary to follow this procedure on those computers (including Gurobi with a network license).

First, download Julia 0.3 for your platform from their webpage and install it:

Then, install the optimisation packages: JuMP as a modelling layer, Cbc as a free open-source solver. From the Julia prompt:

julia> Pkg.update()
julia> Pkg.add("JuMP")
julia> Pkg.add("Cbc")

As a final step, you might be interested in installing a much faster (even though closed-source) solver, such as Gurobi. First, download the solver (64-bit version) and ask for an academic user license (you must register using your student email address and activate the solver from a university network; a license is only valid for one physical computer). Then, install the Julia wrapper from a Julia shell:

julia> Pkg.add("Gurobi")

For an introduction to the language, see the documentation or Andrew Collier’s Month of Julia. For an introduction to JuMP, see the documentation. More detailed examples are available as notebooks (they are not necessarily MILPs!).

Julia also has a more comfortable way of working than a text editor and a console: Juno is a recent IDE for Julia (there is no need to reinstall the packages within Juno).

How to use JuMP?

The first step is to import the required modules, at least JuMP (and a solver if autodetection does not work):

julia> using JuMP
julia> using Cbc # If installed and autodetection does not work
julia> using Gurobi # If installed and autodetection does not work

Then create a model (and associate the solver if needed):

julia> m = Model() # No solver: only use autodetected one
julia> m = Model(solver=CbcSolver()) # Use Cbc
julia> m = Model(solver=GurobiSolver()) # Use Gurobi

Create variables using the @defVar macro (it will automatically create Julia variables):

julia> @defVar(m, x) # Variable x, continuous, no bounds
julia> @defVar(m, y[0:1] >= 10, Int) # Variables y[0] to y[1], integer, greater or equal to 10
julia> @defVar(m, z[0:1, 0:1], Bin) # Variables z[0][0], z[0][1], z[1][0], and z[1][1], booleans

Add some constraints with the @addConstraint macro:

julia> @addConstraint(m, sum(y) >= x)

Add an objective using the @setObjective macro:

julia> @setObjective(m, Max, sum(z))

Print the model with the print() function:

julia> print(m)
Max z[0,0] + z[1,0] + z[0,1] + z[1,1]
Subject to
 y[0] + y[1] - x ≥ 0
 y[i] ≥ 10, integer, for all i in {0,1}
 z[i,j] in {0,1} for all i in {0,1}, j in {0,1}
 x free

Solve the model with the solve() function:

julia> solve(m)

Get the values for the variables with the getValue() function:

julia> getValue(x)

julia> getValue(y)
y: 1 dimensions:
[0] = 10.0
[1] = 10.0

julia> getValue(z)
z: 2 dimensions:
  [0,0] = 1.0
  [0,1] = 1.0
  [1,0] = 1.0
  [1,1] = 1.0

Some tricks

In the REPL, type ; to have access to a standard UNIX shell; type ? for the help mode (equivalent to using the help() function).