Professor: Q. Louveaux.

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.

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 | Branch-and-bound, presentation of the first project, modelling | Data file for the teams | |

3 | 2nd October 2015 | Q&A about the project, branch-and-bound implementation | Branch-and-bound 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 | Prize-collecting 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 | [PDF]/files/math0462-2015/R12_cp.pdf | 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:

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

This second project is about carsharing. Available files:

- the statement
- an example of input: the graph (nodes and edges) and some users.

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

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