University of Liège — Thibaut Cuvelier | PhD student at Montefiore Institute

Discrete Optimisation (MATH0462), 2016-2017

General information

Professor: Q. Louveaux.

Course page.

If you have any question about the exercises or the projects, come to my office or drop me a line to make an appointment.

The practical part of this course is two-fold:

  • exercise sessions to help you understand the theory;
  • 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.

How to use Julia on the university machines?

  • Thalès compute server address: Credentials (login starting with od_group) will be provided for the second project. To get access to the required tools, first type this command: GUROBI_HOME=/usr/ julia -E "Pkg.add(\"JuMP\"); Pkg.add(\"CPLEX\"); Pkg.add(\"Gurobi\")". Julia is then available as julia.
  • Lab accounts (MS800). An old version of Julia is installed on these computers (0.3), along with the necessary tools for this course (albeit outdated).

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: January 03 2017 19:01:25).

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: Figures: See also, for more modelling tricks:
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 Info Day off.
8 18 November 2016 Correction of the first project, cuts and valid inequalities Statement
9 25 November 2016 Cuts and valid inequalities Info No theoretical course on this day: the exercise session begins at 14:00.
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 Info The course will exceptionnally take place in the R75 room.
9 December 2016 Info 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 partly come 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.

Project 1: modelling within games

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

Alterations to the statement and the provided files:

  • 2016-10-13, 11:50: typo in the first question (reversed production and consumption),
  • 2016-10-19, 15:40: removed a useless constant from the data file (storage_capacity_max),
  • 2016-10-25, 15:20: a few precisions (boat travel times are integers; loading and unloading are instantaneous),
  • 2016-10-26, 15:30: make the initial conditions explicit for the fourth question,
  • 2016-10-26, 18:10: clarifications about the moment when the boats are allowed to start (no constraint is imposed),
  • 2016-10-28, 17:30: typo in Table 2 (consumption of a weaver's hut),
  • 2016-10-29, 18:00: removed useless constants from the data file (boat_points),
  • 2016-10-30, 14:30: precision about the definition of the revenues and costs (expressed per minute),
  • 2016-11-02, 11:50: reworded sentence about the number of merchants per minute for clarity.

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.

Since December 2, the results are available on the submission platform. The comments are in the following format:

  • Q1, code (maximum 1 point)
  • Q1, report (maximum 1 point)
  • Q2, code (maximum 2 points)
  • Q2, report (maximum 2 points)
  • Q3, code (maximum 2 points)
  • Q3, report (maximum 2 points)
  • Q3, second question (maximum 2 points)
  • Q4, code (maximum 2 points)
  • Q4, report (maximum 2 points)
  • Q4, second question (maximum 2 points)
  • Q4, third question (maximum 2 points)
  • total for code (maximum 7 points)
  • total for report (maximum 13 points)
  • total (20 points), with the code and the report having the same weight
  • comments

Project 2: paper scheduling

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

Alterations to the statement and the provided files:

  • 2016-11-16, 15:00: missing data in the statement (minimum transition times),
  • 2016-11-21, 17:35: description of the file formats in the statement; a first instance and a code skeleton are now available,
  • 2016-11-22, 12:45: example mixing the minimum production time and the mill shutdowns; typo (only one optimisation horizon),
  • 2016-11-24, 17:30: removed all references to a challenge; eight instances are now available,
  • 2016-12-02, 10:15: updated the skeleton's documentation to be easier to understand,
  • 2016-12-11, 04:50: updated the skeleton to show the way to define functions and scripts in Julia,
  • 2016-12-15, 15:30: submissions will be allowed until Monday 19, 10:00.

Projects: 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, Thalès, or your own (with platform and bitness, if relevant). Don't assume any knowledge on my side 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, MOSEK Modeling Cookbook, Formulating Integer Linear Programs: A Rogues’ Gallery.

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

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.

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

  • For Windows: download the 64-bit package, follow the wizard steps; Julia will be accessible from the Start menu/screen.
  • For macOS: download the DMG image, mount it, copy the application to your Applications folder.
  • For Linux: select the right package type.

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

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)

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

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 0.12- JuMP 0.13+
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)

Julia tricks

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

Last modification: January 03 2017 17:28:15.