DM841 (E21) - Heuristics and Constraint Programming for Discrete Optimization

Obligatory Assignment 4

This is the fourth obligatory assignment of DM841 to be carried out in groups of two members. In case the number of members is different from two discuss the situation with the teacher.

The deadline is Monday, December 13, at noon. You have to submit a short report in PDF and the Python files implementing the heuristics described.

A starting package containing instance files and instance readers has been pushed into your git repository.

The problem

The aim of this assignment is to design, implement and report local search heuristic algorithms for solving general binary programming problems, which are integer linear programming problems in which all variables are binary. They can be written in the form:

$\begin{aligned} \min \: & \sum_{j=1}^n c_j x_j\\ &\sum_{j=1}^na_{ij} x_j\lesseqgtr b_i&\forall i =1,\ldots,m\\ &x_j\in \{0,1\}&\forall j=1,\ldots,n\end{aligned}$

These problems are also known as pseudo-boolean optimization problems and when an optimization criterion is missing as pseudo-boolean decision problems.

Generalized set covering, set partitioning and set packing are examples of binary programming problems, which can be used to model a wide variety of real life problems like crew scheduling and routing.

In the assignment, we will focus on the instances from past PB challanges:

All instances should have been normalized and those with an objective function should have been put in minimization form.

Your Tasks

You are asked to carry out the following tasks:

Design and implement one or more construction heuristics
Design and implement one or more iterated improvement algorithms.
Design and implement stochastic local search or metaheuristic algorithms that use the procedures from the previous two points.
Undertake an experimental analysis where you compare and configure the algorithms from the previous point. Report the results in a table.
Describe the work done in a report of at most 5 pages. The report must at least contain a description of the best algorithm designed and the experimental analysis conducted. The level of detail must be such that it makes it possible for the reader to reproduce your work.
Submit your best algorithms and your report via the git procedure illustrated in Assignment 1.

Overall use a time limit of 120 seconds for your runs.