Goblin P logo GOBNILP

[Benchmarks] [Publications on the theory behind GOBNILP] [Publications using GOBNILP]

GOBNILP (Globally Optimal Bayesian Network learning using Integer Linear Programming) is a C program which learns Bayesian networks from complete discrete data or from local scores. GOBNILP uses the SCIP framework for Constraint Integer Programming. Detailed information on installing, running, licence etc can be found in the:

which is also contained in the GOBNILP distribution.

GOBNILP has been developed by James Cussens and Mark Bartlett. It was supported by MRC grant A graphical model approach to pedigree construction using constrained optimisation (G1002312) until Feb 2015. Goblin 'P' logo courtesy of Robby Higgins.

Download GOBNILP


Benchmarks for the current version

GOBNILP has been developed using a set of local score files used originally in the paper Bayesian network learning with cutting planes. Most of these local score input files are in this gzipped tar file. The local score input files alarm, mirna, phen and wdbc were kindly sent to me by Tommi Jaakkola, the others I generated myself. More recently a local score input file (developed by Mark Bartlett) for learning pedigrees has been used as part of the Pedigree Reconstruction using Integer Linear Programming project. The current release can learn directly form data (as well as from local scores files). Some of the the original datasets and the local scores generated from them are available from this directory. However, these original datasets are in a format incompatible with the current GOBNILP release. (This directory also contain some local score files where the data from which they were generated is not available.)

The 'Mildew' local score files in the gzipped tar file contain errors. The correct local scores for 'Mildew' instances can be found in this this directory. For all other instances the same (correct) local scores can be found in either place. Thanks to Peter van Beek for spotting this problem.

The following table provides a summary of benchmarking results for the current release using default parameter setttings. All times are in seconds. The GOBNILP output for each of these runs is available in this single file. Both the summary and the full output were generated using SCIP's "make test" utility. (Benchmark results for older GOBNILP versions are available here.)

Benchmarks run on a single core of the following machine: Linux pc435h 3.13.0-49-generic #83-Ubuntu SMP Fri Apr 10 20:11:33 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux. Processor was: Intel(R) Core(TM) i5 CPU 650 @ 3.20GHz

GOBNILP can run into memory problems and immediately abort on sufficiently big problems. The 'Link' learning problems mentioned later are like this and are not included in the following table. Note that GOBNILP did not solve the Diabetes_10000_1_2 or the Pigs_10000_1_2 problem which are in the table. It did however make some progress towards a solution before aborting. Consult the full output for details.

------------------+------+--- Original --+-- Presolved --+----------------+----------------+------+---------+--------+-------+----------+---------+--------
Name              | Type | Conss |  Vars | Conss |  Vars |   Dual Bound   |  Primal Bound  | Gap% |  Iters  |  Nodes |  Time | To First | To Best |       
------------------+------+-------+-------+-------+-------+----------------+----------------+------+---------+--------+-------+----------+---------+--------
Diabetes_100_1_2      CIP    4809    7386    5089    7329      -47697.4126      -47697.4126    0.0      1251        1    50.4       14.2      50.4 ok
Diabetes_1000_1_2     CIP   15555   31406   17553   31368      -268847.008      -268847.008    0.0      5193        3   367.9       23.9     366.9 ok
Diabetes_10000_1_2     --       0       0       0       0           -1e+20            1e+20   --           0        0     0.0        0.0       0.0 abort
Mildew_100_1_3        CIP     854    3988     991    3974      -6380.72748      -6380.72748    0.0       107        1     2.2        1.3       2.2 ok
Mildew_1000_1_3       CIP     156     245     143     232      -52258.8572      -52258.8572    0.0       135        3     0.7        0.0       0.7 ok
Mildew_10000_1_3      CIP     461     744     478     737      -454894.404      -454894.404    0.0       310        1     1.1        0.1       1.1 ok
Pigs_100_1_2          CIP    2907    4368    2837    4288       -41017.047       -41017.047    0.0      1156        1    22.8       17.5      22.8 ok
Pigs_1000_1_2         CIP   13848   24383   14434   24383      -340449.646      -340449.646    0.0      6276        1    65.5       24.8      65.5 ok
Pigs_10000_1_2         --       0       0       0       0           -1e+20            1e+20   --           0        0     0.0        0.0       0.0 abort
Water_100_1_3         CIP     308     679     341     676      -1500.96839      -1500.96839    0.0      1668        3     3.9        0.5       3.8 ok
Water_1000_1_3        CIP     504     889     563     889      -13262.3418      -13262.3418    0.0      3532        3     3.2        0.1       3.2 ok
Water_10000_1_3       CIP     687    1391     772    1391       -128705.65       -128705.65    0.0     12733       89     7.7        0.2       5.2 ok
alarm_100_1_3         CIP     742    1330     782    1329      -1349.22742      -1349.22742    0.0       668        1     1.5        0.2       1.5 ok
alarm_1000_1_3        CIP    1010    2523    1157    2522      -11240.3471      -11240.3471    0.0      1913        1     2.6        0.3       2.6 ok
alarm_10000_1_3       CIP    1486    7356    2123    7355      -105226.512      -105226.512    0.0     31906       91    63.0        1.0      35.4 ok
asia_100_1_99         CIP      47      65      47      64      -245.644264      -245.644264    0.0        23        3     0.0        0.0       0.0 ok
asia_1000_1_99        CIP     115     175     126     175      -2317.41151      -2317.41151    0.0        70        1     0.1        0.0       0.1 ok
asia_10000_1_99       CIP     123     237     149     237      -22466.3965      -22466.3965    0.0       495        3     1.3        0.0       0.9 ok
carpo_100_1_3         CIP    3011    6830    3285    6819      -1829.30685      -1829.30685    0.0    173497      442   278.0        2.0     225.6 ok
carpo_1000_1_3        CIP    1899    4946    2166    4939       -17718.948       -17718.948    0.0     24307       19    46.2        1.1      45.2 ok
carpo_10000_1_3       CIP    2844   18086    4700   18085      -174130.564      -174130.564    0.0     94221      131   308.7        4.5     272.0 ok
hailfinder_100_1_3    CIP     237     357     223     322      -6019.46993      -6019.46993    0.0       207        1     0.4        0.0       0.4 ok
hailfinder_1000_1_    CIP     632    1136     679    1133      -52473.2456      -52473.2456    0.0      1382        3     3.2        0.2       3.2 ok
hailfinder_10000_1    CIP    1542    4693    1860    4693      -497631.796      -497631.796    0.0     20297       46    35.4        0.6      24.5 ok
insurance_100_1_3     CIP     288     448     285     441      -1686.22588      -1686.22588    0.0       131        1     0.3        0.1       0.3 ok
insurance_1000_1_3    CIP     592    1126     625    1125      -13887.3501      -13887.3501    0.0       708        1     1.1        0.2       1.1 ok
insurance_10000_1_    CIP    1117    4316    1442    4315      -132968.577      -132968.577    0.0      5334        2     9.1        0.9       9.1 ok
kredit_1000_1_3       CIP      67     104      62      98      -16695.6695      -16695.6695    0.0        28        3     0.1        0.0       0.1 ok
kredit_1000_1_99      CIP      67     104      62      98      -16695.6695      -16695.6695    0.0        28        3     0.1        0.0       0.1 ok
alarm                 CIP    1441    6484    1738    6483       -9944.3113       -9944.3113    0.0      3644        1     6.4        0.9       6.4 ok
mirna                 CIP     845    1789     900    1789       -2653.7505       -2653.7505    0.0       978        1     1.9        0.2       1.9 ok
phen                  CIP     648    2678     731    2677       -6070.7502       -6070.7502    0.0      1855        1     4.0        0.4       4.0 ok
wdbc                  CIP    1946    7079    2462    7078       -6804.2458       -6804.2458    0.0      6024        1    16.3        0.9      16.3 ok
pedigree1             CIP    1267    1954    1267    1954      -1466.59852      -1466.59852    0.0       599        1     4.0        0.6       4.0 ok
------------------+------+-------+-------+-------+-------+----------------+----------------+------+---------+--------+-------+----------+---------+--------

