toulbar2.1 15.3 KB
Newer Older
1
2
.TH TOULBAR2 1
.SH NAME
3
toulbar2 \- exactly solves discrete optimization problems on graphical models
4
5
6
7
8
9
.SH SYNOPSIS
.B toulbar2
[options] 
.IR file
.SH DESCRIPTION
.B toulbar2
10
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...
11
.SH OPTIONS
12
13
14
.PP
GENERAL CONTROL
.TP
15
16
.BR \-a=[\fIinteger\fR]
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).
17
.TP
18
19
20
.BR \-agap=[\fIdecimal\fR]
Stop search if the absolute optimality gap reduces under the given value (provides solutions with a guaranteed absolute approximation).
.TP
21
22
23
24
25
.BR \-D 
Approximate zero-cost solution count with BTD.
.TP
.BR \-logz
Computes the log of probability of evidence (i.e. log partition function or log(Z) or PR task).
26
27
28
Restricted to stochastic graphical models (.uai format).
.TP
.BR \-seed=[\fIinteger\fR]
29
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).
30
31
32
.TP
.BR \--stdin=[\fIformat\fR]
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
33
34
35
36
37
38
39
40
41
.TP
.BR \-timer=[\fIinteger\fR]
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.
.PP
PREPROCESSING
.TP 
.BR \-nopre
42
Deactivates all preprocessing options (equivalent to \-e: \-p: \-t: \-f: \-dec: \-n: \-mst: \-dee: \-trws:). 
43
44
45
46
47
48
49
50
.TP
.BR \-p=[\fIinteger\fR]
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).
.TP
.BR \-t=[\fIinteger\fR]
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).
.TP
.BR \-f=[\fIinteger\fR]
51
Preprocessing only: variable elimination of functional (f=1) (resp. bijective (f=2)) variables (default value is 1).
52
53
.TP
.BR \-dec 
54
Preprocessing only: pairwise decomposition of cost functions with arity larger than 3 into smaller arity cost functions (default: activated).
55
56
57
58
59
60
61
62
63
64
65
66
.TP
.BR \-n=[\fIinteger\fR]
Preprocessing only: projects n\-ary cost functions on all binary cost functions if n is lower than the given value (default value is 10).
.TP
.BR \-mst 
Find a maximum spanning tree ordering for DAC.
.TP
.BR \-M=[\fIinteger\fR]
Apply the Min Sum Diffusion algorithm (default is off, with a number of iterations of 0).
.PP
INITIAL UPPER BOUNDING
.TP
67
.BR \-ub=[\fIdecimal\fR]
68
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.
69
.TP
70
71
72
73
74
.BR \-l=[\fIinteger\fR]
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).
.TP
.BR \-L=[\fIinteger\fR] 
75
Activate randomized (quasi\-random variable ordering) search with restart (maximum number of nodes = 10000 by default).
76
77
78
79
80
81
82
.TP
.BR \-i=[\fI"string"\fR] 
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: \fIstoppinglowerbound randomseed nbiterations method nbmoves neighborhoodchoice neighborhoodchoice minnbneighbors maxnbneighbors neighborhoodchoice autotuning tracemode\fR.
.TP
.BR \-x=[\fI(,i=a)*\fR] 
Assigns variable of index i to value a (multiple assignments are separated by a comma and no space).
83
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.
84
85
86
87
88
89
90
.PP
TREE SEARCH ALGORITHMS AND TREE DECOMPOSITION SELECTION
.TP
.BR \-hbfs=[\fIinteger\fR] 
Use hybrid best\-first search, restarting from the root after a given number of backtracks (default value is 10000).
.TP
.BR \-open=[\fIinteger\fR] 
91
Set hybrid best\-first search limit on the number of stored open nodes (default value is \-1, no limit).
92
93
.TP
.BR \-B=[\fIinteger\fR]
94
Use (0) DFBB, (1) BTD, (2) RDS\-BTD, (3) RDS\-BTD with path decomposition instead of tree decomposition (default value is 0).
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
.TP
.BR \-O=[\fIfilename\fR] 
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.
.TP
.BR \-O=[\fInegative integer\fR] 
Build a tree decomposition (if BTD\-like and/or variable elimination methods are used) and also a compatible DAC ordering using either:
.RS
.RS
.PP
(\-1) maximum cardinality search ordering
.PP
(\-2) minimum degree ordering
.PP
(\-3) minimum fill\-in ordering,
.PP
(\-4) maximum spanning tree ordering (see \-mst), 
.PP
(\-5) reverse Cuthill\-Mckee ordering, 
.PP
114
(\-6) approximate minimum degree ordering.
115
116
117
118
119
120
121
122
123
124
125
126
127
.RE
If not specified, then the order in which variables appear in the problem file is used.
.RE
.TP
.BR \-j=[\fIinteger\fR] 
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).
.TP
.BR \-r=[\fIinteger\fR] 
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).
.TP
.BR \-X=[\fIinteger\fR] 
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).
.TP
128
129
.BR \-E=[\fIfloat\fR] 
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).
130
131
132
133
134
135
136
.TP
.BR \-R=[\fIinteger\fR] 
Choose a specific cluster number as a root cluster.
.TP
.BR \-I=[\fIinteger\fR] 
Solve only a specific rooted cluster subtree (with RDS\-BTD only).
.PP
137
138
139
140
141
142
VNS SEARCH
.TP
.BR \-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).
.TP
.BR \-vnsini=[\fIinteger\fR]
143
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).
144
145
146
147
148
.TP
.BR \-ldsmin=[\fIinteger\fR]
Minimum discrepancy for VNS-like methods (1 by default).
.TP
.BR \-ldsmax=[\fIinteger\fR]
149
Maximum discrepancy for VNS-like methods (number of problem variables multiplied by maximum domain size -1 by default).
150
151
152
153
154
.TP
.BR \-ldsinc=[\fIinteger\fR]
Discrepancy increment strategy for VNS-like methods using (1) Add1, (2) Mult2, (3) Luby operator (2 by default).
.TP
.BR \-kmin=[\fIinteger\fR]
155
Minimum neighborhood size for VNS-like methods (4 by default).
156
157
158
159
.TP
.BR \-kmax=[\fIinteger\fR]
Maximum neighborhood size for VNS-like methods (number of problem variables by default).
.TP
160
161
.BR \-kinc=[\fIinteger\fR]
Neighborhood size increment strategy for VNS-like methods using (1) Add1, (2) Mult2, (3) Luby operator (4) Add1/Jump (4 by default).
162
.TP
163
164
.BR \-best=[\fIinteger\fR]
Stop VNS-like methods if a better solution is found (default value is 0).
165
.PP
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
NODE PROCESSING & BOUNDING OPTIONS
.TP
.BR \-e=[\fIinteger\fR] 
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).
.TP
.BR \-k=[\fIinteger\fR]
Set the soft local consistency level enforced at preprocessing and at each node during search:
.RS
.RS
.PP
0: Node Consistency with Strong Node Inverse Consistency for global cost functions,
.PP
1: Generalized Arc Consistency
.PP
2: Directed Generalized Arc Consistency
.PP
3: Full Directed Generalized Arc Consistency
.PP
4: (weak) Existential Directed Generalized Arc Consistency
.RE
Default value is 4.
.RE
.TP
.BR \-A=[\fIinteger\fR] 
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).
191
.TP
192
193
.BR \-T=[\fIdecimal\fR]
Threshold cost value for VAC (default value is 1).
194
.TP
195
196
.BR \-P=[\fIdecimal\fR]
Threshold cost value for VAC during the preprocessing phase (default value is 1).
197
.TP
198
199
.BR \-C=[\fIfloat\fR]
Multiplies all costs internally by this number when loading the problem (default value is 1).
200
201
.TP
.BR \-S
202
Preprocessing only: performs singleton consistency (only in conjunction with option "-A").
203
.TP
204
205
.BR \-trws=[\fIfloat\fR]
Preprocessing only: enforce TRW-S until a given precision is reached (default value is 0.00001).
206
.TP
207
208
.BR \--trws-n-iters=[\fIinteger\fR]
Preprocessing only: enforce at most N iterations of TRW-S (default value is 1000).
209
.TP
210
211
212
213
214
.BR \--trws-n-iters-no-change=[\fIinteger\fR]
Preprocessing only: stop TRW-S when N iterations did not change the lower bound up the given precision (default value is 5, -1=never).
.TP 
.BR \--trws-n-iters-compute-ub=[\fIinteger\fR]
Preprocessing only: computes UB every N steps in TRW-S (default value is 100).
215
.TP
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
.BR \-dee=[\fIinteger\fR]
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.
.TP
.BR \-o 
Ensures an optimal worst\-case time complexity of Directed and Existential Arc Consistency (can be slower in practice).
.PP
BRANCHING, VARIABLE & VALUE ORDERING
.TP
.BR \-svo
Use a static variable ordering heuristic.
The variable order used will be the same order as the DAC order.
.TP
.BR \-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).
.TP
.BR \-c
Use binary branching with last conflict backjumping variable ordering heuristic.
.TP
.BR \-q=[\fIinteger\fR] 
Use weighted degree variable ordering heuristic if the number of cost functions is less than the given value (default value is 10000).
.TP
.BR \-var=[\fIinteger\fR]
Searches by branching only on the first [\fIgiven value\fR] 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.
.TP
.BR \-m=[\fIinteger\fR]
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.
.TP
.BR \-d=[\fIinteger\fR]
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. 
.TP
.BR \-sortd
Sort domains in preprocessing based on increasing unary costs (works only for binary CFN).
253
.TP
254
255
256
.BR \-solr
Use solution-based phase saving as a value ordering heuristic (default option).
.TP
257
.BR \-V
258
VAC-based value ordering heuristic (default option,  only in conjunction with option "-A").
259
260
261
262
263
264
265
266
267
268
269
270
.PP
CONSOLE OUTPUT
.TP
.BR \-help
Show default help message that toulbar2 prints when it gets no argument.
.TP
.BR \-v=[\fIinteger\fR] 
Set the verbosity level (default 0).
.TP
.BR \-Z=[\fIinteger\fR] 
Debug mode (save problem at each node if verbosity option \-v=num>= 1 and \-Z=num>=3).
.TP
271
.BR \-s=[\fIinteger\fR]
272
273
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.
274
275
276
277
278
279
280
281
282
283
284
285
286
.PP
FILE OUTPUT
.TP
.BR \-w=[\fIfilename\fR]
Writes last solution found in the specified filename (or "sol" if no parameter is given).
The current directory is used as a relative path.
.TP
.BR \-z=[\fIfilename\fR]
 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.
