Professor: Q. Louveaux.
The practical part of this course is twofold: first, exercise sessions to help you understand the theory; second, projects, to give you some experience about the realworld 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.
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.
#  Date  Agenda  Statement  Other files 

1  18th September 2015  MILP modelling, JuMP installation and first examples  Data files (Julia), spoons example  
2  25th September 2015  Branchandbound, presentation of the first project, modelling  Data file for the teams  
3  2nd October 2015  Q&A about the project, branchandbound implementation  Branchandbound skeleton and implementation  
4  9th October 2015  Modelling, formulation comparison  
11th October 2015  Danger Deadline for the first project  
5  16th October 2015  Correction of the first project, formulation comparison  
6  23rd October 2015  Nothing  
7  30th October 2015  Cuts and valid inequalities  
8  13th November 2015  Cuts and valid inequalities  Prizecollecting travelling salesman problem implementation and knapsack base problem  
9  20th November 2015  Dynamic programming  
22nd November 2015  Danger Deadline for the second project, first part  
10  27th November 2015  Project correction; flow algorithms  
11  4th December 2015  Matching and assignment algorithms  
12  11th December 2015  Constraint programming, project Q&A  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.
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 64bit Julia.
The project must be submitted on the submission platform. Submissions will be accepted till 11th October, 2015, 23:59.
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 1
s. 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.
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 XpressMP, Formulating Integer Linear Programs: A Rogues’ Gallery.
Debugging a MIP model: Detecting the Sources of Model Infeasibility using Gurobi.
Julia is a technical computing programming language, completely free and opensource. 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 opensource 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 closedsource) solver, such as Gurobi. First, download the solver (64bit 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).
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
In the REPL, type ;
to have access to a standard UNIX shell; type ?
for the help mode (equivalent to using the help()
function).