Provided by: toulbar2_1.0.0+dfsg3-2_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).

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

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

       -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     Merges leaf clusters with their father if small  local  treewidth  (in  conjunction
              with option "-e").

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

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

       -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     Shows each solution found during search.  The solution  is  printed  on  one  line,
              giving  the  value  (integer)  of each variable successively in increasing order of
              definition in the model file.

       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)

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

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

       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, .cfn.gz,.wcsp, .uai, .LG, .pre, .cnf, .wcnf, .bep files.  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://www.inra.fr/mia/T/toulbar2.

AUTHORS

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

                                                                                      TOULBAR2(1)