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 (under new BSD license) 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/toulbar2 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 at INRA 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 (BB-VE(2)), pseudo conflict-backjumping, and branch and bound with tree decomposition (BTD). finally, it includes a solution counting method for CSP based on tree decomposition (#BTD).
A Stronger Consistency for Soft Global Constraints in Weighted Constraint Satisfaction Jimmy Lee, K. L. Leung Proc. of AAAI-10, Atlanta, Georgia, USA http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/download/1797/1939 Towards Efficient Consistency Enforcement for Global Constraints in Weighted Constraint Satisfaction Jimmy H. M. Lee, Ka Lun Leung Proc. of IJCAI'09. Pasadena (CA). USA, 2009 http://www.aaai.org/ocs/index.php/IJCAI/IJCAI-09/paper/download/641/709 Exploiting problem structure for solution counting A. Favier, S. de Givry, and P. Jégou Proc. of CP-09, Lisbon, Portugal, 2009 http://www.inra.fr/mia/T/degivry/Favier09a.pdf Bounds Arc Consistency for Weighted CSPs M. Zytnicki, C. Gaspin, S. de Givry, and T. Schiex Journal of Artificial Intelligence Research, 35:593-621, 2009 http://www.inra.fr/mia/T/degivry/Zytnicki09a.pdf 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
./toulbar2 version : 0.9.3.0, copyright (c) INRA 2010
Command line is: toulbar2_0_9_3/toulbar2 problem_filename [options]
Available problem formats (specified by the filename extension) are:
*.wcsp : Weighted CSP format (see SoftCSP web site) *.xml : CSP and weighted CSP in XML format XCSP 2.1 *.uai : Bayesian network and Markov Random Field format (see UAI'08 evaluation workshop) followed by an optional evidence filename (perform MPE task) *.pre : pedigree format (see doc/MendelSoft.txt for Mendelian error correction) *.pre *.map : pedigree and genetic map formats (see doc/HaplotypeHalfSib.txt for haplotype reconstruction in half-sib families) *.bep : satellite scheduling format (CHOCO benchmark) *.sol : solution/certificate for the problem
Warning! a New file extension can be enforced using --foo_ext=".myext" ex: --wcsp_ext='.test' --sol_ext='.sol2'
Available options are (use symbol ":" after an option to remove a default option):
-ub=[integer] : initial problem upperbound (default value is 1537228672809129301)
-v=[integer] : verbosity level
-s : show each solution found
-w : write last solution found in filename "sol"
-b : perform binary branching always instead of binary branching for interval domains and n-ary branching for enumerated domains (default option)
-c : perform binary branching with last conflict backjumping variable ordering heuristic (default option)
-q : weighted degree variable ordering heuristic (default option)
-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 value is 3)
-p=[integer] : preprocessing only: general variable elimination of degree less than or equal to the given value (default value is -1)
-t : preprocessing only: project ternary cost functions on binary cost functions and apply partial 3-consistency (can be very slow)
-h : preprocessing only: project n-ary cost functions on all binary (and some ternary) cost functions only if n is lower than the given value (default value is 10)
-m : preprocessing only: minimum degree (if compiled with BOOST)/user-specified re-ordering of variables (in conjunction with options "p" and "O")
-o : ensure optimal worst-case time complexity of DAC and EAC (can be costly in practice)
-k=[integer] : soft local consistency level (NC with Strong NIC for global constrains=0, (G)AC=1, D(G)AC=2, FD(G)AC=3, (weak) ED(G)AC=4) (default value is 4)
-l : limited discrepancy search
-L : randomized search with restart
-i : initial upperbound found by INCOP local search solver (filename "./misc/bin/linux/narycsp")
-z=[integer] : save problem in wcsp format in filename "problem.wcsp" (1: original instance, 2: after preprocessing)
-Z : debug mode (save problem at each node if verbosity option set!)
-x=[(,i=a)*] : assign variable of index i to value a (multiple assignments are separated by a comma and no space) (without any argument, a complete assignment read from file "sol")
-M=[integer] : preprocessing only: Min Sum Diffusion algorithm (default number of iterations is 0)
-A=[integer] : enforce VAC at each search node with a search depth less than a given value (default value is 0)
-T=[integer] : threshold cost value for VAC (default value is 1)
-P=[integer] : threshold cost value for VAC during the preprocessing phase (default value is 1)
-C=[integer] : multiply all costs by this number (default value is 1)
-S : preprocessing only: perform singleton consistency (only in conjunction with option "A")
-V : VAC-based value ordering heuristic
-B=[integer] : (0) DFBB, (1) BTD, (2) RDS-BTD, (3) RDS-BTD with path decomposition instead of tree decomposition (default value is 0)
-O=[filename] : read a variable elimination order from a file in order to build a tree decomposition
(if not specified, then use the variable order in which variables appear in the problem file)
-j=[integer] : split large clusters into a chain of smaller embedded clusters with a number of proper variables less than this number
(use options "-B=3 -j=1" for pure RDS, use value 0 for no splitting) (default value is 0)
-r=[integer] : limit on maximum cluster separator size (merge cluster with its father otherwise, use a negative value for no limit) (default value is -1)
-X=[integer] : limit on minimum number of proper variables in a cluster (merge cluster with its father otherwise, use a zero for no limit) (default value is 0)
-E : merge leaf clusters with their fathers if small local treewidth (in conjunction with option "e")
-R=[integer] : choice for a specific root cluster number
-I=[integer] : choice for solving only a particular rooted cluster subtree
-a : find all solutions (or count the number of zero-cost satisfiable solutions in conjunction with BTD)
-D : approximate satisfiable solution count with BTD
Available for Unix/linux/debian and Windows. Should compile under MacOs? X using misc/script/Makefile.
Download the latest stable source codes (version 0.9) as a gizp'd tarball from:
Lee Leung, 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