Discrete Optimisation (MATH0462), 2016-2017

General information

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: thales02.montefiore.ulg.ac.be. 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).

In English: Coursera’s Discrete Optimization and Advanced Modeling for Discrete Optimization
In French: EnsROtice

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: Data for exercise 1. Solution. Data for exercise 2. Solution to part 1. Solution to part 2. Data for exercise 3. Solution. Data for exercise 4. Solution to part 1. Solution to part 2. Data for exercise 5. Solution.
3	7 October 2016	Advanced MILP modelling, presentation of the first project	Statement [Julia files](/files/math0462-2016/R3_julia.zip): Data for exercise 10. Data generator. Solution. Figures: Illustration of the NOT constraint (exercise 1): y = NOT x. Illustration of the OR constraints (exercise 2), interactive 3D plot ^CDF?: z = x OR y. Illustration of the AND constraints (exercise 3), interactive 3D plot ^CDF?: z = x AND y. Illustration of the implication (exercise 4): x IMPLIES y. Illustration of the if-then constraints (exercise 5) for M = 100 (tightest choice), M = 50 (too small: some points are not feasible while they should), M = 200 (too large: the formulation is not as tight as possible): IF y = 1 THEN x = 100. Illustration of the binary activation (exercise 6): IF y = 1 THEN x >= 100 ELSE x = 0. Illustration of a semicontinuous variable (exercise 7): x IN 0 OR [50, 100]. Illustration of a threshold detection (exercise 8): y = 1 IF x >= 50 ELSE 0. See also: big M and convex hull.
4	14 October 2016	Branch-and-bound algorithm	Statement Figures: Graphical B&B (exercise 1): feasible region, first branching, second branching, third branching, fourth branching, B&B tree. B&B tree exploration node by node (exercise 2). B&B inefficiency (exercise 3): step 0 (feasible area), step 1 (simplex solution), step 2 (after branching), step 3 (simplex solution), step 4 (after branching), step 5 (simplex solution), step 6 (after branching), step 7 (simplex solution), step 8 (after branching), step 9 (simplex solution). See also: basic principles behind a modern MIP solver (includes branch and bound, but also more advanced topics covered in the following lectures)
5	21 October 2016	Formulation comparison	Statement Julia file: Data and solutions for exercise 1. See also: About the TSP: no polynomial formulation exists original formulation (subtour elimination) due to Dantzig, Fulkerson, Johnson a survey of various models
6	28 October 2016	Advanced solver usage, Q&A for the project and the exercise sessions	Slides Julia files: small infeasible problem (corresponding LP file, IIS in LP format), solving the TSP with subtour elimination constraints added lazily. See also: About MIP start: Gurobi example (C and Python) CPLEX documentation About infeasibility detection: algorithms to analyse the cause of infeasibility complete example of IIS retrival within JuMP using Gurobi About lazy constraints and cutting planes: cutting planes vs lazy constraints worked example of lazy constraints (old version of JuMP; syntax translation guide) worked example of user cut (old version of JuMP; syntax translation guide)
7	4 November 2016	Constraint programming	Statement ECLiPSe is a constraint-programming modelling environment based on Prolog. Download it: ECLiPSe Windows x64, ECLiPSe Linux and macOS x64. ECLiPSe solutions: sudoku (exercise 1): skeleton, solution, magic squares (exercise 2): solution, N queens (exercise 3): solution. A catalogue of existing global constraint with propagator algorithms and existing implementations
7	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: Exercise 1.1. Exercise 1.2. Exercise 1.3.
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: PCTSP: skeleton, Solution.
9	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: LightGraphs.jl, in Julia NetworkX, in Python Boost Graph Library, in C++
11	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:

the statement,
a first (very simple) instance #0,
the set of instances (from the easiest one #0 to the hardest one #7),
a code skeleton that implements one possible public interface for your program.

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:

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