Decomposing and Relaxing Mixed Integer Nonlinear Programs

62 concepts58 papers

Imagine trying to optimize a modern infrastructure system, such as a regional power grid or a municipal water network. You face two fundamentally different types of decisions at the same time.

First, you have discrete, logical choices: Should we build this specific pipeline? Should this transmission line switch be open or closed? Second, you must satisfy continuous physical laws: How does water pressure change according to nonlinear hydraulic equations? How does alternating current flow through a network of lines?

When you combine these two paradigms, you get a Mixed-Integer Nonlinear Program (MINLP). Individually, discrete optimization and continuous nonlinear optimization are already difficult. Combined, they form one of the most challenging frontiers in mathematical optimization because they force solvers to navigate a landscape that is simultaneously combinatorial and non-convex.

The Core Challenge: The Combinatorial Non-Convex Trap

To understand why MINLPs are notoriously difficult, consider how standard solvers tackle pure Mixed-Integer Linear Programs (MILPs). They typically solve a continuous relaxation—temporarily ignoring the integer constraints to treat variables as continuous numbers between 0 and 1. This provides an easy-to-compute mathematical bound (a lower bound for minimization) that allows branch-and-bound algorithms to systematically prune away subtrees of discrete choices without exploring them.

In an MINLP, this strategy breaks down. Because the continuous constraints are nonlinear and often non-convex, the continuous relaxation itself is full of local traps and false peaks. You can no longer trust that a local continuous solver has found the true optimal bound.

Furthermore, as shown by Cornelius Brand and Martin Koutecký in Parameterized Algorithms for MILPs with Small Treedepth, the coupling between discrete and continuous variables can cause high fractionality, where continuous variables explode into solutions with massive denominators. This makes discrete approximations computationally prohibitive. This mathematical friction shows up across real-world infrastructure, from alternating-current optimal power flows analyzed by Dan Bienstock et al. in Mathematical programming formulations for the alternating current optimal power flow problem to real-time pump scheduling investigated by Ye Wang et al. in Minimizing Pumping Energy Cost in Real-time Operations of Water Distribution Systems using Economic Model Predictive Control.

The Classical Playbook: Polyhedral Relaxation and Decomposition

How do we solve a problem that is simultaneously combinatorial and non-convex? The classical playbook relies on two core ideas: polyhedral relaxation (approximating smooth, curved spaces with flat, linear faces) and decomposition (separating the integer decisions from the continuous physics).

Outer Approximation and Polyhedral Cuts

In a foundational work, Ignacio E. Grossmann et al. in An outer-approximation algorithm for a class of mixed-integer nonlinear programs introduced the Outer-Approximation (OA) algorithm. Instead of dealing with the nonlinear constraints directly, the OA algorithm solves a series of alternating problems:

  1. An integer master problem that uses linear "supporting hyperplanes" (tangent lines) to approximate the nonlinear feasible region from the outside.
  2. A continuous subproblem that optimizes the nonlinear functions given a fixed set of integer decisions.

By drawing flat tangent lines around the continuous space, the algorithm turns the continuous part into a polyhedron that an integer linear solver can easily navigate.

   True Non-Convex Space           Polyhedral Outer Approximation
          _______                             _______
         /       \                           /       \
        /  (Trap) \                         /|       |\
_______/           \_______       _________/ |       | \_________
                                             (Linear Cuts)

To make these approximations tight enough to guarantee global optimality, modern solvers must continuously inject mathematical constraints called "cuts." For instance, Andreas Lundell and Jan Kronqvist developed advanced polyhedral approximation strategies in Polyhedral approximation strategies for nonconvex mixed-integer nonlinear programming in SHOT to extend these concepts to non-convex landscapes.

Similarly, Max Klimm et al. derived valid cuts specifically tailored to physical networks in Valid Cuts for the Design of Potential-based Flow Networks, preventing combinatorial explosion by cutting away large swathes of infeasible integer configurations early. To handle highly non-linear terms, Harsha Nagarajan et al. proposed dynamic multivariate partitioning in Tightening McCormick Relaxations for Nonlinear Programs via Dynamic Multivariate Partitioning, placing grid points dynamically where they matter most to tighten McCormick relaxations.

Decomposition Frameworks

When problems grow too large for a single monolithic solver, decomposition splits the burden. Bingqian Liu et al. leverage a generalized Benders decomposition approach in A generalized Benders decomposition approach for the optimal design of a local multi-energy system to isolate discrete master planning decisions from non-convex operational subproblems.

In a similar vein, Tiago Andrade et al. utilize relaxation strategies in The p-Lagrangian relaxation for separable nonconvex MIQCQP problems to handle separable non-convex quadratic constraints. By penalizing constraint violations in the objective function rather than enforcing them rigidly, they decouple the problem into independent, manageable pieces.

This strategy is mirrored by Jiangwei Hou et al. in A Fast Solution Method for Large-scale Unit Commitment Based on Lagrangian Relaxation and Dynamic Programming, where the authors combine Lagrangian relaxation with dynamic programming to solve massive unit commitment problems in power systems, achieving rapid convergence by decoupling global system requirements from local physical constraints.

The Modern Frontier: Learning to Optimize

While classical decomposition and relaxation provide rigorous convergence guarantees, they can be slow for real-time operations. Traditional solvers treat every new optimization problem as a completely blank slate, re-running expensive branch-and-bound trees from scratch. This has led to a major paradigm shift: using machine learning to learn the underlying structure of solutions.

Instead of searching the discrete space from scratch every time, recent frameworks treat optimization as a statistical learning problem. For example, Bo Tang et al. proposed a learning-to-optimize (L2O) framework in Learning to Optimize for Mixed-Integer Nonlinear Programming that embeds specialized "integer correction layers" and feasibility projection mechanisms directly into neural networks. This allows the network to predict high-quality, feasible integer solutions instantly, bypassing the expensive combinatorial search.

Traditional MINLP Solver:
[Problem Instance] ──> [Branch-and-Bound Loop (Slow)] ──> [Optimal Solution]

Learning-to-Optimize (L2O):
[Problem Instance] ──> [Neural Network + Correction Layer] ──> [Feasible Solution (Instant)]

Other approaches rethink how the solution space is navigated entirely. Ruihuai Liang demonstrated in Diffusion Models as Network Optimizers: Explorations and Analysis that Generative Diffusion Models can act as network optimizers. Rather than mapping inputs to a single deterministic point, they learn the underlying probability distribution of high-quality solutions across non-convex and mixed-integer spaces, smoothing out the combinatorial hurdles.

Furthermore, when the underlying physics are too complex to write down explicitly, researchers are embedding neural networks directly into the optimization loop. Jonathan Stollberg et al. utilized physics-augmented neural networks to model material behaviors within a multiscale topology optimization framework in Multiscale topology optimization of functionally graded lattice structures based on physics-augmented neural network material models, showing how deep learning can resolve the extreme computational costs of simultaneous macro-scale geometry and micro-scale density design.

Key Foundational Work

Computational experience with dicopt solving MINLP problems in process systems engineering (1989) — contributed 2 concept elements to this direction.
An outer-approximation algorithm for a class of mixed-integer nonlinear programs (1987) — 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_mixed_integer_nonlinear_optimization_453a984a,
  title = {mixed-integer nonlinear optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mixed-integer-nonlinear-optimization/rdr_453a984a86bd43139fd0bbba39647e7b},
  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_mixed_integer_nonlinear_optimization_453a984a_v1,
  title = {mixed-integer nonlinear optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mixed-integer-nonlinear-optimization/rdr_453a984a86bd43139fd0bbba39647e7b/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