Propagation algorithm for Stochastic Constraints on Monotonic Distributions (SCMDs), as described in: Stochastic Constraint Propagation for Mining Probabilistic Networks, Anna Louise D. Latour, Behrouz Babaki, and Siegfried Nijssen, to appear at IJCAI 2019, Macao.
In this repository we provide:
- the
Scala
implementation of our SCMD propagation algorithm; - figures with results as presented in our paper, and additional results;
- some of the test files needed to reproduce our results (based on license/availability).
You need the following pieces of software for building and running the code in this repository:
- Java openjdk 11.0.3 2019-04-16
- sbt-naive-packager for building the SCMD propagator files
- Scala 2.12
- CoverSize constraint for FIM problem setting
In order to build the binaries for the SCMD propagator, go to the SCMD-propagator
subdirectory and run
$ sbt pack
For the sub-linear propagator we support the following problem settings:
- ME: maximize expected value with constraint on the cardinality of the solution (positive decisions)
- MC: maximize cardinality of the solution (positive decisions) with constraint on the maximum expected value
- FIM: Frequent Itemset Mining
and the following branching heuristics:
- top-zero (default)
- top-one
- derivative-zero
- derivative-one
- bottom-zero
- bottom-one
We also support the collection of the search trace in a trace file and toggle detailed output during the search with the -v
or --verbose
flag.
To use our SCMD propagator to solve an ME
problem setting for which the probability distribution is encoded in [OBDD_file]
, with upper bound on the cardinality of the positive decisions [constraint_threshold]
, and branching heuristic [heuristic]
, writing the trace to [trace_file]
and printing the search details to the terminal, run:
$ ./SCMD-propagator/target/pack/bin/run ME --bdd-file [OBDD_file] --max-card [constraint_threshold] --branching [heuristic] --trace-file [trace_file] -v
We have less support for the MC
problem setting:
$ ./SCMD-propagator/target/pack/bin/run MC [OBDD_file] [constraint_threshold]
For the FIM
problem setting we support the same branching heuristics, tracing and verbose functionality as for the ME
problem setting. However, because of the nature of the frequent itemset mining problem, we do not have a cardinality constraint on the positive decisions, but we do need to specify a database with transactions [db_file]
, a minimum required expected value [minexp]
and a minimum support [minsup]
, e.g.:
$ ./SCMD-propagator/target/pack/bin/run FIM --bdd-file [OBDD_file] --db-file [db_file] --min-exp [minexp] --min-sup [minsup] --branching [heuristic] --trace-file [trace_file] -v
For the linear propagator we support only the ME
problem setting, and no tracing or verbosity:
$ ./SCMD-propagator/target/pack/bin/runner-max-exp-linear --bdd-file [OBDD_File] --max-card [constraint_threshold]
Please contact us if you are looking for the following files:
- scripts for generating OBDDs from ProbLog programs;
- code for generating GAC-guaranteeing MIP encoding of Stochastic Constraint Optimisation Problems (SCOPs) and Stochastic Constraint Problems on Monotonic Distributions (SCMDs);
- benchmarking scripts.
The propagation algorithm for the Stochastic Constraint on Monotonic Distributions (SCMD) in ./SCMD-propagator/src/main/scala/ is licensed under the MIT license.
We provide ProbLog
and OBDD
files for power transmission network models in:
- ./testfiles/problog/pgr-eu,
- ./testfiles/problog/pgr-na,
- ./testfiles/obdds/big/pgr-eu,
- ./testfiles/obdds/big/pgr-na,
- ./testfiles/obdds/minimized/pgr-eu, and
- ./testfiles/obdds/minimized/pgr-na,
which are state- or country-level connected components extracted from GridKit: European and North-American extracts, available under the Open Database License (ODbL) version 1.0.
Wiegmans, B. (2016). GridKit: European and North-American extracts [Data set]. Zenodo. http://doi.org/10.5281/zenodo.47317
The code in this repository is written and maintained by
- Behrouz Babaki (@Behrouz-Babaki)
- Siegfried Nijssen (@siegfriednijssen)
- Anna Louise Latour (@latower)