# Optimisation Algorithms M

# Teacher

Prof Paolo Toth (paolo.toth@unibo.it)

Office hours: Tue 11:00 - 13:00, DEI 2nd floor, phone: 93028

# Slides

- Introduction
- Logical constraints
- KP01 and Complexity
- Models (A)
- Models (B)
- VCP
- ATSP
- Branch and bound
- Algorithms for knapsack
- Algorithms for set covering
- Algorithms for the ATSP
- Algorithms for vertex colouring
- Exercises (Part 1)
- Exercises (Part 2)
- Solutions (Part 1)
- Solutions (Part 1-A)
- Solutions (Part 1-B)

# CPLEX Exam Solution

A possible solution to the CPLEX exam can be found here.

# CPLEX

Cplex can be obtained in the following ways:

- Downloading the community edition.
- Registering to the IBM Academic Initiative and downloading the student edition.
- Bringing an USB stick on the first day of lab lectures, and getting a copy (Linux, Mac OS, Windows versions available) which you will: 1. only use for the purposes of this course, and 2. delete at the end of the course.
- Downloading the pre-configured virtual machine.

# The Virtual Machine

The link above lets you download a pre-configured Virtual Machine, which will only be available for the duration of the course.
You can run it by first installing VirtualBox.
The username is *student* and the password is *cplex*.
Once logged in, you can have a look at a C++ programme which uses Cplex, and solves the IMRT problem.
Open a terminal (icon on the top bar), and type `cd local/src/imrt`

to get to the code folder.
The sample programme can be compiled with `sh compile.sh`

and, then, executed with `./imrt`

.
To have a look at the source files, you can use for example *Visual Studio Code*, which is also installed and is available on the top bar.

# Blank Visual Studio project

A blank Visual Studio project ready to be used with Cplex is here: BlankCplexProject.

# CPLEX Documentation

Documentation for the most commonly used CPLEX classes can be downloaded here: cplex_doc.zip. These are the same files that you will use during the exam.

# The IMRT Leaf Sequencing problem

The problem description can be downloaded here: imrt.pdf.

The file containing problem data can be downloaded here: imrt.h.

The file containing the main programme can be downloaded here: main.cpp.

# The Basket Coach problem

The problem description can be downloaded here: basket.pdf.

The Visual Studio project can be downloaded here: BasketProject.

# The Diet problem

The problem description can be downloaded here: diet.pdf.

The Visual Studio project can be downloaded here: DietProject.zip.

An example solution can be downloaded here: DietProjectSolution.zip.

# The Project Scheduling problem

In this problem, we have to schedule *n* activities to complete a project.
Each activity *i* has a duration *d _{i}*.
Furthermore, we are given a list

*P*of pairs

*(i,j)*. Each pair represents a precedence relation between activities, meaning that activity

*j*cannot start before activity

*i*is completed.

We solve this problem using a non-negative real variable *t* to record the total completion time, and non-negative real variables *s _{i}* to record the start time of each activity

*i*. A model for this problem aims at minimising

*t*, while respecting the following two constraints:

*s*for all activities_{i}+ d_{i}≤ t*i*;*s*for all pairs_{i}+ d_{i}≤ s_{j}*(i,j)*.

Code to solve this problem is given here:

` ````
#define IL_STD
#include <ilcplex/ilocplex.h>
#include <array>
#include <utility>
#include <vector>
#include <numeric>
int main() {
// --- Data ---
const int n_activities = 6;
const std::array<double, 6> durations = { 1.0, 3.0, 2.0, 6.0, 3.0, 1.5 };
std::vector<std::pair<int, int>> predecessors;
predecessors.push_back(std::make_pair(0, 2));
predecessors.push_back(std::make_pair(0, 3));
predecessors.push_back(std::make_pair(1, 4));
predecessors.push_back(std::make_pair(1, 5));
predecessors.push_back(std::make_pair(2, 4));
predecessors.push_back(std::make_pair(3, 4));
const double sum_of_durations =
std::accumulate(durations.begin(), durations.end(), 0);
// --- Here starts your code ---
IloEnv env;
IloModel model(env);
IloNumVar tot(env, 0, sum_of_durations, IloNumVar::Float);
IloNumVarArray start(env, n_activities, 0, sum_of_durations, IloNumVar::Float);
// Minimize variable tot:
model.add(IloObjective(env, tot));
// Constraints 1:
for(int i = 0; i < n_activities; ++i) {
model.add(start[i] + durations[i] <= tot);
}
// Constraints 2:
for(unsigned int k = 0; k < predecessors.size(); ++k) {
int i = predecessors[k].first, j = predecessors[k].second;
model.add(start[i] + durations[i] <= start[j]);
}
IloCplex cplex(model);
try {
if(cplex.solve()) {
for(int i = 0; i < n_activities; ++i) {
std::cout << cplex.getValue(start[i]) << "\n";
}
std::cout << "Total: " << cplex.getValue(tot) << "\n";
} else {
std::cerr << "Cplex problem infeasible\n";
}
} catch(IloException& e) {
std::cerr << e.getMessage() << "\n";
}
env.end();
return 0;
}
```