Integers and curves
Draft
A mixed-integer nonlinear program is an optimization problem in which some of the variables must take whole-number values and some of the functions are nonlinear. Written in the form used throughout this series, with \(x\) for the continuous variables and \(y\) for the integer ones, it is
\[\begin{aligned} z^\star \;=\; \min_{x,\,y}\ & f(x, y) \\ \text{subject to}\ & g_i(x, y) \le 0, \qquad i = 1, \dots, m, \\ & l \le (x, y) \le u, \qquad x \in \mathbb{R}^n,\quad y \in \mathbb{Z}^p . \end{aligned}\]The four letters abbreviate the four classes this display contains. Drop the integer variables and the problem is a nonlinear program, an NLP. Make every function linear and it is a mixed-integer linear program, a MILP. Do both and it is a linear program, an LP. Keep both and it is a MINLP. Each of the two ingredients, integrality and curvature, is a classical difficulty with its own literature. Problems with both ingredients arise whenever a discrete choice and a continuous quantity are decided together. Two examples are the siting of a plant together with its operating level, and the choice of which securities to hold together with the size of each position. The tax-lot problem of Section 9, in which the choice is which lots to sell and the quantity is how many shares of each, is the one this series is written toward.
The four classes of the display, and how one becomes another
make every function linear
MINLP ----------------------------------> MILP
| |
| drop the | drop the
| integer | integer
| variables | variables
v v
NLP ----------------------------------> LP
make every function linear
keep both ingredients, integrality and curvature: a MINLP;
remove both: an LP
The smallest instance the series carries shows every symbol of the display at work. It is R3 of Section 1.6, the MINLPLib instance st_e13: minimize \(2x + y\) subject to \(1.25 - x^2 - y \le 0\) and \(x + y \le 1.6\), with \(0 \le x \le 1.6\) and \(y \in \{0, 1\}\). In the display \(n = p = 1\) and \(m = 2\); the objective is \(f(x, y) = 2x + y\), the constraints are \(g_1 = 1.25 - x^2 - y\) and \(g_2 = x + y - 1.6\), and the bounds are \(l = (0, 0)\) and \(u = (1.6, 1)\). The one integer variable and the one curved constraint are enough to put it in the last class, and its optimal value \(z^\star = 2.0\) is attained at \((x, y) = (0.5, 1)\), which Section 1.1 works out from the definitions.
This series is a self-contained account of the subject for a reader who knows mathematics and not optimization. Its weight is on the nonconvex case, in which the continuous part of the problem can itself have many local optima. That is where the open problems are, and it is where the post that follows this series will do its work. Two numbers set the scene. On Mittelmann's benchmark run of 26 February 2026, two hundred instances from the MINLPLib collection were given two hours each on a twelve-core desktop. The best of the four solvers whose results may be published solved 158 of the 200 within the benchmark's tolerances, and at least one of the four solved 183.H. D. Mittelmann, "Mixed Integer Nonlinear Programming Benchmark (MINLPLIB)", page dated 26 February 2026, plato.asu.edu/ftp/minlp.html: 200 MINLPLib instances run through GAMS, two hours each, AMD Ryzen 9 5900X, feasibility tolerance \(10^{-6}\), failures counted at the time limit; BARON solved 158, SCIP 154, LINDO 116 and SHOT 96, where the page's solved counts include runs with the result status "solved not verified"; Gurobi and Xpress were run but their results are marked "publication suppressed". The 183 is the row "optimal auto settings" of the per-instance table plato.asu.edu/ftp/compare.txt (read 5 October 2026), the number of instances solved by at least one of the four published solvers; its LINDO column is from a later run, of 6 March 2026, with 119 solved. Of the 1,633 instances in that library, 1,218 are classified nonconvex, and 538 had a recorded gap above a relative \(10^{-4}\) in the library's export read on 5 October 2026 (latest addition 18 March 2026). This series calls those instances open. The gap is the distance between the best known solution, whose feasibility the library checks to an infeasibility of \(10^{-8}\), and the best bound any solver has proved. The library's own criterion for a solved instance is a relative gap of \(10^{-6}\), which 1,001 instances meet. The \(10^{-4}\) cut is this series's.M. R. Bussieck, A. S. Drud and A. Meeraus, "MINLPLib—a collection of test models for mixed-integer nonlinear programming", INFORMS Journal on Computing 15 (2003). The counts are from the library's export at minlplib.org, read 5 October 2026 (1,633 instances, latest addition 18 March 2026): 376 convex, 1,218 nonconvex, 39 unclassified; 1,095 with a recorded gap of at most \(10^{-4}\) and 538 with a larger gap; 1,001 with a gap of at most \(10^{-6}\), the library's own threshold for "solved" as stated on its documentation page, read the same day. The library reports primal bounds at an infeasibility of at most \(10^{-8}\) and dual bounds per solver. Linear problems with tens of thousands of integer variables are solved routinely, and Section 8 tabulates the sizes at which each class of this series is solved today.The collection on which this is measured is MIPLIB 2017: A. Gleixner et al., "MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library", Mathematical Programming Computation 13 (2021). The progress of the solvers on its 240-instance benchmark set is measured in T. Koch, T. Berthold, J. Pedersen and C. Vanaret, "Progress in mathematical programming solvers from 2001 to 2020", EURO Journal on Computational Optimization 10 (2022), which Section 5.1 reports. Nonconvex problems with a few hundred products of continuous variables often are not. The series explains why that is, what has been done about it, and what a massively parallel machine can and cannot do for it.
Three threads run through the text, and every method named below is a combination of them. The first is relaxation. A nonconvex problem is replaced by a convex one that is easier to solve and whose feasible set contains the original's, so the easier problem's value is a bound on the harder one's. The second is search. The distance between that bound and the best solution in hand is closed by splitting the problem into pieces, relaxing each piece on its own, and discarding every piece whose bound shows that it cannot hold a better solution. The third is formulation. One set of feasible points can be described by many systems of constraints, and the relaxation depends on the description. The bound, and with it the size of the search, therefore depends on how the problem was written down.
The sections follow that order. Section 1 states the problem, fixes the vocabulary, and draws the line between convex and nonconvex that organizes everything after it. It then says what a local method proves, shows that integrality is itself a nonconvexity, reviews what is known about hardness, and ends by defining the six running examples. Section 2 is about relaxations and bounds: the relaxation and the gap, duality, one complete solve that attaches each term of the vocabulary to an event, convex envelopes, presolve and domain reduction. Section 3 is about search: branch and bound, the heuristics that find solutions, cutting planes, the convex case, spatial branch and bound for the nonconvex case, what a solver actually does at a node, and Lagrangian bounds and decomposition. Section 4 treats formulation as a design problem: formulation strength, disjunctions, the perspective, the quadratic structures that portfolio problems have, piecewise-linear models, lifting and the semidefinite hierarchy, cones, reformulations that are themselves algorithms, what can be written at all, and a table that ranks the relaxations. Section 5 reports what moved in the solvers over two decades: how the field measures itself, the global solvers that finish, heuristics that do not need the LP, learning inside the tree and exact arithmetic. Section 6 is about parallelism: what parallelizes in a tree search, the theory of parallel branch and bound, the systems that have been built, and branch and bound on a GPU. Section 7 is about the GPU itself: what it is good at, first-order methods for linear programs, safe bounds from inexact duals, first-order methods inside a tree, interior-point and nonlinear solvers on the GPU, quadratic, conic and semidefinite programs, heuristics, and a research agenda for ultra-fast nonconvex MINLP. Section 8 lists what remains open, Section 9 turns to the tax problem, and Section 10 gives further reading.
At the end the reader should be able to do four things. The first is to read a global solver's log and know what each line certifies. The second is to look at a nonconvex model, design a relaxation for it, and say how tight the relaxation will be. The third is to write a spatial branch-and-bound that proves global optimality to a stated tolerance. The fourth is to reason about which parts of such a solver a GPU accelerates and which parts it does not.
The figures are not pictures of results computed elsewhere. Each one solves a small problem in the page, and its controls change the problem. The prose quotes the numbers the figure displays in its default view, so the reader can check them. Six running examples carry through the series, numbered R1 to R6. R1 is a two-variable integer program over a polygon, and R2 is the bilinear problem of maximizing \(xy\) under \(2x + y \le 1.2\). R3 is the MINLPLib instance st_e13, and R4 is Haverly's pooling problem. R5 is a portfolio of three assets that may hold at most two of them, and R6 is eight tax lots of one stock. Section 1.6 gives their data and the numbers the later sections quote.
Notation. Continuous variables are \(x \in \mathbb{R}^n\) and integer variables are \(y \in \mathbb{Z}^p\). When the distinction does not matter a single vector \(x\) carries an index set \(I\) of integer coordinates. Bounds are \(l \le x \le u\) and the box they define is \(B = [l, u]\). The objective is \(f\), the constraints are \(g_i(x) \le 0\) for \(i = 1, \dots, m\), and the feasible set is \(\mathcal F\). The optimal value is \(z^\star\). The value of a relaxation is \(z_R\), or \(z_{\mathrm{LP}}\) when the relaxation is a linear program. The value of the best feasible point in hand, the incumbent, is \(z_{\mathrm{inc}}\), and \(\varepsilon\) is a tolerance. The convex hull of a set \(S\) is \(\operatorname{conv}(S)\) and the epigraph of a function \(f\) is \(\operatorname{epi} f\), both defined in Section 1.2. These are the symbols Section 1 uses. The following are fixed here so that the series uses one notation throughout, and each is defined where it first occurs. The convex and concave envelopes of \(f\) on a box are \(\operatorname{vex}_B f\) and \(\operatorname{cav}_B f\) (defined for one parabola in Section 1.4 and in general in Section 2.4). Multipliers are \(\lambda \ge 0\), the Lagrangian is \(L(x, \lambda) = f(x) + \lambda^\top g(x)\), the dual function is \(q(\lambda)\) and the dual optimum is \(d^\star \le z^\star\) (Section 2.2). A node of a branch-and-bound tree is one subproblem of the search of Section 3, obtained by restricting the box. It is written \(N\), with box \(B_N\) and relaxation value \(\bar z(N)\). The list of nodes not yet examined, the open nodes, is \(\mathcal L\), and to prune a node is to discard it (Sections 2.1 and 2.3, with the algorithm in Section 3.1). Intervals are written \([a, b]\) (Section 2.6). For quadratic problems the lifted matrix is \(X = x x^\top\) with entries \(X_{ij}\) (Section 4.7). Minimization is the default in every general display of this series. Three of the running examples are written as maximizations where they are defined in Section 1.6: the drawn two-variable program R1, the bilinear example R2 and the pooling problem R4. That is how they are usually stated and drawn, and the text says so each time one of them appears.
The notation on a branch-and-bound tree (general displays minimize)
the problem: box B = [l, u], feasible set F,
objective f, optimal value z*
/ \
a node N: the box B_N, obtained a pruned node:
by restricting the box; its discarded
relaxation value zbar(N)
/ \
open node open node L: the list of the open
nodes, not yet examined
values z_R <= z* <= z_inc
a relaxation optimum the incumbent, the
best feasible point
in hand
(General disclaimers apply.) Nothing here is investment, legal or tax advice. The tax rules sketched in Section 9 are stated from memory, with the sections of the statute against which they can be checked, and they remain unverified. The solver versions, benchmark figures and paper results are as published at the dates given, and the sidenotes say where.