GOBNILPAlgorithm<T>

Models & Types · AiDotNet.CausalDiscovery.Specialized

GOBNILP — Globally Optimal Bayesian Network learning using Integer Linear Programming.

Inheritance: CausalDiscoveryBase<T> → GOBNILPAlgorithm<T>

For Beginners

GOBNILP guarantees finding the BEST possible graph according to the scoring criterion. Most other algorithms are heuristic (they find good but not necessarily optimal solutions). The trade-off is that GOBNILP can be slow for many variables.

How It Works

GOBNILP formulates Bayesian network structure learning as an integer linear programming (ILP) problem. It finds the globally optimal DAG by: (1) Pre-computing BIC scores for all candidate parent sets per variable, (2) Formulating a 0-1 ILP where binary variables indicate which parent set is selected for each variable, (3) Enforcing acyclicity via cluster constraints (for each subset S, at least one variable in S must have all its parents outside S), (4) Solving the ILP with a branch-and-bound search with lazy constraint generation.

Algorithm:

  • For each variable j and each candidate parent set P ⊆ V{j} with |P| ≤ maxParents,

compute BIC score: score(j, P)

  • Create binary variable y_{j,P} = 1 iff P is the parent set of j
  • Objective: maximize sum_j sum_P score(j, P) * y_{j,P}
  • Constraint: for each j, exactly one parent set is selected: sum_P y_{j,P} = 1
  • Acyclicity: for each cluster C ⊆ V with |C| ≥ 2, at least one j ∈ C has parent set

P with P ∩ C = ∅ (enforced lazily via cycle detection)

  • Solve via branch-and-bound with lazy acyclicity constraints

Reference: Cussens (2012), “Bayesian Network Learning with Cutting Planes”, UAI.

Constructors

Constructor Summary
GOBNILPAlgorithm(CausalDiscoveryOptions options)

Properties

Property Summary
CausalDiscoveryCategory Category { get; }
bool SupportsNonlinear { get; }
string Name { get; }