ToolBarIntro
ToolBarIntrotoolbar is a generic solver for WCSP, Max-SAT, and Bayesian Networks. It is a free software under GNU/GPL license. toulbar2 is a new C++ version that includes most algorithms of toolbar, some new ones, the ability to work in collaboration with ILOG Solver, and to deal with big (thousands of variables and/or large domains) problems. A reference to what a WCSP is, and what the algorithms inside toolbar are can be found in:
In the quest of the best form of local consistency for Weighted CSP J. Larrosa & T. Schiex In Proc. of IJCAI-03. Acapulco, Mexico, 2003 http://www.lsi.upc.es/~larrosa/publications/IJCAI03.ps Existential arc consistency: Getting closer to full arc consistency in weighted csps S. de Givry, M. Zytnicki, F. Heras, and J. Larrosa In Proc. of IJCAI-05, Edinburgh, Scotland, 2005 http://www.inra.fr/bia/T/degivry/Heras05.pdf
See a short description of the toolbar collaborative project at http://www.inra.fr/bia/T/degivry/ToolBar.pdf. toolbar and toulbar2 are developped as open source programs and are accessible in our own source forge:
Usage: toolbar [options] problem.wcsp
toolbar version 3.0, an open source solver for Weighted CSP and Max-SAT.
-fFileFormat (0=WCSP, 1=CNF, 2=WCNF). 0 selects the WCSP solver. 1/2 selects the WCNF solver.
-lLocalConsistency (0=NC, 1=AC, 2=DAC, 3=FDAC, 4=EDAC, MaxSAT? only: 5=2-RES, 6=generalized 3-RES)
-S[Number]: (restricted) singleton consistency (with optional number of selected variables for singleton testing)
-d: Koster's dominance rule
-oNumber: preprocessing techniques (only at the root node)
0 : none
1 : Koster's dominance rule
2 : singleton consistency
3 : Koster's dominance rule and singleton consistency
-uUpperBound
-a: count the number of solutions whose cost is strictly less than UpperBound? -cCertificate
-pMaxArity: project nary on binary for small arity
-VNumber: value ordering heuristics
0 : none (file order)
1 : min unary cost (ties broken lexic.)
2 : min unary cost (ties broken randomly)
-HNumber: variable ordering heuristics (ties are broken lexicographically
0 : none (file order)
1 : max degree
2 : random static
3 : random dynamic
4 : min domain (ties broken lexic.)
5 : min domain by degree (ties broken lexic.)
6 : 2-sided Jeroslow like (ties broken lexic.)
7 : 2-sided Jeroslow like (ties broken randomly)
-TNumber: compute a cluster tree decomposition
0 : max cardinality
1 : min fill
3 : min width
4 : Koster
-g: export the tree-decomposition and the graph to two postscript files tree.eps and graph.eps
-qFileName: save problem in WCSP format after preprocessing is done and quit. -Wnumber (with -q): saves problem in WCNF instead of WCSP format. -W0: direct enc., -W1 log enc. (max 64 values)
-tTimeLimit (in seconds, 0 means infinity)
-nNodeLimit
-eElimLevel (<=2)
-sNumber: seed for random generator
-v[Number]: verbose (with optional verbosity level)
-i: bucket elimination resolution. The ordering of the variables is the one from -T option, or by default, the lexicographical one.
-wNumber: the resulting function of each mini-bucket is not bigger than 2^Number. By default, Number=maximum_domain^w*. The feasible limit is Number=32.
-m: Apply max-sat rules in cnf/wcnf files.
-R: Apply local search in cnf/wcnf files. maxwalksat should be in the same directory.
-h: this help
If no filename is present, standard input is used.
WCSP DEFAULTS: -f0 -l4 -o0 -V1 -H5 -t0 -n4294967295 -e-1 -s0 -p2
Max-SAT DEFAULTS: Similar to WCSP DEFAULTS but -l6
If no filename is present, standard input is used.
For Unix and Windows. Download the latest stable source codes (version 3.1) as a gizp'd tarball from: http://mulcyber.toulouse.inra.fr/frs/download.php/635/toolbar.3.1.tgz
Javier Larrosa, Thomas Schiex, Federico Heras, and Simon de Givry. 2005
http://mulcyber.toulouse.inra.fr/frs/download.php/656/toolbarbtd.2.3.tgz
The winner of the MaxCSP? Competition 2006 (http://cpai.ucc.ie/06/COMPETITION06.pdf) exploits a tree decomposition. It can solve Bayesian Networks (MPE task) in ergo format.
Exploiting tree decomposition and soft local consistency in weighted csp S. de Givry, T. Schiex, and G. Verfaillie In Proc. of AAAI-06, page 6p., Boston, MA, 2006 http://www.inra.fr/bia/T/degivry/Schiex06a.pdf
toulbar2 includes binary and ternary local consistency EDAC, and also VAC (only binary cost functions) and BAC (only simple arithmetic and disjunctive cost functions). It also exploits the structure of the constraint graph through restricted variable elimination, pseudo conflict-backjumping, and branch and bound with tree decomposition.
Bound arc consistency for weighted CSPs M. Zytnicki, C. Gaspin, S. de Givry, T. Schiex. To appear in JAIR, 2009. Russian Doll Search with Tree Decomposition M. Sanchez, D. Allouche, S. de Givry, T. Schiex Proc. of IJCAI'09. 2009. Pasadena (CA). USA. http://www.inra.fr/mia/T/schiex/Export/IJCAI2009.pdf Virtual Arc Consistency for Weighted CSP. M. Cooper, S. de Givry, M. Sanchez, T. Schiex and M. Zytnicki. Proc. of AAAI'2008. Chicago, USA. http://www.inra.fr/mia/T/schiex/Export/AAAI2008.pdf Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques M. Sanchez, S. de Givry, and T. Schiex Constraints, 13(1), 2008 Special issue on Bioinformatics and Constraints http://www.inra.fr/mia/T/schiex/Export/Constraints2007a.pdf
Usage: toulbar2 problem.wcsp [upperbound] [options]
Available problem formats (specified by the filename extension):
*.wcsp : wcsp format
*.xml : XML format XCSP 2.1
*.uai : Bayesian network (UAI-08) format followed by an optional evidence filename (MPE task)
*.pre : pedigree format
*.bep : BEP (satellite scheduling) format
Alternatively one call the random problem generator:
bin-{n}-{m}-{p1}-{p2}-{seed}
p1 is the tightness in percentage
p2 is the num of binary constraints to include
the seed parameter is optional
or:
binsub-{n}-{m}-{p1}-{p2}-{seed} binary submodular cost functions (p1 unused) (plus 10 permutations of two randomly-chosen values for each domain)
or:
tern-{n}-{m}-{p1}-{p2}-{p3}-{seed} p3 is the num of ternary constraints
or:
nary-{n}-{m}-{p1}-{p2}-{p3}...{pn}-{seed}
Initial upperbound is optional (default value: 1537228672809129301)
Available options (use symbol ":" before an option letter to remove a default option):
v : verbosity (repeat this option to increase the verbosity level)
s : show each solution found
g : sort pedigree by increasing generation number and if equal by increasing individual number
u[integer] : add a penalty weight (must use option y also) on genotyped individuals depending on the number of their genotyped children in order to penalize genotyping removals if the number of genotyped children is strictly greater than a given threshold
w[mode] : write last solution found
and for pedigree problems:
mode=0: save pedigree with erroneous genotypings removed
mode=1: save pedigree with erroneous genotypings corrected
mode=2: save pedigree with erroneous genotypings corrected and missing genotypes of informative individuals inferred
y [genotypinpErrorRate probabilityPrecision genotypePriorMode] : pedigree solved by Bayesian MPE
y must be the last option in the command line followed by three arguments:
genotypingErrorRate is a prior uniform probability of genotyping errors (default value: 0.05)
probabilityPrecision is a conversion factor (a power of ten) for representing fixed point numbers (default value: 7)
genotypePriorMode selects the prior mode for allele probability distribution (default value: 0)
= 0 : uniform allele probability distribution
= 1 : allele probability distribution read from pedigree data
= 2 p1 p2 p3...: allele probability distribution given explicitely in the command line
a : find all solutions
b : binary branching always instead of binary branching for interval domains and n-ary branching for enumerated domains (default option)
c : binary branching with conflict-directed variable ordering heuristic (default option)
q : weighted degree variable ordering heuristic
d : dichotomic branching instead of binary branching when current domain size is strictly greater than 10 (default option)
e[integer] : boosting search with variable elimination of small degree (less than or equal to 3) (default option)
p[integer] : preprocessing only: variable elimination of degree less than or equal to the given value
t : preprocessing only: project ternary constraints on binary constraints and apply 3-consistency
h : preprocessing only: project ternary constraints on binary constraints following a heuristic
o : ensure optimal worst-case time complexity of DAC and EAC (can be costly in practice)
k[integer] : soft local consistency level (NC=0, AC=1, DAC=2, FDAC=3, EDAC=4)
l : limited discrepancy search
i : initial upperbound found by INCOP local search solver
z : save current problem in wcsp format
Z : debug mode (save problem at each node if verbosity option set!)
x : load a solution from a file
M[integer] : Min Sum Diffusion on preprocessing
A[integer] : enforce VAC at search nodes with depth less than a given threshold
T[integer] : threshold cost value for VAC
P[integer] : threshold cost value for VAC during the preprocessing phase
C[integer] : multiply all costs by this number
S : singleton consistency on preprocessing
B[integer] : (0) DFBB, (1) BTD, (2) RDS-BTD, (3) RDS-BTD with path decomposition (default value: 0)
O[filename] : read variable elimination order from a file (if not specified, then use variable order in which variables appear in the problem file)
j[integer] : split larger clusters into a chain of smaller embedded clusters with a number of proper variables less than this number (B3j1 for pure RDS)
r[integer] : limit on maximum cluster separator size
E : merge leaf clusters with their fathers if small local treewidth (in conjunction with option e)
R[integer] : choice for root cluster
I[integer] : choice solving only a particular subtree
For Unix and Windows.
Download the latest stable source codes (version 0.8) as a gizp'd tarball from: http://mulcyber.toulouse.inra.fr/frs/download.php/740/toulbar2_08.tgz
Since releases higher than 0.5, you can choose the type of cost values. Depending on your problem, change the type of cost values in file tb2types.hpp before compiling. For instance by replacing #define LONGLONG_COST by #define INT_COST if using only 4-Bytes integer weights.
Charles Fai-keung Siu, Hélène Fargier, Emma Rollon, Marti Sanchez, and Matthias Zytnicki have also contributed to the source codes.
return to AlgorithmS