------------------------------[Nodes]---------------[Time]--------------[ToFirst]-----------[ToLast]-----
  Cnt  Pass  Time  Fail  total(k)     geom.     total     geom.     total     geom.     total     geom.
---------------------------------------------------------------------------------------------------------
   34    32     0     2         0       3.0    1309.1       5.6      96.9       1.5    1176.3       5.3
 shifted geom. [  100/ 10.0]           15.2                11.6                 1.9                10.8 
---------------------------------------------------------------------------------------------------------
@02 timelimit: 0
@01 SCIP(3.1.1)cpx(12.6.0.0):default [GitHash: bade511]

The result in the above table are for learning from precomputed local scores. These local scores were computed from synthetic data generated from various BNs. The following table gives information on these BNs, the synthetic data and the local scores. Importantly it gives the time taken to compute these local scores. (GOBNILP 1.4.1 was used to compute the local scores.)

'BN' is the name of the BN from which the data was originally generated. 'p' is the number of variables in the original dataset (and thus in the optimal BN). 'n' is the number of datapoints in the data. 'palim' is the limit on the size of parent sets in any learned BN. '|PaSets|' is the number of candidate parent sets generated by GOBNILP's local scoring algorithm - this is the size of the input to the main GOBNILP learning algorithm. 'Scoring' is time in seconds to compute all the local scores.

BN p n palim |PaSets| Scoring
Diabetes 413 100 2 4441 1135
Diabetes 413 1000 2 21493 2754
Diabetes 413 10000 2 262129 5497
Link 724 100 2 7431402 411
Link 724 1000 2 2379361 1150
Link 724 10000 2 2421283 9005
Mildew 35 100 3 3520 17
Mildew 35 1000 3 161 64
Mildew 35 10000 3 463 167
Pigs 441 100 2 2692 151
Pigs 441 1000 2 15847 203
Pigs 441 10000 2 304219 2082
Water 32 100 3 482 1
Water 32 1000 3 573 1
Water 32 10000 3 961 7
alarm 37 100 3 907 1
alarm 37 1000 3 1928 3
alarm 37 10000 3 6473 16
asia 8 100 41 1
asia 8 1000 112 1
asia 8 10000 169 1
carpo 60 100 3 5068 5
carpo 60 1000 3 3827 14
carpo 60 10000 3 16391 99
hailfinder 56 100 3 244 20
hailfinder 56 1000 3 761 39
hailfinder 56 10000 3 3768 124
insurance 27 100 3 279 1
insurance 27 1000 3 774 1
insurance 27 10000 3 3652 5
kredit 18 1000 3 70 1
kredit 18 1000 70 248
alarm 37 5630
mirna 22 1279
phen 25 2296
wdbc 31 5921
pedigree1 100 1195

Publications on the theory behind GOBNILP

Publications using GOBNILP


Last modified: Fri May 29 19:07:02 BST 2015