aolibWCSP
Computes the minimum cost solution to a Weighted Constraint Satisfaction Problem (WCSP)
Author
Description
The library contains the implementations of the depth AND/OR Branch-and-Bound as well as the Best-First AND/OR search algorithms for solving WCSPs. Both algorithms exploit the independencies revealed by the underlying graphical model by traversing the context minimal AND/OR search graph associated with the input WCSP.
The effectiveness of the depth-first and best-first AND/OR search algorithms depends on the quality of the heuristic evaluation functions. We provide a general scheme for generating heuristic estimates of varying strengths, automatically from the functional specification of the problem, based on the Mini-Bucket approximation. Naturally, more accurate heuristic estimates may yield a smaller search space, however at a much higher computational cost. Therefore, the right trade-off between the computational overhead at each node and the pruning power exhibited during search may be hard to predict.
The Mini-Bucket heuristics can be
pre-compiled before search (static Mini-Bucket heuristics), or
generated dynamically, during search (dynamic Mini-Bucket heuristics).
In addition, we also provide an implementation of the AND/OR Branch-and-Bound guided by a form of local soft consistency propagation, called Existential Directional Arc Consistency (in short EDAC) an introduced in the past few years by [5]. The algorithm can also accommodate dynamic variable ordering heuristics.
Input format
The WCSP instance needs to be specified in the WCSP_file_format.
For some example problems please see our Repository.
Usage
The algorithm is invoked with three arguments:
aolibWCSP <inputFile> <parameterFile> <outputFile>
with the following meaning:
<inputFile> specifies the path to the problem specification in WCSP_file_format.
<parameterFile> specifies the path to the file containing custom parameters for the algorithm. See the example file that comes with the binary program file for syntax reference.
<outputFile> specifies the path to the file to which the cost of the best solution is written.
Detailed step-by-step instructions are available here.
Parameters
Parameters for the algorithm, which can be specified within the parameter file:
h: (string) the heuristic to use for finding a variable elimination order by which to construct the And/Or search space:
- minfill: indicates the min-fill heuristic
- hypergraph: indicates the hypergraph partitioning heuristic
a: (integer) specifies which algorithm to run. The following values can be used:
- 3: AND/OR Branch-and-Bound with static mini-bucket heuristics (i.e., AOBB+SMB(i))
- 4: AND/OR Branch-and-Bound with dynamic mini-bucket heuristics (i.e., AOBB+DMB(i))
- 7: AND/OR Branch-and-Bound with EDAC heuristics (i.e., AOEDAC)
- 9: Best-First AND/OR search with static mini-bucket heuristics (i.e., AOBF+SMB(i))
- available only for Windows
- 10: Best-First AND/OR search with dynamic mini-bucket heuristics (i.e., AOBF+DMB(i))
- available only for Windows
ib: (integer) specifies the i-bound of the guiding mini-bucket heuristic.
cb: (integer) specifies the cache bound used by AND/OR Branch-and-Bound algorithms.
l (integer) specifies the time limit in seconds. Default value is -1, which indicates no time limit.
vo: (string) specifies the variable ordering used. The following values can be used:
svo: stands for Static Variable Ordering
- applicable to algorithms: 3, 4, 7, 9, 10.
pvo: stands for Partial Variable Ordering
applicable to algorithms: 7
dvo: stands for Full Dynamic Variable Ordering
- applicable to algorithms: 7
dso1: stands for Dynamic Separator Ordering
- applicable to algorithms: 7
Download
A 32-bit Linux binary and an example parameter file are available here.
Get the 32-bit Windows binary and an example parameter file are here.
If you are interested in obtaining the source code, please contact the program author.
References
[1] Radu Marinescu and Rina Dechter. AND/OR Branch-and-Bound Search for Graphical Models. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2005. Link
[2] Radu Marinescu and Rina Dechter. Memory Intensive Branch-and-Bound Search in Graphical Models. In Proceedings of the National Conference on Artificial Intelligence (AAAI), 2006. Link
[3] Radu Marinescu and Rina Dechter. Dynamic Variable Orderings for AND/OR Branch-and-Bound Search in Graphical Models. In Proceedings of the European Conference on Artificial Intelligence (ECAI), 2006. Link
[4] Radu Marinescu and Rina Dechter. Best-First AND/OR Search for Graphical Models. In Proceedings of the National Conference on Artificial Intelligence (AAAI), 2007. Link
[5] Simon de Givry, Matthias Zytnicki, Federico Heras and Javier Larrosa. Existential Arc Consistency: Getting Closer to Full Arc Consistency in Weighted CSPs. In Proceedings of the International Joint Conference on Artificial Intelligence, 2005.