REVIEW 3 major objections 6 minor 19 references
Mathematical Programming Models for Exact and Interpretable Formulation of Neural Networks
T0 review · 3 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read Training, pruning, and architecture selection for small ReLU networks can be cast as one globally optimal mixed-integer linear program.
desk verdict The paper's central exact-encoding claim fails because constraints (1i) and (2o) force pre-activations to be nonnegative, making ReLU's zero branch unreachable and reducing the model to affine maps. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the big-M piecewise-linear encoding of a ReLU unit as $a = \max(0,z)$, implemented with a binary switch $\delta$ through the constraints $a \ge 0$, $a \ge z$, $a \le z - z_{\min}(1-\delta)$, and $a \le z_{\max}\delta$, where $z_{\min}<0<z_{\max}$ are precomputed pre-activation bounds. Around this core, the model adds binary switches $\gamma_l$ for dense layers and $\gamma_c^{(l)}$ for convolutional output channels that zero all weights, biases, and activations of a pruned unit through $M\gamma$ big-M bounds; auxiliary variables $u$ that make $u=|W|$ at optimum, giving an exact $\ell^1$ penalty; and binary selection variables $\zeta$ that implement max pooling. These objects convert nonlinear training and architecture selection into one MILP.
What would settle it
Take the stated MILP with one hidden ReLU neuron, one sample $(x,t)=(-1,-1)$, and a linear output. An exact ReLU network fits this with a negative pre-activation and zero activation, but the constraint $0 \le z \le M\gamma_1$ forbids negative $z$, so the solver cannot reach the true optimum; the returned optimal value and the sign of $z$ settle whether the encoding is exact.
Extended reading notes
Core claim
On its own terms, the paper's central claim is that the forward pass of a dense ReLU network and of a CNN—convolution with weight sharing, ReLU, max pooling, flattening, and the final affine output—admits a linear encoding with binary helpers, and that the same encoding can be extended to structural decisions. Each ReLU unit is modeled by a binary $\delta$ that picks the identity or zero branch via big-M bounds; each layer (dense) or output channel (CNN) gets a binary $\gamma$ that zeros all associated weights, biases, and activations when pruned; the $\ell^1$ penalty is linearized by auxiliary variables $u=|W|$; max pooling is modeled by binary selection variables $\zeta$. The paper's conclusion is that any feasible solution of the MILP is a completely specified network and any optimal solution minimizes the composite objective globally, so training, pruning, and architecture selection no longer need separate pipelines.
Load-bearing premise
The argument stands or falls on the big-M encoding being an exact representation of ReLU for every unit; the displayed constraints $0 \le z \le M\gamma$ force all pre-activations nonnegative, which removes the negative branch of ReLU and so the model as written cannot represent a general ReLU network.
Editorial extensions
If this is right
- Small dense networks can be trained with hidden layers pruned automatically while keeping accuracy; the paper reports 96.7–99.1% test accuracy on IRIS, WBC, and Wine, with the WBC model collapsing to one hidden layer.
- Convolutional filters can be pruned during training without a separate pruning pass; the paper reports 4 of 6 filters retained with 91% test accuracy on MNIST.
- Because the forward pass is a set of linear constraints, constraints encoding fairness, monotonicity, or logic rules can be added at training time and are satisfied by construction.
- Every feasible MILP solution is a completely specified network, so the same object used for training can be handed to a verifier without re-encoding.
- The composite objective lets the user interpolate between accuracy, weight sparsity, and architectural compactness by tuning $\alpha$, $\lambda$, and $\beta$.
Reading between the lines
- The ReLU encoding itself is not tied to the squared loss; swapping in an $\ell^1$ or hinge-style objective should preserve the same forward constraints, which would extend the framework to robust or quantile-style training.
- The stated pruning bounds $0 \le z \le M\gamma$ contradict the negative pre-activation bounds $z_{\min}<0$; a corrected model would need $z \ge z_{\min}\gamma$ (or equivalent) to keep the zero branch of ReLU reachable, so the exactness claim should be read as intended rather than as literally displayed.
- Because the binary count grows as samples times units times spatial locations, the practical ceiling is small tabular or low-resolution image problems; the paper's own MNIST configuration already exceeds 1.5 million ReLU binaries.
- A quick single-neuron test on a point requiring a negative pre-activation would show whether an implemented solver, not just the displayed equations, honors the claimed exactness.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes mixed-integer linear programming (MILP) models for training fully connected and convolutional neural networks with ReLU activations, integrating parameter learning, architecture selection, and structural sparsity regularization into a single optimization problem. The dense model is presented in Section 2 and the convolutional model in Section 3, with experiments on IRIS, Wine, WBC, and MNIST reported in Section 4. The central claims are that the formulations provide an exact encoding of ReLU network behavior and that solving them yields globally optimal solutions with respect to a composite objective that balances prediction accuracy, weight sparsity, and architectural compactness.
Significance. If correct, the proposed framework would be a useful contribution to the growing area of exact, verifiable neural network training, offering a unified way to handle small-scale training, pruning, and architecture search with formal guarantees. The paper is clearly written and the intended scope is appropriate for a methods paper. However, the correctness of the core formulation is not established: the printed constraints do not encode general ReLU networks, and the experimental results do not support the global optimality claim. As written, the central contribution is undermined, so the significance is currently not realized.
major comments (3)
- [Section 2, constraint (1i)] Constraint (1i) imposes 0 ≤ z(l)_{i,j} ≤ M γ_l for all hidden layers, which forces every hidden pre-activation to be nonnegative. In the ReLU encoding (1e)-(1h), this makes the zero branch (δ=0) feasible only when z=0 and infeasible for any z<0. The text explicitly states that z_min < 0 is a precomputed lower bound essential for the big-M encoding, so (1i) directly contradicts the stated design. A correct big-M ReLU encoding requires z(l)_{i,j} to range over an interval with a negative lower bound, e.g., z_min ≤ z ≤ Mγ and a(l)_{i,j} ≤ Mγ_l. As printed, the dense model only represents affine maps rather than general ReLU networks, invalidating the exactness claims in the abstract and Section 5.
- [Section 3, constraints (2o) and (2r)] The convolutional formulation repeats the same defect. Constraint (2o) forces 0 ≤ z(l)_{i,c,h,w} ≤ M γ(l)_c, and constraint (2r) states z(l)_{i,c,h,w} ∈ [0, M]. Consequently all convolutional pre-activations are nonnegative, and the ReLU encoding (2d)-(2g) cannot represent the zero branch for negative pre-activations. The statement in Section 3 that constraints (2d)-(2g) yield an exact piecewise-linear representation of ReLU is therefore false without a valid negative lower bound on z, so the convolutional model also fails to encode general CNN behavior.
- [Section 4, Tables 1 and 2] The reported MIP gaps of 8.6%, 4.0%, 10.2%, and 20.3% indicate that the solver did not prove optimality within the time budget. The abstract claims that the framework yields globally optimal solutions with respect to the composite objective, but these experiments provide only incumbent solutions without optimality certificates. This is a separate issue from the encoding defect, but it is another load-bearing discrepancy between the claims and the evidence.
minor comments (6)
- [Section 3, first paragraph] The term "MLIP" appears in the first paragraph and should be "MILP".
- [Section 3, constraint (2h)] The notation l ∈ L_pool is used but the set L_pool is never defined in the paper.
- [Section 4, experimental description] The sentence "The ReLU activity dropped by over 30%" is not defined or quantified against a clear baseline; please state how this metric is measured.
- [Section 2, constraint (1o)] The symmetry-breaking constraint is claimed to preserve global optimality, but the paper does not prove that every functional equivalence class contains a feasible representative satisfying the row-sum ordering.
- [Section 3, constraint (2j)] The choice of the big-M constant for the max-pooling encoding is described only as needing to be "conservative"; the paper should specify how M is computed or bounded to ensure correctness.
- [Section 4, dataset splits] For reproducibility, the exact train-test splits (including whether a subset of MNIST was used) and the number of samples per split should be reported.
Circularity Check
No significant circularity: the MILP formulation is a direct encoding of affine operations and ReLU with separately estimated bounds, not a fit renamed as a prediction.
full rationale
The paper's central claim is that the proposed MILP exactly encodes fully connected and convolutional ReLU networks, enabling joint training, pruning, and architecture selection. The derivation proceeds by introducing variables and constraints that directly represent the affine maps, ReLU switches, max-pooling, and structural pruning decisions; none of these constraints is defined in terms of the claimed outcome. The objective is a composite of squared loss, elastic net penalties, and architectural penalties, and no parameter is fitted to a subset of data and then reported as a prediction of a closely related quantity. The big-M bounds are estimated from an LP relaxation using forward passes, which is a standard bound-calculation step rather than a fitting of the target result. The paper contains no self-citations used as load-bearing evidence, and no uniqueness theorem is imported from the authors' prior work. A potential correctness concern exists: constraints (1i) and (2o) impose 0 <= z for hidden pre-activations, which may make the zero branch of ReLU unreachable and thus undermine the exactness claim as printed; however, this is a modeling or sign error in the formulation, not a circular derivation. The claimed result is not equivalent to its inputs by construction, so the appropriate circularity score is 0.
Assumptions & free parameters
free parameters (5)
- α (elastic net strength) =
0.1
- λ (L1 vs L2 balance) =
0.9
- β (structural pruning penalty) =
0.01, 0.1, or 1.0 per dataset
- Big-M bounds z_min and z_max =
estimated from LP relaxation
- Network capacity (layer widths, filter counts) =
L ≤ 3 layers of 10 neurons; CNN with 2x6 filters and dense layer of 7
assumptions (3)
- domain assumption Pre-activation bounds z_min < 0 < z_max are valid for all feasible solutions, but the model does not enforce z within these bounds.
- domain assumption Restricting hidden pre-activations to z ≥ 0 is without loss of generality for representing the target ReLU networks.
- domain assumption A solver stop at a 1% optimality gap or a two-hour timeout still yields a globally optimal network.
Cite this review
Pith. "Pith review of Mathematical Programming Models for Exact and Interpretable Formulation of Neural Networks." pith.science (2026). https://pith.science/paper/XSIZ7SBG
@misc{pith2026250414356,
author = {Pith},
title = {Pith review of: Mathematical Programming Models for Exact and Interpretable Formulation of Neural Networks},
year = {2026},
howpublished = {\url{https://pith.science/paper/XSIZ7SBG}},
note = {Machine review of arXiv:2504.14356}
}
read the original abstract
This paper presents a unified mixed-integer programming framework for training sparse and interpretable neural networks. We develop exact formulations for both fully connected and convolutional architectures by modeling nonlinearities such as ReLU activations through binary variables and encoding structural sparsity via filter- and layer-level pruning constraints. The resulting models integrate parameter learning, architecture selection, and structural regularization within a single optimization problem, yielding globally optimal solutions with respect to a composite objective that balances prediction accuracy, weight sparsity, and architectural compactness. The mixed-integer programming formulation accommodates piecewise-linear operations, including max pooling and activation gating, and permits precise enforcement of logic-based or domain-specific constraints. By incorporating considerations of interpretability, sparsity, and verifiability directly into the training process, the proposed framework bridges a range of research areas including explainable artificial intelligence, symbolic reasoning, and formal verification.
Reference graph
Works this paper leans on
-
[1]
Nature Machine Int elligence 1(5), 206–215 (2019)
Rudin, C.: Stop explaining black box machine learning models for high s takes decisions and use interpretable models instead. Nature Machine Int elligence 1(5), 206–215 (2019)
work page 2019
-
[2]
Communication s of the ACM 61(10), 36–43 (2018)
Lipton, Z.C.: The mythos of model interpretability. Communication s of the ACM 61(10), 36–43 (2018)
work page 2018
-
[3]
arXiv p reprint arXiv:1312.6034 (2013)
Simonyan, K., Vedaldi, A., Zisserman, A.: Deep inside convolutional n et- works: Visualising image classification models and saliency maps. arXiv p reprint arXiv:1312.6034 (2013)
arXiv 2013
-
[4]
Ribeiro, M.T., Singh, S., Guestrin, C.: ”why should i trust you?”: Ex plaining the predictions of any classifier. In: Proceedings of the 22nd ACM SIGK DD Inter- national Conference on Knowledge Discovery and Data Mining, pp. 1 135–1144 (2016)
work page 2016
-
[5]
Advances in Neural Information Processing Systems 30 (2017)
Lundberg, S.M., Lee, S.-I.: A unified approach to interpreting mod el predictions. Advances in Neural Information Processing Systems 30 (2017)
work page 2017
-
[6]
Knowled ge-based Systems 8(6), 373–389 (1995)
Andrews, R., Diederich, J., Tickle, A.B.: Survey and critique of tech niques for extracting rules from trained artificial neural networks. Knowled ge-based Systems 8(6), 373–389 (1995)
work page 1995
-
[7]
Garcez, A.d., Besold, T.R., De Raedt, L., F¨ oldiak, P., Hitzler, P., Ica rd, T., Kordjamshidi, P., Lamb, L.C., Miikkulainen, R., Silver, D.L.: Neural-symbo lic computing: An effective methodology for principled integration of ma chine learning and reasoning. FLAP 6(4), 611–632 (2019)
work page 2019
-
[8]
arXiv pr eprint arXiv:1510.00149 (2015)
Han, S., Mao, H., Dally, W.J.: Deep compression: Compressing deep n eural net- work with pruning, trained quantization and huffman coding. arXiv pr eprint arXiv:1510.00149 (2015)
arXiv 2015
Show all 19 references
-
[9]
In: Adva nces in Neural Information Processing Systems, pp
LeCun, Y., Denker, J.S., Solla, S.A.: Optimal brain damage. In: Adva nces in Neural Information Processing Systems, pp. 598–605 (1990)
1990
-
[10]
arXiv preprint arXiv:1711.07356 (2017)
Tjeng, V., Xiao, K., Tedrake, R.: Evaluating robustness of neur al networks with mixed integer programming. arXiv preprint arXiv:1711.07356 (2017)
2017 arXiv
-
[11]
In: International Confer ence on Machine Learning, pp
Serra, T., Tjandraatmadja, C., Ramalingam, S.: Bounding and co unting lin- ear regions of deep neural networks. In: International Confer ence on Machine Learning, pp. 8968–8977 (2020)
2020
-
[12]
Mathemat- ical Programming 183(1), 3–39 (2020) 19
Anderson, R., Huchette, J., Ma, W., Tjandraatmadja, C., Vielma , J.P.: Strong mixed-integer programming formulations for trained neural netwo rks. Mathemat- ical Programming 183(1), 3–39 (2020) 19
2020
-
[13]
arXiv preprint arX iv:2012.13349 (2020)
Nair, V., Bartunov, S., Gimeno, F., Von Glehn, I., Lichocki, P., Lobo v, I., O’Donoghue, B., Sonnerat, N., Tjandraatmadja, C., Wang, P., et al.: Solving mixed integer programs using neural networks. arXiv preprint arX iv:2012.13349 (2020)
2020 arXiv
-
[14]
Chemical Engineering Research and De sign 88(1), 55– 60 (2010)
Dua, V.: A mixed-integer programming approach for optimal con figuration of artificial neural networks. Chemical Engineering Research and De sign 88(1), 55– 60 (2010)
2010
-
[15]
Plos one 18(2), 0261029 (2023)
Thorbjarnarson, T., Yorke-Smith, N.: Optimal training of integ er-valued neural networks with mixed integer programming. Plos one 18(2), 0261029 (2023)
2023
-
[16]
IEEE Transactions o n Automatic Control 68(12), 7514–7529 (2023)
Schwan, R., Jones, C.N., Kuhn, D.: Stability verification of neural network controllers using mixed-integer programming. IEEE Transactions o n Automatic Control 68(12), 7514–7529 (2023)
2023
-
[17]
Constraints 23, 296–309 (2018)
Fischetti, M., Jo, J.J.: Deep neural networks and mixed integer lin ear optimiza- tion. Constraints 23, 296–309 (2018)
2018
-
[18]
In: International Conference on Artificia l Intelligence and Statistics (AISTATS) (2022)
P´ erez, J., Goel, S., Weller, A.: Fairness certification of neural n etworks via laurent polynomial optimization. In: International Conference on Artificia l Intelligence and Statistics (AISTATS) (2022)
2022
-
[19]
In: Pr oceedings of the AAAI Conference on Artificial Intelligence, vol
ElAraby, E., Rosenberg, C., Hsu, D., Shih, J.K., Cheung, A.: Oamip: Opti- mal architecture search using mixed-integer programming. In: Pr oceedings of the AAAI Conference on Artificial Intelligence, vol. 34, pp. 4011–4018 (2020) 20
2020
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.