TOULBAR2(1)

📦
version 1.2.1 · 2 versions
, in debian trixie, ubuntu noble, ubuntu resolute

💖 TOULBAR2(1) — the toulbar2 glow-up ✨

okay bestie, gather round, because we're about to talk about toulbar2 from the General Commands Manual and she is that girl. no cap, this tool exactly solves discrete optimization problems on graphical models. exactly. not approximately. not "close enough bestie". exactly. 💅

🌸 NAME 🌸

toulbar2 — exactly solves discrete optimization problems on graphical models 🦋

⭐ SYNOPSIS ⭐

toulbar2 [options] file

👑 DESCRIPTION 👑

so like. toulbar2 solves discrete optimization problems defined by a graphical model. and when I say graphical model I mean the whole squad:

  • Cost Function Networks — which is solving the Weighted Constraint Satisfaction Problem 💛
  • Markov Random Fields — which is solving Maximum A Posteriori or MAP/MRF 🌿
  • Bayesian Networks — which is solving Maximum Probability Explanation or MPE/BN 🔮
  • Quadratic Pseudo Boolean Optimization Problems — a.k.a. QPBO or MAXCUT ✂️
  • Partial Weighted Maximum Satisfiability… and honestly the list keeps going, she contains multitudes 💀

✨ OPTIONS ✨

🎀 GENERAL CONTROL 🎀

  • -a=[integer] — finds at most a given number of solutions whose cost is strictly lower than the initial upper bound, then stops. and if you don't give her an integer at all? she finds all the solutions (or counts the number of zero-cost satisfiable solutions when you pair her up with BTD). iconic behavior honestly 🫶
  • -agap=[decimal] — stops the search the moment the absolute optimality gap drops under the value you gave. tl;dr you get solutions with a guaranteed absolute approximation — approximation with receipts 💖
  • -D — approximate zero-cost solution count with BTD. like, she's estimating the count, be normal about it 🙈
  • -logz — computes the log of probability of evidence (that's the log partition function, or log(Z), or the PR task if you're fancy). ⚠️ restricted to stochastic graphical models (.uai format only), so don't try it on anything else bestie, she will simply not 🚫
  • -seed=[integer] — seeds the pseudo-random generator inside toulbar2 with a fixed non-negative integer. give her a negative argument instead and she'll seed the generator from the current time. default value is 1 🎲
  • --stdin=[format] — says "read the problem from standard input instead of a file." default format is cfn. like for example: cat example.uai | toulbar2 --stdin=uai — chef's kiss, pipes are her love language 🐍
  • -timer=[integer] — a cpu-time limit in seconds. toulbar2 stops once that much CPU time has been consumed. and listen — this is a CPU user time limit, not a wall clock time limit. they are not the same thing and she will not pretend they are ⏰

🧼 PREPROCESSING 🧼

  • -nopre — deactivates all the preprocessing options. it's equivalent to -e: -p: -t: -f: -dec: -n: -mst: -dee: -trws:. a full skincare cleanse, everything off 🧴
  • -p=[integer] — preprocessing only: activates variable elimination of variables with degree less than or equal to the value you give. default is -1, which means no elimination performed at all ✂️
  • -t=[integer] — preprocessing only: simulates restricted path consistency by adding ternary cost functions on triangles of binary cost functions, within a given maximum space limit in MB 📐
  • -f=[integer] — preprocessing only: variable elimination of functional variables (f=1) or bijective variables (f=2). default value is 1 🔁
  • -dec — preprocessing only: pairwise decomposition of cost functions with arity larger than 3 into smaller arity cost functions. default: activated 🍰 (slice it up)
  • -n=[integer] — preprocessing only: projects n-ary cost functions onto all binary cost functions if n is lower than the value given. default value is 10 🧮
  • -mst — finds a maximum spanning tree ordering for DAC 🌳
  • -M=[integer] — applies the Min Sum Diffusion algorithm. default is off, with a number of iterations of 0 💫

