Optimizing Sparse Boolean Rule Networks using Mixed Integer Linear Programming
Abstract
We study the problem of learning accurate and cognitively simple binary classifiers that are directly interpretable as Boolean rules. We propose mixed integer linear programming (MILP) formulations for training sparse disjunctive normal form (DNF) networks, viewed as small networks with a conjunctive hidden layer and a disjunctive output layer. Contrary to previous work that uses MILP for inductive rule learning, we start with a fixed network structure, for which we then find optimal weights. A regularized objective explicitly trades off misclassification costs against sparsity, yielding globally optimized rule sets. Our main technical contribution is an enhanced formulation that substantially reduces the number of integer decision variables and eliminates redundant constraints, while preserving exact Boolean semantics for all feasible solutions. Furthermore, we develop a combined approach based on initialization and dropout to break symmetries in the weights between rules, mitigating redundancy, and encouraging more diverse and stable rule representations. Experiments on synthetic benchmarks and UCI datasets show that the advanced formulation improves computational efficiency and achieves competitive or superior accuracy compared to established interpretable baselines, including SAT-based DNF learning and well-known rule- and tree-based learners. Overall, our approach provides a principled optimization framework for learning compact Boolean rule sets with explicit control over accuracy and sparsity trade-offs.
Related
- Learning to Solve Mixed-Integer Nonlinear Programming with Neural Networks and Sequential Quadratic Programming Refinement
- Integer linear programming based methods for computing the maximum chordal subgraph of an arbitrary graph
- Hidden Convexity via Symmetric Displacement Covers: Mixed-Integer Quadratic Programming and Integer Cubic Programming in Fixed Dimension
- Accelerated Benders decomposition for bi-objective mixed integer programming
- Physics-Informed Mixed Integer Programming Methods for Optimal Patch Antennas
BibTeX
@misc{pammer2026optimizing,
title = {{Optimizing Sparse Boolean Rule Networks using Mixed Integer Linear Programming}},
author = {Thomas Pammer and Johannes Fürnkranz and Markus Sinnl},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20170},
eprint = {2610.20170},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20170},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimizing Sparse Boolean Rule Networks using Mixed Integer Linear Programming
AU - Thomas Pammer
AU - Johannes Fürnkranz
AU - Markus Sinnl
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.20170
UR - https://arxiv.org/abs/2610.20170
AB - We study the problem of learning accurate and cognitively simple binary classifiers that are directly interpretable as Boolean rules. We propose mixed integer linear programming (MILP) formulations for training sparse disjunctive normal form (DNF) networks, viewed as small networks with a conjunctive hidden layer and a disjunctive output layer. Contrary to previous work that uses MILP for inductive rule learning, we start with a fixed network structure, for which we then find optimal weights. A regularized objective explicitly trades off misclassification costs against sparsity, yielding globally optimized rule sets. Our main technical contribution is an enhanced formulation that substantially reduces the number of integer decision variables and eliminates redundant constraints, while preserving exact Boolean semantics for all feasible solutions. Furthermore, we develop a combined approach based on initialization and dropout to break symmetries in the weights between rules, mitigating redundancy, and encouraging more diverse and stable rule representations. Experiments on synthetic benchmarks and UCI datasets show that the advanced formulation improves computational efficiency and achieves competitive or superior accuracy compared to established interpretable baselines, including SAT-based DNF learning and well-known rule- and tree-based learners. Overall, our approach provides a principled optimization framework for learning compact Boolean rule sets with explicit control over accuracy and sparsity trade-offs.
ER -