Optimizing Sparse Boolean Rule Networks using Mixed Integer Linear Programming
Authors: Thomas Pammer, Johannes Fürnkranz, Markus Sinnl
Organizations: Institute for Application-Oriented Knowledge Processing (FAW), Johannes Kepler University Linz, Austria · LIT AI Lab, Johannes Kepler University Linz, Austria · Institute of Business Analytics & Technology Transformation/JKU Business School, Johannes Kepler University Linz, Austria
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.
Figures & tables
Figure 1: Illustration of a DNF formula (a), its conversion to a weight matrix W (b), and the resulting network structure (c), consisting of an input layer X into which the k -th training example Xk is fed, a hidden layer H which is connected to the inputs with edges corresponding to the weight matrix, and a predictive node y^k . Solid lines show active, and dashed lines show inactive weights. Bold lines highlight the computation path for the first conjunctive node.
Figure 2: DNF network structure for basic and advanced constraint formulation.
Dataset
120 s
360 s
basic
advanced
aggregated
basic
advanced
aggregated
d01
96.00
96.49
98.05
99.90
100.00
100.00
d02
84.66
97.85
98.05
97.55
99.12
99.22
d03
96.49
100.00
100.00
100.00
100.00
100.00
d04
84.76
89.94
94.44
99.02
99.71
99.71
d05
88.18
91.21
94.44
94.54
98.64
98.83
Table 1: Comparing accuracies of basic and advanced MILP approaches on artificial datasets. The best accuracy per instance is marked in bold , while the best accuracy for the shorter time limit is in italic .
Dataset
Time limit
Approaches
Milp
Sat
Lord
Ripper
Cart
breast
300
95.99
94.56
94.71
94.28
93.42
car-evaluation
1200
99.36
98.67
98.20
96.70
98.03
kr-vs-kp
7200
99.66
99.50
99.50
99.37
99.44
monk-1
30
100.00
100.00
100.00
93.70
100.00
monk-2
180
100.00
98.67
87.20
73.54
97.84
Table 2: Comparing accuracies of the advanced MILP approach with aggregated constraints to existing algorithms on UCI datasets. The best accuracy per instance is marked in bold .
Ripper Initialization
Time Limit
300
600
900
1800
3600
7200
No
76.07
76.07
76.07
76.63
78.63
80.28
Yes
84.75
84.77
84.87
84.87
84.96
85.17
Table 3: Accuracies on adult dataset with and without Ripper -Initialization.
Figure 3: Accuracy on adult dataset by time limit and dropout rate.
Interpretable machine learning is essential in high-stakes domains where decision-making requires accountability, transparency, and trust. While rule-based models offer global and exact interpretability, learning rule sets that simultaneously achieve high predictive performance and low, human-understandable complexity remains challenging. To address this, we introduce TT-Sparse, a flexible neural building block that leverages differentiable truth tables as nodes to learn sparse, effective connections. A key contribution of our approach is a new soft TopK operator with straight-through estimation for learning discrete, cardinality-constrained feature selection in an end-to-end differentiable manner. Crucially, the forward pass remains sparse, enabling efficient computation and exact symbolic rule extraction. As a result, each node (and the entire model) can be transformed exactly into compact, globally interpretable DNF/CNF Boolean formulas via Quine-McCluskey minimization. Extensive empirical results across 28 datasets spanning binary, multiclass, and regression tasks show that the learned sparse rules exhibit superior predictive performance with lower complexity compared to existing state-of-the-art methods.
Hans Farrell Soegeng, Sarthak Ketanbhai Modi, Thomas Peyrin
School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore.
Traditional neural networks have an impressive classification performance, but what they learn cannot be inspected, verified or extracted. Neural Logic Networks on the other hand have an interpretable structure that enables them to learn a logical mechanism relating the inputs and outputs with AND and OR operations. We generalize these networks with NOT operations and biases that take into account unobserved data and develop a rigorous logical and probabilistic modeling in terms of concept combinations to motivate their use. We also propose a novel factorized IF-THEN rule structure for the model as well as a modified learning algorithm. Our method improves the state-of-the-art in Boolean networks discovery and is able to learn relevant, interpretable rules in tabular classification, notably on examples from the medical and industrial fields where interpretability has tangible value.
Vincent Perreault, Katsumi Inoue, Richard Labib +1
Department of Mathematics and Industrial Engineering Polytechnique Montréal · National Institute of Informatics, Tokyo
We develop a method for training neural networks on Boolean data in which the values at all nodes are strictly ±1, and the resulting models are typically equivalent to networks whose nonzero weights are also ±1. The method replaces loss minimization with a nonconvex constraint formulation. Each node implements a Boolean threshold function (BTF), and training is expressed through a divide-and-concur decomposition into two complementary constraints: one enforces local BTF consistency between inputs, weights, and output; the other imposes architectural concurrence, equating neuron outputs with downstream inputs and enforcing weight equality across training-data instantiations of the network. The reflect-reflect-relax (RRR) projection algorithm is used to reconcile these constraints. Each BTF constraint includes a lower bound on the margin. When this bound is sufficiently large, the learned representations are provably sparse and equivalent to networks composed of simple logical gates with ±1 weights. Across a range of tasks -- including multiplier-circuit discovery, binary autoencoding, logic-network inference, and cellular automata learning -- the method achieves exact solutions or strong generalization in regimes where standard gradient-based methods struggle. These results demonstrate that projection-based constraint satisfaction provides a viable and conceptually distinct foundation for learning in discrete neural systems, with implications for interpretability and efficient inference.
Veit Elser, Manish Krishan Lal
Department of Physics, Cornell · Mathematics, Independent Researcher, India