Reformulating Non-Linear Optimization into Mixed-Integer Linear Programs

31 concepts28 papers1 proposal

Real-world engineering and economic systems are inherently messy. Whether you are routing data over millimeter-wave networks, managing a multi-fuel shipping fleet, or designing a carbon-capture plant, the underlying physics and economics introduce non-linear relationships. When these non-linearities are combined with discrete choices—such as selecting a specific engine type, opening a facility, or routing a packet—we get Mixed-Integer Nonlinear Programs (MINLPs).

MINLPs are notoriously difficult to solve. They combine the combinatorial explosion of discrete integer choices with the complex, non-convex geometry of non-linear surfaces. In contrast, Mixed-Integer Linear Programs (MILPs) are highly tractable. Decades of engineering have made industrial MILP solvers incredibly fast at navigating large search spaces using branch-and-bound algorithms and cutting planes.

The core insight of this research direction is simple: instead of building better non-linear solvers, we should transform non-linear problems into linear ones. By reformulating complex models into MILPs, researchers can leverage standard industrial solvers to find exact or near-optimal solutions that were previously computationally intractable.

Piecewise Linearization of Curves

The most intuitive way to eliminate a non-linear curve is to chop it up into straight line segments. This technique, known as piecewise linearization, replaces a continuous non-linear function with a set of linear approximations. To maintain the mathematical structure, binary variables are introduced to "select" which linear segment corresponds to the current operating point.

Consider the challenge of modeling an energy hub where conversion efficiency changes depending on the current load. Huang et al. handle this by approximating non-linear efficiency curves using a series of parallel, constant-efficiency linear segments. This transformation allows complex performance characteristics to be integrated directly into a standard MILP framework.

This geometric intuition applies across a wide variety of domains:

  • Industrial Carbon Capture: Samani applies piecewise linearization to approximate the non-linear physics of carbon capture and utilization plants, balancing mathematical accuracy with solver efficiency to enable real-time grid flexibility.
  • Telecommunications: In load-coupled LTE networks, You and Yuan approximate complex, concave load-coupling functions using linear segments, transforming an intractable network optimization problem into a manageable MILP.
  • Environmental Engineering: Zhang et al. linearize non-linear hydraulic equations to make the design of municipal reclaimed water distribution networks solvable via standard optimization tools.
  • Energy Systems: Zhao and Chu employ linearization to convert a complex MINLP model for integrating renewable energy and energy storage into a mixed-integer programming problem, preserving essential system dynamics while enhancing tractability.

Taming Bilinearities and Interferences

Non-linearity does not just arise from single-variable curves; it frequently occurs when two decision variables are multiplied together. These bilinear terms create non-convex landscapes that defeat standard linear solvers.

In strategic interactions, such as leader-follower congestion games, the leader's continuous strategy is multiplied by the followers' discrete equilibrium responses. To resolve this intractability, Castiglioni et al. use McCormick envelopes. This technique bounds the bilinear terms within a set of linear inequalities, allowing the continuous leader strategies to be optimized against discrete follower responses within a linear framework.

A similar challenge occurs in wireless network scheduling, where signal interference requirements introduce non-linear constraints. Niu et al. employ constraint linearization techniques to transform these interference requirements into a linear model, providing a clear benchmark for scheduling heuristics. In embedded systems, Mo et al. use mathematical lemmas to linearize non-linear task mapping and routing constraints, allowing industrial solvers to compute exact solutions for heterogeneous multicore architectures.

Structural Shifts and Variable Re-allocation

Sometimes, the key to linearization is not approximating the geometry, but fundamentally changing how the problem's variables and choices are structured.

For instance, in system synthesis, choosing between discrete hardware configurations typically yields a non-linear optimization landscape. Jansen et al. demonstrate that by converting these discrete configuration choices into nondeterministic branches within a standard Markov Decision Process (MDP), the non-linear problem can be solved using efficient linear programming techniques. This structural shift reduces computation times from minutes to seconds.

From a complexity theory perspective, Niedermeier et al. manage the computational overhead of mixed-integer programming by utilizing continuous rational variables to model non-linear shapes. Because solvers scale polynomially with continuous variables but exponentially with discrete ones, this strategy allows the inclusion of complex constraints without triggering an exponential explosion in discrete variables.

Similarly, Hou reformulates a mixed-integer non-polynomial routing problem into a non-linear programming framework to simplify the optimization landscape, while You captures production scheduling dynamics by transforming a non-linear mixed-integer program into a linear MILP to facilitate the use of standard solvers. In maritime logistics, Wu et al. transform a complex non-linear integer programming model for multi-fuel engine selection into a linear integer programming model, making advanced decision support accessible to industry practitioners.

Variable Reduction and Learning-Based Simplification

The ultimate form of reformulation involves reducing the problem size or complexity before the solver even begins its search.

In large-scale supply chain design, You and Grossmann show that reformulating a general non-linear integer programming model into a mixed-integer non-linear framework can significantly reduce the total number of binary variables required, making stochastic inventory problems tractable.

Taking this a step further, recent work leverages machine learning to automate and accelerate this reduction process. Li et al. introduce a framework that learns to reduce complex MILPs into simpler, equivalent linear programs by predicting which integer variables can be fixed and identifying active constraints. This data-driven transformation yields massive speed improvements compared to traditional industrial solvers while maintaining high solution quality.

Key Foundational Work

Mixed-Integer Nonlinear Programming Models and Algorithms for Large-Scale Supply Chain Design with Stochastic Inventory Management (2008) — contributed 2 concept elements to this direction.
Cross-layer optimization for routing data traffic in UWB-based sensor networks (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_milp_reformulation_7172c6f6,
  title = {MILP reformulation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/milp-reformulation/rdr_7172c6f6bef94f5ea288c6780e1aeed6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_milp_reformulation_7172c6f6_v1,
  title = {MILP reformulation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/milp-reformulation/rdr_7172c6f6bef94f5ea288c6780e1aeed6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake