Mixed-Integer Nonlinear Programming (MINLP)
Mixed-Integer Nonlinear Programming (MINLP) is one of the most expressive and challenging classes of optimization problems. It combines the features of Nonlinear Programming (NLP) and Mixed-Integer Linear Programming (MILP) by allowing both nonlinear relationships and integer or binary decision variables within the same model.
MINLP is essential for modeling complex systems where decisions are discrete but governed by nonlinear physical, economic, or logical laws. Typical application areas include process engineering, energy systems, supply chain design, telecommunications, finance, and scheduling.
What is Mixed-Integer Nonlinear Programming (MINLP)?
Formally, a Mixed-Integer Nonlinear Program (MINLP) seeks to optimize a nonlinear objective function subject to nonlinear constraints, with a subset of variables restricted to integer values. A general MINLP can be written as:
- Minimize or maximize a nonlinear objective function
- Subject to nonlinear equality and/or inequality constraints
- With some variables continuous and others integer or binary
If all nonlinearities are removed, the problem reduces to a Mixed-Integer Linear Program (MILP). If all variables are continuous, the problem becomes a Nonlinear Program (NLP). MINLP, therefore, sits at the intersection of these two fundamental problem classes.
The feasible region of an MINLP is typically nonconvex and discrete, making these problems among the hardest in mathematical optimization.
Convex vs. Nonconvex MINLP
As with continuous NLP, a crucial distinction exists between convex and nonconvex MINLPs:
- In convex MINLP, the continuous relaxation is convex. While still computationally difficult due to integrality, these problems allow stronger theoretical guarantees and more effective global optimization methods.
- In nonconvex MINLP, nonlinearities and integrality interact to create multiple local optima, disconnected feasible regions, and highly complex search spaces.
This distinction strongly influences the choice of algorithms and the feasibility of finding globally optimal solutions.
Solving Mixed-Integer Nonlinear Programs
MINLPs are typically solved using hybrid algorithms that combine techniques from MILP and NLP:
- Spatial Branch-and-Bound, which extends Branch-and-Bound by partitioning both integer domains and continuous variable ranges,
- Outer Approximation, which alternates between NLP subproblems and MILP master problems,
- Generalized Benders Decomposition, extending classical Benders ideas to nonlinear settings,
- Branch-and-Cut methods enhanced with nonlinear relaxations and cutting planes.
For large or highly nonconvex problems, solvers often rely on heuristics, local search, and relaxation-based approximations to obtain high-quality feasible solutions.
Extensions and related problem classes
Mixed-Integer Nonlinear Programming (MINLP) acts as a unifying framework across optimization:
- It generalizes Mixed-Integer Linear Programming (MILP) by introducing nonlinear constraints and objectives.
- It generalizes Nonlinear Programming (NLP) by incorporating discrete decisions.
- Many combinatorial optimization problems with nonlinear cost structures can be naturally modeled as MINLPs.
In practice, MINLP models are frequently reformulated, decomposed, or approximated to exploit problem structure and improve tractability.
Further reading and references
Duran, M. A., & Grossmann, I. E. (1986). An Outer-Approximation Algorithm for a Class of Mixed-Integer Nonlinear Programs. Mathematical Programming, 36(3), 307–339.
Introduced the outer approximation method, one of the most influential algorithmic frameworks for convex MINLP.
Floudas, C. A. (1995). Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications. Oxford University Press.
One of the earliest comprehensive textbooks covering both nonlinear programming and MINLP, with strong emphasis on global optimization and engineering applications.
Bonami, P., Kilinç, M., & Linderoth, J. (2012). Algorithms and Software for Convex Mixed Integer Nonlinear Programming. In Mixed Integer Nonlinear Programming (IMA Volumes in Mathematics and its Applications).
A key reference connecting MINLP theory with modern solver implementations, focusing on convex MINLP and branch-and-bound–based methods.