DM841 (E23) -  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 18, at noon. You have to submit a short report in PDF and the Python files implementing the heuristics described.

A starting package containing the problems instances and an API for the solvers together with instance readers is available in your git repository. You can start getting familiar with the API reading the documentation.

For this and the next assignment it is recommended to use the PyPy alternative implementation of Python (the latest version is v7.3.13). The standard Python interpreter (v3.9 or above) will also work. Pypy can give much faster execution (up to 20x), as long as you stick to plain Python code (no numpy or other extension modules written in C).

The problem

The aim of this assignment is to design, implement and report 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 (PB) 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.

  1. A description of the problem considered
  2. Modelling decisions, such as the definition of the decision space, construc- tion rule, and neighbourhood structure
  3. Implementation decisions, including solution, component and local move representation, generation, and evaluation
  4. Preliminary experimental results

Your Tasks

You are asked to carry out the following tasks:

  1. Design and implement metaheuristics based on construction heuristics and local search.

  2. Undertake an experimental analysis where you configure and compare the algorithms from the previous point.

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

    The report must present:

    • the modeling decisions:
      • local search compoenents,
      • solution components construction rules
    • a sketch of the algorithm developed
    • the implementation decisions:
      • delta evaluation
      • neighborhood search
      • computational costs of the step in local search or the construction rule
    • the best results on the given instances in a table.

  4. Submit the program of your best algorithms and your report via the git procedure illustrated in Assignment 1.

It is recommended to proceed by considering first the design, implementation and experimentation of:

  1. greedy algorithms
  2. iterated improvement algorithms.

The results of these and of their random restart metaheuristics are to be used as the baseline for the experimental comparison.

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

Instructions for the Submission via Git

Your repository must at least contain:

  • src/ the source files that implement the algorithm

  • Makefile as handed out

  • src/base.py the file to call to run your algorithm

  • data/ containing the test instances.

  • res/ containing your results, the performance measurements

  • r/ statistics, data analysis, visualization

  • doc/ a description of the algorithms.

  • log/ other log files produced by the run of the algorithm

The programs will run on a machine with at least Python 3.8 (Python 3.10).

The program must run with the following parameters from command line: instance file, output file, seed and time limit:

$ python3 src/base.py --budget 120 --seed 1 --log-level info --log-file log.txt \
--output-file instance.sol instance.opb.bz2

No other parameter need to be specified. If you have any, then you will need to hard code their deafults.

Note that:

  • the option --seed must be implemented.
  • the option --budget must be implemented. The framework distinguishes --lbudget and --cbudget for local search and constructive search respectively.

The program will be killed externally at the time limit if it did not terminate already. Hence make sure that you output in time the best solution you found during the search.

All output must go in the standard output and in the output file. Do not create other files. The files must be in ASCII format and the output file must contain the solution certificate in the format described in the next section. Your solutions will be verified by an external program.

Solution Format

Output: There is no specific order in the solvers output lines. However, all lines, according to its first character, must belong to one of the three following categories:

  • comments (any information that authors want to emphasize), beginning with the two chars “c “

  • solution (satisfying all constraints or not). Only one line of this type is allowed. This line must begin with the two chars “s “ and must be one of the following ones:

    s FEASIBLE
s INFEASIBLE

  • values of a solution (if any), beginning with the two chars “v “ (explained below).

The line starting with “v “ must provide a 0-terminated sequence of the indices of the variables that are set to one. All variables whose indices are not listed are set to zero. Arbitrary white space characters, including ordinary white spaces and tabulation characters, are allowed between the indices, as long as the line containing the indices is a value line, i.e. it begins with the two chars “v “.

The certificate in a value line must be provided in both cases of a feasible and infeasible solution.

Note that indices must start from 1 and not from 0.

For instance, the following output is valid for a given instance:

mycomputer:~$ ./mysolver myinstance-sat
c mysolver 6.55957 starting with SATTIMEOUT fixed to 120s
c Trying to guess a solution...
s FEASIBLE
c Objective 2000
v 3 4 6 18 21 1 7 0
c Time: 234s.

Benchmark instances

A set of benchmark instances has been made available in the git repository. There are two categories: DEC-SMALLINT-LIN and OPT-SMALLINT-LIN. The former contains 180 satisfiability instances and the latter 97 optimization instances. The best known results are available from a supplementary page. In the final assessment a random subset of these instances will be selected and used to compare your algorithms.