Discrete Optimisation (MATH0462), 2016-2017

General information

Professor: Q. Louveaux.

Course page.

The practical part of this course is two-fold:

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.

How to use Julia on the university machines?

What online courses do you recommend?

You may also have a look at a French portal on operational research, with many interesting links. It also includes a Julia section.

Publicly available slides for the theoretical course

Exercise book

An exercise book is being prepared for this course. The current version is already available, and contains the exercises done during the exercise sessions and some supplementary ones. Not all exercises are part of the course syllabus; please refer to the contents of the exercise sessions.

Download current version (last edition: June 29 2017 12:41:32).

Exercise sessions

# Date Agenda Downloads
1 23 September 2016 A Gentle Introduction to Julia for Optimisation. Slides
More complete slides. These also contain conic constraints and the Convex.jl modelling layer, which may be useful for the second project.
2 30 September 2016 MILP modelling Statement
Julia files:
3 7 October 2016 Advanced MILP modelling, presentation of the first project Statement
[Julia files](/files/math0462-2016/R3_julia.zip): Figures: See also: big M and convex hull.
4 14 October 2016 Branch-and-bound algorithm Statement
Figures: See also:
5 21 October 2016 Formulation comparison Statement
Julia file: See also:
6 28 October 2016 Advanced solver usage, Q&A for the project and the exercise sessions Slides
Julia files: See also:
7 4 November 2016 Constraint programming Statement
ECLiPSe is a constraint-programming modelling environment based on Prolog. Download it: ECLiPSe solutions: A catalogue of existing global constraint with propagator algorithms and existing implementations
4 November 2016 Danger Deadline for the first project
11 November 2016 Note Day off.
8 18 November 2016 Correction of the first project, cuts and valid inequalities Statement
Figures:
9 25 November 2016 Cuts and valid inequalities Note No theoretical course on this day: the exercise session begins at 14:00.
Statement
Julia files:
25 November 2016 Danger Deadline for the first part of the second project
10 2 December 2016 Correction of the second project, modelling with flows Note The course will exceptionnally take place in the R75 room.
Statement
9 December 2016 Note No exercise session.
11 16 December 2016 Solving flow problems Statement
See also real implementations of these algorithms:
16 December 2016 Danger Deadline for the second part of the second project
23 December 2016 Danger Project presentations

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

How to open CDF files?

You may use Mathematica (the university offers a license for students) or the CDF Player.

Projects

Project 1: modelling within games

This first project is about the video game Anno 1404. Available files:

The project must be submitted on the submission platform. The platform is not yet updated for this year. Submissions will be accepted till 4 November, 2016, 23:59:59.

An implementation of a solution is available.

Project 2: paper scheduling

This second project is about scheduling in the paper industry. Available files:

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:

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

Julia

Julia Step by Step

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, albeit far from recent. It is not necessary to follow this procedure on those computers (including Gurobi with a network license). This version of Julia should be sufficient for most of your work (except the new JuMP syntax or lazy constraints).

First, download Julia 0.4 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), there is also an experimental Eclipse extension for Julia.

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 @variable macro (it will automatically create Julia variables):

julia> @variable(m, x) # Variable x, continuous, no bounds
julia> @variable(m, y[0:1] >= 10, Int) # Variables y[0] to y[1], integer, greater or equal to 10
julia> @variable(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 @constraint macro:

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

Add an objective using the @objective macro:

julia> @objective(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)
20.0

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

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

What are the differences in syntax between JuMP 0.12- and 0.13+?

Between the versions 0.12 and 0.13, JuMP changed its syntax. Using the old syntax still works with the new versions, but emit warnings; however, the new syntax does not work with the older versions. The difference is important, as an old version of JuMP is installed on the MS800 machines: only the old syntax works there.

Meaning JuMP up to 0.12 JuMP between 0.13 and 0.18
Defining a variable @defVar(model, variable, class) @variable(model, variable, class)
Defining a constraint @addConstraint(model, constraint) @constraint(model, constraint)
Defining the objective function @setObjective(model, sense, expression) @objective(model, sense, expression)
Getting the value of a variable after optimisation getValue(variable) getvalue(variable)
Getting the objective value after optimisation getObjectiveValue(model) getobjectivevalue(model)

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).