Alberto Santini

Optimisation Algorithms M

Teacher

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

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

Tutor

Alberto Santini (a.santini@unibo.it)

Office hours: By mail

Slides

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 di. 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 si to record the start time of each activity i. A model for this problem aims at minimising t, while respecting the following two constraints:

  1. si + di ≤ t for all activities i;
  2. si + di ≤ sj for all pairs (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;
}