c ./bin/Linux/toulbar2 version : v1.4.0-30-g109ed30c-master-tainted (1791404331), copyright (c) 2006-2024, toulbar2 team ************************* * ToulBar2 Help Message * ************************* Command line is: toulbar2 problem_filename [options] Available problem formats (specified by the filename extension) are: *.cfn : Cost Function Network format (see toulbar2 web site) *.wcsp : Weighted CSP format (see toulbar2 web site) *.wcnf : Weighted Partial Max-SAT format (see Max-SAT Evaluation) *.cnf : (Max-)SAT format *.qpbo : quadratic pseudo-Boolean optimization (unconstrained quadratic programming) format (see also option -qpmult) *.opb : pseudo-Boolean optimization format *.wbo : Weighted Boolean Optimization format *.lp : integer linear programming format *.uai : Bayesian network and Markov Random Field format (see UAI'08 Evaluation) followed by an optional evidence filename (performs MPE task, see -logz for PR task, and write its solution in file .MPE or .PR using the same directory as toulbar2) *.LG : Bayesian network and Markov Random Field format using logarithms instead of probabilities *.pre : pedigree format (see misc/doc/MendelSoft.txt for Mendelian error correction) *.pre *.map : pedigree and genetic map formats (see misc/doc/HaplotypeHalfSib.txt for haplotype reconstruction in half-sib families) *.bep : satellite scheduling format (CHOCO benchmark) *.order : variable elimination order *.cov : tree decomposition given by a list of clusters in topological order of a rooted forest, each line contains a cluster number, then a cluster parent number with -1 for the root(s) cluster(s), followed by a list of variable indexes *.dec : a list of overlapping clusters without the running intersection property used by VNS-like methods, each line contains a list of variable indexes *.sol : initial solution for the problem (given as initial upperbound plus one and as default value heuristic, or only as initial upperbound if option -x: is added) Note: cfn, cnf, lp, LG, qpbo, opb, uai, wcnf, wcsp, wbo formats can be read in gzip'd or bzip2 or xz compressed format, e.g., toulbar2 problem.cfn.xz Warning! File formats are recognized by filename extensions. To change the default file format extension, use option --old_ext=".new" Examples: --cfn_ext='.json' --wcspgz_ext='.wgz' --sol_ext='.sol2' Available options are (use symbol ":" after an option to remove a default option): -help : shows this help message -ub=[decimal] : initial problem upperbound (default value is 512409557603043100) -agap=[decimal] : stops search if the absolute optimality gap reduces below the given value (provides guaranteed approximation) (default value is 0) -rgap=[double] : stops search if the relative optimality gap reduces below the given value (provides guaranteed approximation) (default value is 0) -v=[integer] : verbosity level -s=[integer] : shows each solution found. 1 prints value numbers, 2 prints value names, 3 prints also variable names (default 1) -w=[filename] : writes last/all solutions in filename (or "sol" if no parameter is given) -w=[integer] : 1 writes value numbers, 2 writes value names, 3 writes also variable names (default 1) -precision=[integer] defines the number of digits that should be representable on probabilities or energies in uai/pre or costs in cfn/lp/opb/qpbo/wbo files resp. (default value is 7 except for cfn) -qpmult=[double] defines coefficient multiplier for quadratic terms (default value is 2) -card : when reading opb or lp format, decomposes cardinality equality constraints into a network of binary and ternary constraints (default value is 0) -timer=[integer] : CPU time limit in seconds -bt=[integer] : limit on the number of backtracks (9223372036854775807 by default) -seed=[integer] : random seed non-negative value or use current time if a negative value is given (default value is 1) -sigma=[real] : standard deviation of zero-centered gaussian noise added to energy values in UAI format file (default value is 0) --stdin=[format] : read file from pipe ; e.g., cat example.wcsp | toulbar2 --stdin=wcsp -var=[integer] : searches by branching only on the first -the given value- decision variables, assuming the remaining variables are intermediate variables completely assigned by the decision variables (use a zero if all variables are decision variables) (default value is 0) -b : searches using binary branching always instead of binary branching for interval domains and n-ary branching for enumerated domains (default option) -svo : searches using a static variable ordering heuristic (same order as DAC) -c : searches using binary branching with last conflict backjumping variable ordering heuristic (default option) -q=[integer] : weighted degree variable ordering heuristic if the number of cost functions is less than the given value (default value is 1000000) -m=[integer] : variable ordering heuristic based on mean (m=1) or median (m=2) costs (in conjunction with weighted degree heuristic -q) (default value is 0) -d=[integer] : searches using dichotomic branching (d=1 splitting in the middle of domain range, d=2 splitting in the middle of sorted unary costs) instead of binary branching when current domain size is strictly greater than 10 (default value is 1) -sortd : sorts domains based on increasing unary costs (warning! works only for binary WCSPs) -sortc : sorts constraints based on lexicographic ordering (1), decreasing DAC ordering (2), decreasing constraint tightness (3), DAC then tightness (4), tightness then DAC (5), randomly (6), DAC with special knapsack order (7), increasing arity (8), increasing arity then DAC (9), decreasing DAC then increasing arity (10), or the opposite order if using a negative value (default value is 10) -solr : solution-based phase saving (default option) -bisupport=[float] : in bi-objective optimization with the second objective encapsulated by a bounding constraint, the value heuristic chooses between both EAC supports of first (main) and second objectives by minimum weighted regret (if parameter is non-negative, it is used as the weight for the second objective) or always chooses the EAC support of the first objective (if parameter is zero) or always chooses the second objective (if parameter is negative, -1: for choosing EAC from the lower bound constraint, -2: from the upper bound constraint, -3: to favor the smallest gap, -4: to favor the largest gap) (default value is 0) -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=[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) -hve=[integer] : hidden variable encoding with a given limit to the maximum domain size of hidden variables (see also option -n) (default value is 0) a negative size limit means restoring the original encoding after preprocessing while keeping the improved dual bound. -pwc=[integer] : pairwise consistency by hidden variable encoding plus intersection constraints, each one bounded by a given maximum space limit (in MB) a negative size limit means restoring the original encoding after preprocessing while keeping the improved dual bound. (see also options -minqual, -hve to limit the domain size of hidden variables, and -n to limit the maximum arity of dualized n-ary cost functions). -minqual : finds a minimal intersection constraint graph to achieve pairwise consistency (combine with option -pwc) (default option) -f=[integer] : preprocessing only: variable elimination of functional (f=1, or f=3 before and after PWC) (resp. bijective (f=2)) variables (default value is 1) -dec : preprocessing only: pairwise decomposition of cost functions with arity >=3 into smaller arity cost functions (default option) -n=[integer] : preprocessing only: projects n-ary cost functions defined in extension to the global lower bound if n is nonzero (only when reading wcsp/cfn/uai format) and to all scope-included binary cost functions if n is lower than the given value (default value is 10) (see also option -hve and -pwc) -mst : maximum spanning tree DAC ordering -amo=[integer] : automatically detect at-most-one constraints and add them to existing knapsack constraints (positive value) and/or directly in the cost function network up to a given absolute number (non-zero value except -1) -nopre : removes all preprocessing options (equivalent to -e: -p: -t: -f: -dec: -n: -mst: -dee: -trws: -hve: -pwc:) -o : ensures optimal worst-case time complexity of DAC and EAC (can be slower in practice) -k=[integer] : soft local consistency level (NC with Strong NIC for global cost functions=0, (G)AC=1, D(G)AC=2, FD(G)AC=3, (weak) ED(G)AC=4) (default value is 4) -dee=[integer] : restricted dead-end elimination (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) -kpdp=[integer] : solves knapsack constraints using dynamic programming (-2: never, -1: only in preprocessing, 0: at every search node, >0: after a given number of nodes) (default value is -2) -l=[integer] : limited discrepancy search, use a negative value to stop the search after the given absolute number of discrepancies has been explored (discrepancy bound = 4 by default) -L=[integer] : randomized (quasi-random variable ordering) search with restart (maximum number of nodes/VNS restarts = 10000 by default) -ai=[integer] : AI-generated heuristics (only for Max-2SAT) -i=["string"] : initial upperbound found by INCOP local search solver. string parameter is optional, using "0 1 3 idwa 100000 cv v 0 200 1 0 0" by default with the following meaning: stoppinglowerbound randomseed nbiterations method nbmoves neighborhoodchoice neighborhoodchoice2 minnbneighbors maxnbneighbors neighborhoodchoice3 autotuning tracemode -pils=["string"] : initial upperbound found by PILS local search solver. string parameter is optional, using "3 0 0.333 100 500 10000 0.1 0.5 0.1 0.1" by default with the following meaning: nbruns perturb_mode perturb_strength flatMaxIter nbEvalHC nbEvalMax strengthMin strengthMax incrFactor decrFactor -lrbcd=["string"] : initial upperbound found by LR-BCD local search solver. string parameter is optional, using "5 -2 3" by default with the following meaning: maxiter rank nbroundings (a negative rank means dividing the theoretical rank by the given absolute value) -vns : unified decomposition guided variable neighborhood search (a problem decomposition can be given as *.dec, *.cov, or *.order input files or using tree decomposition options such as -O) by default DGVNS explores its neighborhoods using restricted LDS, use options -l: -bt to rather use DFS with a fixed backtrack limit. and add a fixed neighborhood size repeated a given maximum number of times to perform Large Neighborhood Search, e.g. -vns -vnsini=-1 -l: -bt=1000 -kmin=50 -kmax=50 -L=10000 -vnsini=[integer] : initial solution for VNS-like methods found (-1) at random, (-2) min domain values, (-3) max domain values, (-4) first solution found by a complete method, (k=0 or more) tree search with k discrepancy max (-4 by default) -ldsmin=[integer] : minimum discrepancy for VNS-like methods (1 by default) -ldsmax=[integer] : maximum discrepancy for VNS-like methods (number of problem variables multiplied by maximum domain size -1 by default) -ldsinc=[integer] : discrepancy increment strategy for VNS-like methods using (1) Add1, (2) Mult2, (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 (number of problem variables by default) -kinc=[integer] : neighborhood size increment strategy for VNS-like methods using (1) Add1, (2) Mult2, (3) Luby operator (4) Add1/Jump (4 by default) -best=[decimal] : stop DFBB or VNS-like methods if a better or equal solution is found (default value is 0) -z=[filename] : saves problem in wcsp (by default) or cfn format (see below) in filename (or "problem.wcsp/.cfn" if no parameter is given) writes also the graphviz dot file and the degree distribution of the input problem (wcsp format only and non-negative verbosity) -z=[integer] : 1 or 3: saves original instance in 1-wcsp or 3-cfn format (1 by default), 2 or 4: saves after preprocessing in 2-wcsp or 4-cfn format, -2 or -4: saves after preprocessing using initial domains (this option can be combined with the previous one giving a filename) -Z=[integer] : debug mode (save problem at each node if verbosity option -v=num >= 1 and -Z=num >=3) -opt filename.sol : checks a given optimal solution (given as input filename with ".sol" extension) is never pruned by propagation (works only if compiled with debug) -x=[(,i[=#<>]a)*] : performs an elementary operation ('=':assign, '#':remove, '<':decrease, '>':increase) with value a on variable of index i (multiple operations are separated by a comma and no space) (without any argument, a complete assignment -- used as initial upper bound and as value heuristic -- read from default file "sol" taken as a certificate or given as input filename with ".sol" extension) -M=[integer] : preprocessing only: Min Sum Diffusion algorithm (default number of iterations is 0) -A=[integer] : enforces VAC at each search node with a search depth less than the absolute value of a given value, if negative value then VAC is not performed inside depth-first search of hybrid best-first search (default value is 0) -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=[float] : preprocessing only: performs restricted singleton consistency on at-most a given number of variables (all variables if no integer value is given, change stopping accuracy if floating-point value is given in [0,1[) -glb=[integer] : preprocessing only: in conjunction with option -S, performs singleton node consistency using Gilmore-Lawler lower bound before (-glb=2) or instead of (-glb=1) EAC-like greedy heuristic (default value is 0) -V=[integer] : VAC-based and Knapsack value (and variable) ordering heuristics (1:VAC value heuristic, 2:Knapsack value heuristic, 4: Knapsack fractional variable heuristic, or any combination of these options) (default value is 1) -vacint : VAC-integrality/Full-EAC variable ordering heuristic -vaclin : VAC applied on linear constraints (in conjunction with option "-A") (default option) -vacthr : automatic threshold cost value selection for VAC during search -rasps=[integer] : VAC-based upper bound probing heuristic (0: disable, >0: max. nb. of backtracks) (default value is 0) -raspslds=[integer] : VAC-based upper bound probing heuristic using LDS instead of DFS (0: DFS, >0: max. discrepancy) (default value is 0) -raspsdeg=[integer] : automatic threshold cost value selection for probing heuristic (default value is 10°) -raspsini : reset weighted degree variable ordering heuristic after doing upper bound probing -camb=[integer] : reduced costs filtering level for alldifferent and gcc constraints -trws=[float] : enforces TRW-S in preprocessing until a given precision is reached (default value is -1) --trws-order : replaces DAC order by Kolmogorov's TRW-S order --trws-n-iters=[integer] : enforces at most N iterations of TRW-S (default value is 1000) --trws-n-iters-no-change=[integer] : stops TRW-S when N iterations did not change the lower bound up to the given precision (default value is 5, -1=never) --trws-n-iters-compute-ub=[integer] : computes UB every N steps in TRW-S (default value is 100) -B=[integer] : (0) no tree decomposition, (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 or directly a valid tree decomposition (given by a list of clusters in topological order of a rooted forest, each line contains a cluster number, followed by a cluster parent number with -1 for the root(s) cluster(s), followed by a list of variable indexes) from a file used for BTD-like and variable elimination methods, and also DAC ordering -O=[negative integer] : build a tree decomposition (if BTD-like and/or variable elimination methods are used) and also a compatible DAC ordering using (-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, (-7) default file ordering (the same if this option is missing, i.e. use the variable order in which variables appear in the problem file) (-8) lexicographic ordering of variable names. (-9) topological ordering of variables for Bayesian networks only. -root=[integer] : root cluster heuristic (0:largest, 1:max. size/(height-size), 2:min. size/(height-size), 3:min. height) (default value is 0) -minheight : minimizes cluster tree height when searching for the root cluster -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, 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=[float] : merges leaf clusters with their fathers if small local treewidth (in conjunction with option "-e" and positive threshold value) or ratio of number of separator variables by number of cluster variables above a given threshold (in conjunction with option "-vns") (default value is 0) -F=[integer] : merges clusters automatically to give more freedom to variable ordering heuristic in BTD-HBFS (-1: no merging, positive value: maximum iteration value for trying to solve the same subtree given its separator assignment before considering it as unmerged) (default value is -1) -R=[integer] : chooses a specific root cluster number -I=[integer] : chooses a particular rooted cluster subtree for solving (with RDS-BTD only) -a=[integer] : finds at most a given number of solutions with a cost strictly lower than the initial upper bound and stops, or if no integer is given, finds all solutions (or counts the number of zero-cost satisfiable solutions in conjunction with BTD) -div=[integer] : minimum Hamming distance between diverse solutions (use in conjunction with -a=integer with a limit of 1000 solutions) (default value is 0) -divm=[integer] : diversity encoding method: 0:Dual 1:Hidden 2:Ternary 3:Knapsack (default value is 0) -mdd=[integer] : maximum relaxed MDD width for diverse solution global constraint (default value is 0) -mddh=[integer] : MDD relaxation heuristic: 0: random, 1: high div, 2: small div, 3: high unary costs (default value is 0) -D : approximate satisfiable solution counting with BTD -bilevel : bilevel optimization (it requires two input problems in cfn format) -logz : computes log of probability of evidence (i.e. log partition function or log(Z) or PR task) for graphical models only (problem file extension .uai) -epsilon=[float] : floating-point precision (smaller than 1, default value is 1e-09) or epsilon-approximation factor (1 + epsilon) for computing the partition function (greater than 1, default value is 1) -hbfs=[integer] : hybrid best-first search, restarting from the root after a given number of backtracks (default value is 32768) -hbfsmin=[integer] : hybrid best-first search compromise between BFS and DFS minimum node redundancy alpha percentage threshold (default value is 5%) -hbfsmax=[integer] : hybrid best-first search compromise between BFS and DFS maximum node redundancy beta percentage threshold (default value is 10%) -open=[integer] : hybrid best-first search limit on the number of open nodes (default value is -1) -sopen=[integer] : number of visited open nodes before sorting the remaining open nodes (double this limit for the next sorting) (default value is 0) -eps=[integer|filename] : embarrassingly parallel search mode (output a given number of open nodes in -x format and exit, see ./misc/script/eps.sh to run them) (default value is 0) --------------------------- Alternatively one can call the random problem generator with the following options: -random=[bench profile] : bench profile must be specified as follow : 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 num of binary cost functions to include :the seed parameter is optional (and will overwrite -seed) or: 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 num 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) or: tern-{n}-{d}-{t1}-{p2}-{p3}-{seed} p3 is the num of ternary cost functions or: nary-{n}-{d}-{t1}-{p2}-{p3}...-{pn}-{seed} pn is the num of n-ary cost functions or: salldiff-{n}-{d}-{t1}-{p2}-{p3}...-{pn}-{seed} pn is the num of salldiff global cost functions (p2 and p3 still being used for the number of random binary and ternary cost functions) or: wcolor-{n}-{d}-0-{p2}-{seed} random weighted graph coloring problem :p2 is the number of edges or: vertexcover-{n}-{d}-{t1}-{p2}-{maxcost}-{seed} :t1 is the tightness (should be equal to 25) :p2 is the number of edges :maxcost each vertex has a weight randomly chosen between 0 and maxcost or: bivertexcover-{n}-{d}-{t1}-{p2}-{maxcost}-{ub2}-{seed} :t1 is the tightness (should be equal to 25) :p2 is the number of edges in the graph :maxcost each vertex has two weights, both randomly chosen between 0 and maxcost :ub2 upper bound for the bounding constraint on the second objective ---------------------------