------------------------------------------------------------------------------------------------
Anytime Hybrid Best-First Search with Tree Decomposition for Weighted CSP
David Allouche, Simon De Givry, George Katsirelos, Thomas Schiex, Matthias Zytnicki
In Proc. of CP'15, Cork, Ireland, 2015
------------------------------------------------------------------------------------------------

Benchmarks
----------
-MRF: Probabilistic Inference Challenge 2011
http://www.cs.huji.ac.il/project/PASCAL/realBoard.php
-MRF: UAI 2008 Evaluation 
http://graphmod.ics.uci.edu/uai08/Evaluation/Report/Benchmarks
-MRF: Computer Vision and Pattern Recognition (CVPR) OpenGM2 Benchmark
http://hci.iwr.uni-heidelberg.de/opengm2/
-WPMS: Weighted Partial Max-SAT Evaluation 2013
http://maxsat.ia.udl.cat:81/13/benchmarks
-CFN: CFLib, library of Cost Function Networks
http://costfunction.org/benchmark
-CP: MiniZinc Challenge 2012 and 2013
http://www.minizinc.org/challenge2012/results2012.html
http://www.minizinc.org/challenge2013/results2013.html
-MaxCSP: CSP and Max-CSP 2008 Competition
http://www.cril.univ-artois.fr/CPAI08/
http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html

Download benchmarks in all formats (uai, wcnf, wcsp, lp, mzn&dzn)
-----------------------------------------------------------------
wget -r -nH --no-parent -e robots=off --cut-dirs=1 http://genoweb.toulouse.inra.fr/~degivry/evalgm

or only a specific category, e.g. cost function networks:
wget -r -nH --no-parent -e robots=off --cut-dirs=2 http://genoweb.toulouse.inra.fr/~degivry/evalgm/CFN

Solvers
-------
-daoopt  version 1.1.2
https://github.com/lotten/daoopt
-toulbar2 version 0.9.8
http://mulcyber.toulouse.inra.fr/projects/toulbar2/ in the bfs branch.

Parameters
----------
We used a cluster of 48-core Opteron 6176 nodes at 2.3 GHz with 378 GB RAM, with a limit of 24 simultaneous jobs per node.
For all methods/solvers, 1 core with 3600 seconds CPU-time and 8 GB RAM limits.

-daoopt  version 1.1.2 (no local search, no LDS, single min-fill ordering)
BRAO-i15:
daooptW -y -i 15 --slsX=0 --lds -1 -m 125 -t 1
BRAO-i35:
daooptW -y -i 35 --slsX=0 --lds -1 -m 4096 -t 1

-toulbar2 version 0.9.8
DFS:
 -O=-3
LDS:
 -O=-3 -l=1024
Luby:
 -O=-3 -L=1000000000
HBFS:
 -O=-3 -hbfs
BTD:
 -O=-3 -B=1
BTD-HBFS:
 -O=-3 -hbfs -B=1
BTD-r4:
 -O=-3 -r=4 -B=1
BTD-HBFS-r4:
 -O=-3 -hbfs -r=4 -B=1

Results
-------
See file results_hbfs3600_with_bounds.html for an HTML table presenting the results with anytime lower and upper bound curves associated to each instance.
See also results_hbfs3600_normalized directory containing normalized anytime curves per problem category.

Legends for results_hbfs3600.csv columns
-------------------------------
- Problem: instance name
- nbvar: number of variables
- max_dom: maximum domain size
- nbconstr: number of potentials/cost-functions/constraints
- max_arity: maximum arity of potentials/cost-functions/constraints

Followed by, for each method/solver in this ordering:
toulbar2 DFS, LDS, Luby, HBFS, BTD, BTD-HBFS, BTD-r4, BTD-HBFS-r4, daoopt BRAO-i15, BRAO-i35
- bestsol: cost of the best solution found (or "?" if no solution found)
- time: CPU time to end the search (or "mem" if memory error occured, or "ARITY" if translation to MRF/potentials not possible due to large clause arity, or "N/A" if the corresponding encoding was not available)
- status: S (solution found), C (optimum found and proved), UNK (no solution found within the time limit)

Known problem issues
--------------------
- Instances CP/Warehouse/capmo1-5.dzn, CP/Warehouse/capmp1-5.dzn, CP/Warehouse/capmq1-5.dzn (resp. CP/Warehouse/capa-b-c.dzn) have all their cost values divided by 100 (resp. multiplied by 10) compared to wcsp/wcnf/lp instances
- Problem sizes (nbvar,maxdom,nbconstr,maxarity) are unavailable if min-fill heuristic in preprocessing does not terminate before the deadline
- Different problem optimum reported bewteen MRF solver (daoopt) and toulbar2 due to double/integer conversions (Linkage/pedigree34-50, MIPLib/p0033, ImageAlignment/fileforGal_400markers, Auction/cat_sched_60_170_0001). First, MRF instances (except CVPR) were translated into CFN instances using 2-digit precision. Then, the resulting wcsp instances were translated back to uai instances (_digit2 extension) in order to optimize the same objective function.
- All CVPR instances in wcnf format are using 2-digit precision, in wcsp and lp formats are using 8-digit precision (except some instances already using integer potentials), in uai format are using floating-point numbers. 
- Instance WPMS/MIPLib/normalized-mps-v2-20-10-mod008.opb.msat cannot be translated in uai format (clause arity too large (93))