DM841 (E23) - | Heuristics and Constraint Programming for |
Discrete Optimization |
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 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.
You are asked to carry out the following tasks:
Design and implement metaheuristics based on construction heuristics and local search.
Undertake an experimental analysis where you configure and compare the algorithms from the previous point.
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:
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:
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.
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:
--seed
must be implemented.--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.
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.
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.