this repo has no description
dekker.one
1# Incremental Meta-Search Experiments
2
3This repository contains benchmarks of meta-search through incremental usage of MiniZinc, included in Jip J. Dekker's PhD Thesis and partially presented in the following paper.
4
5> Dekker J.J., de la Banda M.G., Schutt A., Stuckey P.J., Tack G. (2018) Solver-Independent Large Neighbourhood Search. In: Hooker J. (eds) Principles and Practice of Constraint Programming. CP 2018. Lecture Notes in Computer Science, vol 11008. Springer, Cham. https://doi.org/10.1007/978-3-319-98334-9_6
6
7These experiments concern two model for the incremental solving of MiniZinc models:
8- The usage of propagation engine adjustments that capture some of the context of the current search space. This context can later be accessed by special propagators to enforce properties that are interesting for meta-search. Such as:
9 - The last value a variable has taken
10 - The last solution a variable has taken
11 - A random value, to be assigned by a variable
12- An incremental rewriting engine for MiniZinc instances that minimizes overhead of incremental changes.
13
14These benchmarks tests the effectiveness of these approaches.
15The experiments are conducted on the `gbac`, `radiation`, `rcpsp-wet` and `steelmillslab` problems from the MiniZinc challenge.
16The `radiation` model uses a lexicographic objective.
17The other models are solved using two neighbourhoods for an round robin LNS approach.
18
19## Setup
20
21The script `setup.sh` contains initial configuration of the experiments:
22
23- The amount of time given for the test (120 sec)
24- The amount of repeats for randomised search (10)
25- It adds the correct version of MiniZinc to the `PATH`
26
27The solver versions used are stored in the `software/` folder as git sub-modules.
28The `install.sh` script can be used to compile the solvers and put them in the correct place.
29
30## Run
31
32### Large Neighbourhood Search
33
34The experiments can be run as different parts:
35
36- Regular Gecode (baseline)
37- Regular Chuffed (baseline)
38- Restart Based Gecode (proposal)
39- Restart Based Chuffed (proposal)
40- Recording Gecode (data for replay)
41- Replaying Gecode (ideal case, no computation)
42
43For each part there is a `run_*.sh` script that will run the experiments and put its results into the `output` folder.
44The `run_all.sh` script can be used to run them all in sequences.
45
46### Effort Comparison
47
48## Analyse
49
50### Large Neighbourhood Search
51
52The scripts `analyse_{gecode,chuffed}.py` can be used to process the information gathered during the experiments.
53Each script is specific to that solver.
54It takes the output folder of one of the models as an argument (e.g., `output/gecode/gbac`).
55The script produces a CSV format that can then be processed using software like Excel or Numbers.
56
57The script `cumulative_analysis.py` can generate a PDF plot `output.pdf` for of the cumulative objective value over time.
58It takes the output folder of one of the models and the name of the solver as an argument.
59
60### Effort Comparison