.TP
.BR \-z=[\fIinteger\fR]
1: saves original instance (by default), 2: saves
287
  after preprocessing (this option can be used in combination with \-z=filename).
288
289
290
291
292
293
294
295
296
.PP
PROBABILITY REPRESENTATION AND NUMERICAL CONTROL
.TP
.BR \-precision=[\fIinteger\fR] 
Probability/real log10 precision conversion factor (a power of ten) for representing probabilities as fixed decimal point numbers.
Default value is 7.
.TP
.BR \-epsilon=[\fIfloat\fR] 
Approximation factor for computing the partition function (default value is 1000 representing epsilon=1/1000).
297
298
299
.TP
.BR \-qpmult=[\fIdouble\fR]
Coefficient multiplier for quadratic terms when reading qpbo format (default value is 2).
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
.PP
RANDOM PROBLEM GENERATION
.TP
.BR \-random=[\fIbench profile\fR]
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.
.RS
.RS
.PP			
bin\-{n}\-{d}\-{t1}\-{p2}\-{seed}
.RS
.PP
t1 is the tightness in percentage \% of random binary cost functions
.PP
p2 is the number of binary cost functions to include
.PP
the seed parameter is optional
.RE
.PP
binsub\-{n}\-{d}\-{t1}\-{p2}\-{p3}\-{seed} binary random \& submodular cost functions       
.RS
.PP
t1 is the tightness in percentage \% of random cost functions
.PP
p2 is the number of binary cost functions to include
.PP
p3 is the percentage \% of submodular cost functions among p2 cost functions (plus 10 permutations of two randomly\-chosen values for each domain).
.RE
tern\-{n}\-{d}\-{t1}\-{p2}\-{p3}\-{seed} 
.RS
.PP
p3 is the number of ternary cost functions
.RE
nary\-{n}\-{d}\-{t1}\-{p2}\-{p3}...\-{pn}\-{seed}
333
334
.PP
.RS
335
336
.PP
pn is the number of n\-ary cost functions
337
.RE
338
339
salldiff\-{n}\-{d}\-{t1}\-{p2}\-{p3}...\-{pn}\-{seed}  
.RS
340
.PP
341
342
343
344
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 (\fI e.g., sgcc, sgccdp, wgcc\fR).
.RE
.RE
.SH FILE FORMATS
345
toulbar2 can read .cfn, .cfn.gz, .wcsp, .uai, .LG, .cnf, .wcnf, .qpbo, .pre, .bep files. See the full user documentation for a description of these file formats.
346
.SH SEE ALSO
347
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.
348
.SH AUTHORS
349
See https://github.com/toulbar2/toulbar2