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

Introduction

Resit

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

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

Projects

Project 1: modelling

This first project is about lorry dispatching. Available files:

• the statement
• the data structures for the input data and outputs, including a first data set
• a stub defining the name of the functions to write
• the test file that will be used to load the data and call the functions to hand in (the only executable file)

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 statement
• an example of input: the graph (nodes and edges) and some users
• more test inputs

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.

Julia

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:

• For Windows: download the 64-bit package, follow the wizard steps; Julia will be accessible from the Start menu/screen.
• For OS X: 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!).

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

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