• aolibMPE
• Demo

aolibMPE step-by-step instructions

In the following we provide step-by-step instructions on how to use the aolibMPE algorithm on an example problem instance. This example is based on Windows, but the steps for Linux are almost the same.

Downloading and running the algorithm

1. Download the archive with the executable from the algorithm's page. Since we assume a Windows operating system here, we need this file.

2. Unpack the archive contents (the binary and a sample parameter file) into a directory of your choice, say C:\aolib\.

3. Obtain an Ergo file of a MPE problem instance, for instance from our local Repository. For this example we pick 90-24-1e20 from the deterministic grid problem set. This problem comes with evidence, too, so we'll get the respective evidence file as well.

4. The problem instance and evidence file come in gzip'ed form, so unpack them to the same directory as the algorithm executable; in our case C:\aolib\.¹

5. Open a command line (In Windows: Choose "Run" in the start menu and enter cmd) and navigate to the directory where we put the files by entering cd C:\aolib\.

6. Run the algorithm by specifying the problem file, the evidence file, the parameter file and the output file, as described on the algorithm's page. We'll use the parameter file that comes with the program file. If we wish to have the result output into the file 90-24-1e20.out, the command line call in our case will be (all on one line):

   aolibMPE
       90-24-1e20.erg
       90-24-1e20.erg.evid
       paramsMPE.txt
       90-24-1e20.out

   Note that if you want to disregard the evidence (or have a problem without evidence present), just leave out the second argument pointing to the evidence file.

Algorithm output

The algorithm will run and, depending on the speed of your computer, the result should be returned shortly afterwards. The output should look somewhat like this:

BAYES: number of tuples:        4196
BAYES: number of nogoods:       1892
BAYES: degree of determinism:   45.0906 %

PP: forced connected:           no
PP: number of variables:        556
PP: number of functions:        576
PP: domain size bound:          2
PP: constraint arity:           3
PP: channel noise:              0.2200
PP: induced width:              33
PP: pseudo-tree depth:          111
PP: number of nodes in graph:   556
PP: number of edges in graph:   1522
PP: graph density:              0.9865 %
PP: preprocessing time:         0.4500 seconds
PP: pseudo-tree time:           0.0600 seconds

AOBB started ...
   time limit:  -1
   i-bound:     20
   c-bound:     1000
   cache sch:   classic
   cache impl:  hash
   # cached:    350
   heuristic:   SMBE
   ordering:    SVO
   BCP:         false
    -time        1.0, nodes 11238, open 37, closed 79, cost 0
    -time        2.0, nodes 21778, open 36, closed 81, cost 0
    -time        3.0, nodes 32324, open 33, closed 73, cost 0
    -time        4.0, nodes 42730, open 37, closed 83, cost 0
    -time        5.0, nodes 53391, open 37, closed 83, cost 0
    -time        6.0, nodes 63905, open 33, closed 71, cost 0
    -time        7.0, nodes 74423, open 42, closed 95, cost 0
    -time        8.0, nodes 84821, open 43, closed 101, cost 0
    -time        9.0, nodes 95212, open 45, closed 101, cost 0
    -time       10.0, nodes 105349, open 44, closed 99, cost 0
    -time       11.0, nodes 115998, open 44, closed 101, cost 0
    -time       12.0, nodes 126412, open 50, closed 107, cost 0
    -time       13.0, nodes 136643, open 34, closed 77, cost 0
    -time       14.0, nodes 146896, open 40, closed 93, cost 0
    -time       15.0, nodes 157149, open 38, closed 93, cost 0
    -time       16.0, nodes 167385, open 35, closed 71, cost 0
    -time       17.0, nodes 177751, open 50, closed 107, cost 0
    -time       18.0, nodes 187862, open 28, closed 65, cost 0
    -time       19.0, nodes 198466, open 36, closed 79, cost 0
    -time       20.0, nodes 208946, open 33, closed 71, cost 0
    -time       21.0, nodes 219301, open 43, closed 97, cost 0
    -time       22.0, nodes 229347, open 40, closed 93, cost 0
    -time       23.0, nodes 239712, open 32, closed 74, cost 0
    -time       24.0, nodes 250423, open 43, closed 99, cost 0
    -time       25.0, nodes 261159, open 48, closed 104, cost 0
    -time       26.0, nodes 271925, open 34, closed 71, cost 0
    -time       27.0, nodes 282586, open 33, closed 75, cost 0
    -time       28.0, nodes 293423, open 42, closed 99, cost 0
    -time       29.0, nodes 304211, open 45, closed 101, cost 0
    -time       30.0, nodes 314950, open 45, closed 99, cost 0
    -time       31.0, nodes 325246, open 46, closed 103, cost 0
    -time       32.0, nodes 335432, open 47, closed 103, cost 0
    -time       33.0, nodes 346171, open 40, closed 93, cost 0
    -time       34.0, nodes 357080, open 37, closed 80, cost 0
    -time       35.0, nodes 368047, open 51, closed 109, cost 0
    -time       36.0, nodes 378878, open 44, closed 101, cost 0
    -time       37.0, nodes 389163, open 37, closed 83, cost 0
    -time       38.0, nodes 399407, open 43, closed 95, cost 0
    -time       39.0, nodes 410606, open 27, closed 65, cost 9.98181e-09
   out of time: no
   optimal solution cost:       9.98181e-09 (-8.00079)
   CPU time (preproc):       32.4800
   CPU time (search):        39.1700
   CPU time (total):         71.6500
   number of nodes:             412291
   memory usage:                0.0368 MB
   cache usage:                 0.0042 %
END.

In addition to this diagnostic output, the log probability of the most probable explanation has been written to the file 90-24-1e20.out. aolibMPE also outputs a short summary of its computation to a file with a name starting in summary_<problem name>, which you should feel free to look at.