Bayesian Network Structure Learning with Integer Programming: Polytopes, Facets and Complexity
Authors: James Cussens, Matti Järvisalo, Janne H. Korhonen, Mark Bartlett
JAIR 2017 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we make several theoretical contributions towards these goals: (i) we study the computational complexity of the separation problem, proving that the problem is NP-hard; (ii) we formalise and analyse the relationship between three key polytopes underlying the IP-based approach to BNSL; (iii) we study the facets of the three polytopes both from the theoretical and practical perspective, providing, via exhaustive computation, a complete enumeration of facets for low-dimensional family-variable polytopes; and, furthermore, (iv) we establish a tight connection of the BNSL problem to the acyclic subgraph problem. |
| Researcher Affiliation | Academia | James Cussens EMAIL Department of Computer Science & York Centre for Complex Systems Analysis University of York, United Kingdom Matti J arvisalo EMAIL Helsinki Institute for Information Technology HIIT Department of Computer Science University of Helsinki, Finland Janne H. Korhonen EMAIL Department of Computer Science Aalto University, Finland Mark Bartlett EMAIL Department of Computer Science University of York, United Kingdom |
| Pseudocode | No | The paper uses mathematical formulations to describe algorithms and processes, such as the sub-IP in equations (9-13), but these are presented as a system of constraints and objective function, not in a structured pseudocode or algorithm block format. |
| Open Source Code | No | The paper refers to existing systems and programs like 'gobnilp system', 'SCIP system (Achterberg, 2007)', and 'cdd computer program (Fukuda, 2016)' which the authors used or developed previously. However, it does not explicitly state that the source code for the specific methodologies or theoretical contributions described in *this paper* is being released or provide a link to such a repository. |
| Open Datasets | No | The paper discusses Bayesian network structure learning from 'given data' and mentions that the 'gobnilp' system can compute coefficients from a 'discrete dataset with no missing values'. However, the paper does not use any specific named datasets for evaluation, nor does it provide concrete access information (links, DOIs, citations to specific dataset repositories) for any dataset used in its theoretical analysis or examples. |
| Dataset Splits | No | The paper is theoretical in nature and does not conduct empirical experiments with datasets. Therefore, there is no mention of dataset splits such as training, validation, or test sets. |
| Hardware Specification | No | The paper focuses on theoretical contributions and computational complexity. It does not describe any experimental setup that would require hardware specifications, and therefore no details about GPUs, CPUs, or other computing resources are provided. |
| Software Dependencies | No | The paper mentions 'gobnilp system', 'SCIP system (Achterberg, 2007)', 'LP solver such as So Plex or CPLEX', and 'cdd computer program (Fukuda, 2016)'. While these tools are named, specific version numbers (e.g., 'CPLEX 12.4' or 'SCIP 6.0') are not provided. The years in parentheses for SCIP and cdd are part of citations rather than explicit version declarations. |
| Experiment Setup | No | The paper is primarily theoretical, focusing on mathematical properties, computational complexity, and polyhedral analysis. It does not describe any practical experiments with specific models, algorithms, or hyperparameter settings, and thus no experimental setup details are provided. |