Goblin P logo GOBNILP

[Benchmarks] [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. The GOBNILP distribution provides a separate C program to generate BDeu local scores from complete discrete data. 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 is supported by MRC grant A graphical model approach to pedigree construction using constrained optimisation (G1002312). Goblin 'P' logo courtesy of Robby Higgins.

Download GOBNILP

The current version of GOBNILP does not work with the most recent version of SCIP (SCIP 3.1.0). We are working on a new release which does, but in the meantime please use SCIP 3.0.2.


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. (This directory also contain some local score files where the data from which they were generated is not available.)

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 3.0.18-x86_64 #1 SMP PREEMPT Thu Jan 26 12:54:10 GMT 2012 x86_64 Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz GenuineIntel GNU/Linux.

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       2    4441    1829    4384      -47697.4126      -47697.4126    0.0      1429        1   105.7        0.8     105.7 ok
Diabetes_1000_1_2     CIP       2   21493    6995   21455      -268847.008      -268847.008    0.0      6256        1  7407.0        3.1    7407.0 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       2    3520     292    3506      -6380.72748      -6380.72748    0.0       110        1     0.5        0.1       0.5 ok
Mildew_1000_1_3       CIP       2     161      77     148      -52258.8572      -52258.8572    0.0       135        1     0.2        0.0       0.2 ok
Mildew_10000_1_3      CIP       2     463     182     456      -454894.404      -454894.404    0.0       402        1     0.6        0.0       0.6 ok
Pigs_100_1_2          CIP       2    2692    1257    2612       -41017.047       -41017.047    0.0      1123        1     3.1        0.5       3.1 ok
Pigs_1000_1_2         CIP       2   15847    4581   15847      -340449.646      -340449.646    0.0      7797        1    33.6        2.1      33.6 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       2     482     188     479      -1500.96839      -1500.96839    0.0      1879        1     6.4        0.0       6.4 ok
Water_1000_1_3        CIP       2     573     250     573      -13262.3418      -13262.3418    0.0      3661        1     6.0        0.0       6.0 ok
Water_10000_1_3       CIP       2     961     326     961       -128705.65       -128705.65    0.0      5506        1     6.5        0.0       6.5 ok
alarm_100_1_3         CIP       2     907     211     906      -1349.22742      -1349.22742    0.0       603        1     0.7        0.0       0.7 ok
alarm_1000_1_3        CIP       2    1928     390    1927      -11240.3471      -11240.3471    0.0      2093        1     4.0        0.1       4.0 ok
alarm_10000_1_3       CIP       2    6473     942    6472      -105226.512      -105226.512    0.0     58200      685    71.5        0.2      24.7 ok
asia_100_1_99         CIP       2      41      22      40      -245.644264      -245.644264    0.0        21        1     0.1        0.0       0.1 ok
asia_1000_1_99        CIP       2     112      39     112      -2317.41151      -2317.41151    0.0        90        1     0.1        0.0       0.1 ok
asia_10000_1_99       CIP       2     169      58     169      -22466.3965      -22466.3965    0.0       187        1     0.2        0.0       0.2 ok
carpo_100_1_3         CIP       2    5068     871    5068      -1829.30685      -1829.30685    0.0    112967      527   238.8        0.2     226.3 ok
carpo_1000_1_3        CIP       2    3827     676    3826       -17718.948       -17718.948    0.0     17773       14    75.6        0.1      75.5 ok
carpo_10000_1_3       CIP       2   16391    2390   16390      -174130.564      -174130.564    0.0    174797     1431   362.4        1.0     195.4 ok
hailfinder_100_1_3    CIP       2     244      97     217      -6019.46993      -6019.46993    0.0       208        1     0.1        0.0       0.1 ok
hailfinder_1000_1_    CIP       2     761     266     758      -52473.2456      -52473.2456    0.0      1318        1     7.9        0.0       7.9 ok
hailfinder_10000_1    CIP       2    3768     690    3768      -497631.796      -497631.796    0.0      9835        9    32.8        0.1      32.8 ok
insurance_100_1_3     CIP       2     279     107     277      -1686.22588      -1686.22588    0.0       127        1     0.2        0.0       0.2 ok
insurance_1000_1_3    CIP       2     774     200     773      -13887.3501      -13887.3501    0.0       724        1     1.1        0.0       1.1 ok
insurance_10000_1_    CIP       2    3652     576    3652      -132968.577      -132968.577    0.0      4193        1     7.4        0.1       7.4 ok
kredit_1000_1_3       CIP       2      70      37      64      -16695.6695      -16695.6695    0.0        32        1     0.1        0.0       0.1 ok
kredit_1000_1_99      CIP       2      70      37      64      -16695.6695      -16695.6695    0.0        32        1     0.1        0.0       0.1 ok
alarm                 CIP       2    5630     607    5629       -9944.3113       -9944.3113    0.0      3066        1     4.7        0.1       4.7 ok
mirna                 CIP       2    1279     278    1279       -2653.7505       -2653.7505    0.0      1624        1     4.0        0.0       4.0 ok
phen                  CIP       2    2296     234    2295       -6070.7502       -6070.7502    0.0      2120        1     7.0        0.1       7.0 ok
wdbc                  CIP       2    5921     938    5920       -6804.2458       -6804.2458    0.0      7196        1    28.2        0.2      28.2 ok
pedigree1             CIP       2    1195     456    1195      -1466.59852      -1466.59852    0.0       683        1    13.1        0.1      13.1 ok
------------------+------+-------+-------+-------+-------+----------------+----------------+------+---------+--------+-------+----------+---------+--------

------------------------------[Nodes]---------------[Time]--------------[ToFirst]-----------[ToLast]-----
  Cnt  Pass  Time  Fail  total(k)     geom.     total     geom.     total     geom.     total     geom.
---------------------------------------------------------------------------------------------------------
   34    32     0     2         2       2.1    8429.8       6.5       9.1       1.1    8203.5       6.2
 shifted geom. [  100/ 10.0]           23.3                14.2                 0.3                13.2 
---------------------------------------------------------------------------------------------------------
@02 timelimit: 0
@01 SCIP(3.0.1)cpx(12.5.0.0):default [GitHash: 9ee94b7]

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 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 using GOBNILP


Last modified: Mon Sep 8 16:58:28 BST 2014