Provided by: toulbar2_1.2.1+dfsg-0.1_amd64 bug

NAME

       toulbar2 - exactly solves discrete optimization problems on graphical models

SYNOPSIS

       toulbar2 [options] file

DESCRIPTION

       toulbar2 solves discrete optimization problems defined by a graphical model including Cost
       Function Networks (solving the Weighted Constraint Satisfaction  Problem),  Markov  Random
       Fields  (solving  Maximum  A  Posteriori  or  MAP/MRF), Bayesian Networks (solving Maximum
       Probability Explanation or MPE/BN), Quadratic Pseudo Boolean Optimization  Problems  (QPBO
       or MAXCUT), Partial Weighted Maximum Satisfiability...

OPTIONS

       GENERAL CONTROL

       -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).

       -agap=[decimal]
              Stop  search if the absolute optimality gap reduces under the given value (provides
              solutions with a guaranteed absolute approximation).

       -D     Approximate zero-cost solution count with BTD.

       -logz  Computes the log of probability of evidence (i.e. log partition function or  log(Z)
              or PR task).  Restricted to stochastic graphical models (.uai format).

       -seed=[integer]
              Initializes  the  pseudo-random  generator  used  inside toulbar2 with a fixed non-
              negative integer argument. A negative argument instead specifies that  the  pseudo-
              random generator be seeded by current time (default value is 1).

       --stdin=[format]
              Indicates that the problem should be read from the standard input instead of a file
              (default format is cfn). Eg. cat example.uai | toulbar2 --stdin=uai

       -timer=[integer]
              Gives a cpu-time limit in seconds.  Toulbar2 will stop after the  specified  amount
              of  CPU  time has been consumed.  The time limit is a CPU user time limit, not wall
              clock time limit.

       PREPROCESSING

       -nopre Deactivates all preprocessing options (equivalent to -e:  -p:  -t:  -f:  -dec:  -n:
              -mst: -dee: -trws:).

       -p=[integer]
              Preprocessing only: activates variable elimination of variables of degree less than
              or equal to the given value (default value is -1, with no elimination performed).

       -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  (f=1)  (resp.  bijective
              (f=2)) variables (default value is 1).

       -dec   Preprocessing only: pairwise decomposition of cost functions with arity larger than
              3 into smaller arity cost functions (default: activated).

       -n=[integer]
              Preprocessing only: projects n-ary cost functions on all binary cost functions if n
              is lower than the given value (default value is 10).

       -mst   Find a maximum spanning tree ordering for DAC.

       -M=[integer]
              Apply  the Min Sum Diffusion algorithm (default is off, with a number of iterations
              of 0).

       INITIAL UPPER BOUNDING

       -ub=[decimal]
              Gives a primal (upper in minimization mode, lower otherwise) bound on cost  that  a
              solution  must satisfies. If the file specifies a primal bound too, the tightest of
              the two bounds is used. A tight primal bound can accelerate search or  be  used  in
              conjunction with -a to find all solutions of sufficient quality.

       -l=[integer]
              Activate limited discrepancy search.  Use a negative value to stop search after the
              given absolute number of discrepancies have been explored (discrepancy bound = 4 by
              default).

       -L=[integer]
              Activate  randomized  (quasi-random variable ordering) search with restart (maximum
              number of nodes = 10000 by default).

       -i=["string"]
              Use initial upper bound found by INCOP local search solver.  The  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       neighborhoodchoice      minnbneighbors      maxnbneighbors
              neighborhoodchoice autotuning tracemode.

       -pils=["string"]
              Use initial upper bound found by PILS local search solver.  The 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.

       -x=[(,i=a)*]
              Assigns  variable  of  index  i to value a (multiple assignments are separated by a
              comma and no space).  Without any argument, a complete assignment, used as  initial
              upper  bound  and  as a value orderin heuristic, is read from default file "sol" or
              from a filename  given  directly  as  an  additional  input  filename  with  ".sol"
              extension and without -x.

       TREE SEARCH ALGORITHMS AND TREE DECOMPOSITION SELECTION

       -hbfs=[integer]
              Use  hybrid  best-first  search,  restarting  from the root after a given number of
              backtracks (default value is 10000).

       -open=[integer]
              Set hybrid best-first search limit on the number  of  stored  open  nodes  (default
              value is -1, no limit).

       -B=[integer]
              Use  (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 BTD-like and/or variable elimination methods are used). The order
              is also used as a DAC ordering.

       -O=[negativeinteger]
              Build a tree decomposition (if BTD-like and/or  variable  elimination  methods  are
              used) and also a compatible DAC ordering using either:

                     (-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  not  specified, 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, use value 0 for no splitting) (default value is 0).

       -r=[integer]
              Set a limit on the maximum cluster separator size (merge cluster  with  its  father
              otherwise, use a negative value for no limit, default value is -1).

       -X=[integer]
              Set  a  limit on the 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 a ratio of number of separator
              variables by number of cluster variables is above a given threshold (in conjunction
              with option "-vns") (default value is 0).

       -R=[integer]
              Choose a specific cluster number as a root cluster.

       -I=[integer]
              Solve only a specific rooted cluster subtree (with RDS-BTD only).

       VNS SEARCH

       -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).

       -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=[integer]
              Stop VNS-like methods if a better solution is found (default value is 0).

       NODE PROCESSING & BOUNDING OPTIONS

       -e=[integer]
              Perform  "on the fly" variable elimination of variable with small degree (less than
              or equal to a specified value. Default is 3, creating a  maximum  of  ternary  cost
              functions).

       -k=[integer]
              Set  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]
              Enforce  Virtual  Arc Consistency at each search node with a search depth less than
              the given value (default value is 0 which enforces VAC only at 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: enforce TRW-S until a given precision is reached (default value
              is 0.00001).

       --trws-n-iters=[integer]
              Preprocessing only: enforce at most N iterations of TRW-S (default value is 1000).

       --trws-n-iters-no-change=[integer]
              Preprocessing  only: stop TRW-S when N iterations did not change the lower bound up
              the given precision (default value is 5, -1=never).

       --trws-n-iters-compute-ub=[integer]
              Preprocessing only: computes UB every N steps in TRW-S (default value is 100).

       -dee=[integer]
              Enforce 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.

       -o     Ensures an optimal worst-case time  complexity  of  Directed  and  Existential  Arc
              Consistency (can be slower in practice).

       BRANCHING, VARIABLE & VALUE ORDERING

       -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.

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

                                                                                      TOULBAR2(1)