🎯 INITIAL UPPER BOUNDING 🎯

  • -ub=[decimal] — gives a primal bound (that's upper in minimization mode, lower otherwise) on the cost that a solution must satisfy. if the file also specifies a primal bound, then the tightest of the two wins. a tight primal bound can speed up the search, or you can pair it with -a to find all solutions of sufficient quality 💅
  • -l=[integer] — activates limited discrepancy search. use a negative value to stop the search after the given absolute number of discrepancies have been explored. discrepancy bound default is 4 🔍
  • -L=[integer] — activates randomized search (quasi-random variable ordering) with restart. maximum number of nodes default is 10000 🎰
  • -i=["string"] — uses the initial upper bound found by the INCOP local search solver. the string parameter is optional, and by default it's "0 1 3 idwa 100000 cv v 0 200 1 0 0", with this meaning: stoppinglowerbound randomseed nbiterations method nbmoves neighborhoodchoice neighborhoodchoice minnbneighbors maxnbneighbors neighborhoodchoice autotuning tracemode 🧠
  • -pils=["string"] — uses the initial upper bound found by the PILS local search solver. the string parameter is optional, and by default it's "3 0 0.333 100 500 10000 0.1 0.5 0.1 0.1", with this meaning: nbruns perturb_mode perturb_strength flatMaxIter nbEvalHC nbEvalMax strengthMin strengthMax incrFactor decrFactor 🎈
  • -x=[(,i=a)*] — assigns variable of index i to value a. multiple assignments get separated by a comma and no space, she's strict about that. without any argument, a complete assignment is read from the default file sol — or from a filename given directly as an additional input filename with a .sol extension and without -x — and it's used as an initial upper bound and as a value ordering heuristic 📝

🌳 TREE SEARCH ALGORITHMS AND TREE DECOMPOSITION SELECTION 🌳

  • -hbfs=[integer] — uses hybrid best-first search, restarting from the root after a given number of backtracks. default value is 10000 🔄
  • -open=[integer] — sets the hybrid best-first search limit on the number of stored open nodes. default value is -1, which means no limit 🚪
  • -B=[integer] — picks your algorithm: (0) DFBB, (1) BTD, (2) RDS-BTD, (3) RDS-BTD with path decomposition instead of tree decomposition. default value is 0 🎛️
  • -O=[filename] — reads a variable elimination order from a file, in order to build a tree decomposition (if BTD-like and/or variable elimination methods are used). the order is also used as a DAC ordering 📂
  • -O=[negativeinteger] — builds a tree decomposition (if BTD-like and/or variable elimination methods are used) and a compatible DAC ordering, using one of these:
    • (-1) maximum cardinality search ordering
    • (-2) minimum degree ordering
    • (-3) minimum fill-in ordering,
    • (-4) maximum spanning tree ordering (see -mst),
    • (-5) reverse Cuthill-Mckee ordering,
    • (-6) approximate minimum degree ordering.

if you don't specify one, then the order in which variables appear in the problem file is used 🗂️

  • -j=[integer] — splits 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 -svo -k=1" for pure RDS, and use value 0 for no splitting. default value is 0 🔪
  • -r=[integer] — sets a limit on the maximum cluster separator size (otherwise she merges the cluster with its father). use a negative value for no limit. default value is -1 🧲
  • -X=[integer] — sets a limit on the minimum number of proper variables in a cluster (otherwise she merges the cluster with its father). use 0 for no limit. default value is 0 📏
  • -E=[float] — merges leaf clusters with their fathers if the local treewidth is small (used together with option -e and a positive threshold value), or if the ratio of separator variables to cluster variables is above a given threshold (used together with option -vns). default value is 0 🍃
  • -R=[integer] — chooses a specific cluster number as the root cluster 👑
  • -I=[integer] — solves only a specific rooted cluster subtree. RDS-BTD only, don't get any ideas elsewhere 🙅
  • -vns — unified decomposition guided variable neighborhood search. a problem decomposition can be given as *.dec, *.cov, or *.order input files, or by using tree decomposition options such as -O 🗺️
  • -vnsini=[integer] — where the initial solution for VNS-like methods comes from: (-1) at random, (-2) min domain values, (-3) max domain values, (-4) first solution found by a complete method, or (k=0 or more) tree search with k discrepancy max. default is -4 🎲
  • -ldsmin=[integer] — minimum discrepancy for VNS-like methods. 1 by default 📉
  • -ldsmax=[integer] — maximum discrepancy for VNS-like methods. default is the number of problem variables multiplied by maximum domain size, minus 1 📈
  • -ldsinc=[integer] — discrepancy increment strategy for VNS-like methods, using (1) Add1, (2) Mult2, or (3) Luby operator. 2 by default ⚙️
  • -kmin=[integer] — minimum neighborhood size for VNS-like methods. 4 by default 🏘️
  • -kmax=[integer] — maximum neighborhood size for VNS-like methods. default is the number of problem variables 🌆
  • -kinc=[integer] — neighborhood size increment strategy for VNS-like methods, using (1) Add1, (2) Mult2, (3) Luby operator, or (4) Add1/Jump. 4 by default 🪜
  • -best=[integer] — stop VNS-like methods if a better solution is found. default value is 0 🏆

🔥 NODE PROCESSING & BOUNDING OPTIONS 🔥

  • -e=[integer] — performs "on the fly" variable elimination of variables with small degree (less than or equal to a specified value). default is 3, which creates a maximum of ternary cost functions 💥
  • -k=[integer] — sets the soft local consistency level enforced at preprocessing and at each node during search:
    • 0: Node Consistency with Strong Node Inverse Consistency for global cost functions,
    • 1: Generalized Arc Consistency
    • 2: Directed Generalized Arc Consistency
    • 3: Full Directed Generalized Arc Consistency
    • 4: (weak) Existential Directed Generalized Arc Consistency

default value is 4 🧚

  • -A=[integer] — enforces Virtual Arc Consistency at each search node with a search depth less than the value given. default value is 0, which enforces VAC only at the root node 🌱
  • -T=[decimal] — threshold cost value for VAC. default value is 1 🎚️
  • -P=[decimal] — threshold cost value for VAC during the preprocessing phase. default value is 1 🎚️
  • -C=[float] — multiplies all costs internally by this number when loading the problem. default value is 1 ✖️
  • -S — preprocessing only: performs singleton consistency (only in conjunction with option -A) ☝️
  • -trws=[float] — preprocessing only: enforces TRW-S until a given precision is reached. default value is 0.00001 🎯
  • --trws-n-iters=[integer] — preprocessing only: enforces at most N iterations of TRW-S. default value is 1000 🔁

ok bestie we're not done yet, there's more where that came from, don't go anywhere 🌈

  • --trws-n-iters-no-change=[integer] — preprocessing only, bestie ✨ stops TRW-S when N iterations did not move the lower bound up to the given precision. Default value is 5, and -1=never (so -1 means never stop, go off king 💅).
  • --trws-n-iters-compute-ub=[integer] — again preprocessing only: computes UB every N steps in TRW-S. Default value is 100. 🎀
  • -dee=[integer] — enforces restricted dead-end elimination, or value pruning by dominance rule from EAC value (dee>=1 and dee<=3) and soft neighborhood substitutability, in preprocessing (dee=2 or dee=4) or during search (dee=3). Default value is 1. it's giving pruning, periodt ✂️
  • -o — ensures an optimal worst-case time complexity of Directed and Existential Arc Consistency (can be slower in practice, no cap, just being honest 🫶).

🌈 BRANCHING, VARIABLE & VALUE ORDERING 🌈

the glow-up section, truly 💖

  • -svo — use a static variable ordering heuristic. The variable order used will be the same order as the DAC order. ✨
  • -b — use binary branching (as a default) instead of k-ary branching. Uses binary branching for interval domains and small domains and dichotomic branching for large enumerated domains (see option -d). 🦋
  • -c — use binary branching with last conflict backjumping variable ordering heuristic. 💅
  • -q=[integer] — use weighted degree variable ordering heuristic if the number of cost functions is less than the given value (default value is 10000). 👑
  • -var=[integer] — searches by branching only on the first [given value] decision variables, assuming the remaining variables are intermediate variables that will be completely assigned by the decision variables (use a zero if all variables are decision variables). Default value is 0. 🎀
  • -m=[integer] — use a variable ordering heuristic that preferably selects variables such that the sum of the mean (m=1) or median (m=2) cost of all incident cost functions is maximum (in conjunction with weighted degree heuristic -q). Default value is 0: unused. 🌸
  • -d=[integer] — searches using dichotomic branching. The default d=1 splits domains in the middle of domain range while d=2 splits domains in the middle of the sorted domain based on unary costs. ✂️
  • -sortd — sort domains in preprocessing based on increasing unary costs (works only for binary CFN). 🍓
  • -solr — use solution-based phase saving as a value ordering heuristic (default option). 💜
  • -V — VAC-based value ordering heuristic (default option, only in conjunction with option "-A"). ⭐

✨ CONSOLE OUTPUT ✨

  • -help — show default help message that toulbar2 prints when it gets no argument. 🙈
  • -v=[integer] — set the verbosity level (default 0). 🔥
  • -Z=[integer] — debug mode (save problem at each node if verbosity option -v=num>= 1 and -Z=num>=3). 💀
  • -s=[integer] — shows each solution found during search. The solution is printed on one line. The default -s=1 gives the value (integer) of each variable successively in increasing order of definition in the model file. For -s=2, the value name is used instead, for -s=3, variable name=valuename is printed instead. 👑

🎀 FILE OUTPUT 🎀

  • -w=[filename] — writes last solution found in the specified filename (or "sol" if no parameter is given). The current directory is used as a relative path. 💾
  • -z=[filename] — saves problem in wcsp format in filename (or "problem.wcsp" if no parameter is given). Writes also the graphviz .dot file and the degree distribution of the input problem. 🌈
  • -z=[integer] — 1: saves original instance (by default), 2: saves after preprocessing (this option can be used in combination with -z=filename). ✨

🧚 PROBABILITY REPRESENTATION AND NUMERICAL CONTROL 🧚

  • -precision=[integer] — probability/real log10 precision conversion factor (a power of ten) for representing probabilities as fixed decimal point numbers. Default value is 7. 💖
  • -epsilon=[float] — approximation factor for computing the partition function (default value is 1000 representing epsilon=1/1000). 🌸
  • -qpmult=[double] — coefficient multiplier for quadratic terms when reading qpbo format (default value is 2). 💅

🦋 RANDOM PROBLEM GENERATION 🦋

  • -random=[benchprofile] — benchmark profile must be specified as follows, where n and d are respectively the number of variable and the maximum domain size of the random problem. 🎲
bin-{n}-{d}-{t1}-{p2}-{seed}
  • t1 is the tightness in percentage of random binary cost functions
  • p2 is the number of binary cost functions to include
  • the seed parameter is optional
binsub-{n}-{d}-{t1}-{p2}-{p3}-{seed}

binary random submodular cost functions

  • t1 is the tightness in percentage of random cost functions
  • p2 is the number of binary cost functions to include
  • p3 is the percentage of submodular cost functions among p2 cost functions (plus 10 permutations of two randomly-chosen values for each domain).
tern-{n}-{d}-{t1}-{p2}-{p3}-{seed}
  • p3 is the number of ternary cost functions
nary-{n}-{d}-{t1}-{p2}-{p3}...-{pn}-{seed}
  • pn is the number of n-ary cost functions
salldiff-{n}-{d}-{t1}-{p2}-{p3}...-{pn}-{seed}
  • pn is the number of salldiff global cost functions (p2 and p3 still being used for the number of random binary and ternary cost functions). salldiff can be replaced by gcc or regular keywords with three possible forms (e.g., sgcc, sgccdp, wgcc).

💜 FILE FORMATS 💜

toulbar2 can read .cfn, .wcsp, .uai, .LG, .cnf, .wcnf, .qpbo, .pre, .bep files. The files can be compressed with gzip or xz (e.g., .cfn.gz or .cfn.xz, except for pre and bep formats). See the full user documentation for a description of these file formats. 📂

quick vibe check: pre and bep do not do the compression thing, bestie, don't try it 🙈

🌟 SEE ALSO 🌟

A more complete user documentation should be available on your system, in /usr/share/doc/toulbar2/userdoc.pdf or can be otherwise downloaded from http://miat.inrae.fr/toulbar2. 📖

👑 AUTHORS 👑

See https://github.com/toulbar2/toulbar2. 🫶

and that's a wrap on TOULBAR2(1) bestie 💖 go forth and solve, you absolute main character ✨👑💅

📦 where this page comes from