Nonconvex piecewise linear functions: Advanced formulations and simple modeling tools
Proposes novel logarithmic MIP formulations for nonconvex piecewise linear functions, achieving up to 3x speedup in complex instances.
Key Findings
Methodology
This work leverages geometric embedding and combinatorial disjunctive constraint frameworks to develop strong, compact MIP models for univariate and bivariate nonconvex piecewise linear functions. Using Vielma (2018)’s geometric techniques and Huchette & Vielma (2019a)’s combinatorial approach, the authors construct multiple formulations (LogE, LogIB, ZZI, ZZB) that scale logarithmically with the number of segments. The PiecewiseLinearOpt package automates model generation, simplifying complex formulations for end-users. These models balance model strength, size, and branching behavior, leading to significant computational improvements.
Key Results
- In univariate cases, the new models outperform existing approaches, with speedups up to 3x on hard instances, especially when segment counts are not powers of two. Bivariate models extend this advantage, achieving over tenfold acceleration. Experimental data shows improved LP relaxation tightness, balanced branchings, and reduced solution times across multiple solvers.
- Compared to SOS2 and incremental formulations, the proposed models maintain high strength while enhancing branching efficiency. They exhibit better scalability and robustness in large-scale problems, demonstrating practical superiority.
- The PiecewiseLinearOpt software supports all models, enabling automatic model creation and deployment, thus lowering implementation barriers and promoting adoption in industry and academia.
Significance
This research addresses fundamental bottlenecks in nonconvex optimization involving piecewise linear functions, offering models that are both theoretically strong and computationally efficient. The compactness and improved branching behavior facilitate solving large, complex problems in energy systems, transportation, and finance, potentially transforming industry practices and academic research. The integration of geometric and combinatorial techniques opens new avenues for modeling other nonconvex structures, bridging theory and practical application.
Technical Contribution
The paper introduces a unified framework combining geometric embedding and combinatorial disjunctive techniques to produce models with logarithmic size and ideal strength. It extends existing SOS2 formulations to multilevel encodings, including Gray codes and novel zig-zag codes, resulting in models that are both small and highly effective. The software implementation further democratizes access to advanced formulations, fostering broader adoption and innovation.
Novelty
This is the first comprehensive application of geometric embedding and combinatorial disjunctive frameworks to construct multiple classes of logarithmic MIP formulations for nonconvex piecewise linear functions, especially in the bivariate case. The development of new encoding schemes (e.g., zig-zag codes) and their integration into software tools represent significant innovations that surpass prior state-of-the-art models in scalability, strength, and usability.
Limitations
- Extension to higher dimensions (>2D) remains challenging due to exponential growth in model complexity, requiring further research for scalable solutions.
- The models assume structured domain partitions (e.g., grid triangulations), limiting applicability to irregular or highly non-uniform domains.
- Despite improvements, large instances with extremely many segments or complex geometries still pose computational hurdles, necessitating heuristic or approximation methods.
Future Work
Future research will focus on extending these formulations to higher-dimensional nonconvex functions, integrating machine learning techniques for adaptive model selection, and optimizing software tools for real-world large-scale problems. Exploring hybrid approaches combining these models with heuristics could further enhance scalability and robustness.
AI Executive Summary
Optimizing nonconvex piecewise linear functions is a longstanding challenge in mathematical programming, often hindered by large model sizes and weak relaxations. Traditional approaches either suffer from scalability issues or fail to produce tight bounds, limiting their practical utility in complex applications such as energy networks, transportation, and finance.
This paper introduces a suite of advanced mixed-integer programming (MIP) formulations that leverage recent geometric embedding and combinatorial disjunctive constraint techniques. These models, including LogE, LogIB, ZZI, and ZZB, are designed to scale logarithmically with the number of segments, maintaining model strength while significantly reducing size. The authors demonstrate that these formulations outperform existing models by up to three times in computational speed, especially on instances where segment counts are not powers of two.
A key innovation is the development of software tools—PiecewiseLinearOpt—that automate the generation of these complex models, making them accessible to practitioners. Extensive computational experiments validate the models’ superior performance, showing tighter LP relaxations, more balanced branchings, and faster solution times across multiple solvers. The models’ robustness and scalability suggest broad applicability in industry sectors requiring efficient nonconvex optimization.
While promising, the work also highlights ongoing challenges, such as extending models to higher dimensions and irregular domains, and handling extremely large instances. Nonetheless, this research marks a significant step forward in nonconvex optimization, providing both theoretical insights and practical tools that could reshape how complex nonlinear problems are tackled in the future.
Deep Dive
Abstract
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.