mbeWCSP
Approximates the minimum cost solution to a Weighted Constraint Satisfaction Problem (WCSP)
Author
Description
The library contains the implementation of the Mini-Bucket Elimination MBE(i) algorithm for WCSP.
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:
mbeWCSP <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:
- 2: the Mini-Bucket MBE(i) algorithm
ib: (integer) specifies the i-bound of MBE(i).
Download
A 32-bit Linux binary and an example parameter file will be available soon.
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] Mini-Buckets: A General Scheme For Generating Approximations In Automated Reasoning. Rina Dechter. In Fifteenth International Joint Conference of Artificial Intelligence (IJCAI97), Japan, 1997. Link