# Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools

arXiv: https://arxiv.org/abs/1708.00050 · HTML: https://mlsanity.com/paper/1708.00050/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2017.

## Built on by (most cited first, 7 of 7)

- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert](https://mlsanity.com/paper/2308.09474/) (2023)
- [Generating Likely Counterfactuals Using Sum-Product Networks](https://mlsanity.com/paper/2401.14086/) (2024)
- [Piecewise Polynomial Regression of Tame Functions via Integer Programming](https://mlsanity.com/paper/2311.13544/) (2023)
- [Characterizing the Discrete Geometry of ReLU Networks](https://mlsanity.com/paper/2606.07728/) (2026)
- [Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate](https://mlsanity.com/paper/2505.01985/) (2025)
- [An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions](https://mlsanity.com/paper/2605.00855/) (2026)

## Abstract (arXiv)

We present novel mixed-integer programming (MIP) formulations for optimization over nonconvex piecewise linear functions. We exploit recent advances in the systematic construction of MIP formulations to derive new formulations for univariate functions using a geometric approach, and for bivariate functions using a combinatorial approach. All formulations are strong, small (so-called logarithmic formulations), and have other desirable computational properties. We present extensive experiments in which they exhibit substantial computational performance improvements over existing approaches. To accompany these advanced formulations, we present PiecewiseLinearOpt, an extension of the JuMP modeling language in Julia that implements our models (alongside other formulations from the literature) through a high-level interface, hiding the complexity of the formulations from the end-user.