Spending Compute to Save Memory: Memory-Capped Branch-and-Bound for Nonconvex Binary Quadratics

Branch-and-bound solves discrete optimization problems by splitting the search into a tree of smaller problems. At each node it solves a continuous "relaxation", a version of the problem where integer variables may take fractional values, to get a lower bound on the best solution in that subtree. Subtrees whose bound is worse than the best known solution are discarded. On hard instances the list of unexplored nodes grows until the machine runs out of memory. When the objective is nonconvex, the relaxations stop giving trustworthy bounds, and solvers either fall back to heuristics or give up their optimality guarantees. This note proposes a solver for nonconvex quadratic problems over binary variables with three properties: it keeps a certified optimality gap, it runs under a hard memory cap, and it treats the accuracy of each node's relaxation solve as the knob that converts spare computation into saved memory.

The idea fits in two sentences. Frank-Wolfe, an optimization method that moves toward the best vertex of the feasible region at each step, produces a valid lower bound at every iteration, not only at convergence. That makes it safe to stop a node solve early, and safe to evict a node from memory while keeping only a single number. So when memory is scarce the solver should solve nodes more tightly, which prunes more children and keeps the open list small, and when memory is plentiful it should solve them loosely and branch quickly.

Core Claim

For binary variables, the identity $x_i^2 = x_i$ lets us add $\sum_i \lambda_i (x_i^2 - x_i)$ to a nonconvex quadratic objective without changing its value at any integer point. With large enough diagonal shifts $\lambda_i$, the shifted objective is convex on the continuous relaxation, so its relaxation bounds are valid for the original problem. A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization uses this trick, but in its partial form, which leaves the relaxation nonconvex. The authors report that partial shifting finds better incumbent solutions than full shifting, and that their method runs purely as a primal heuristic with no dual certificate. We take the opposite division of labor. The fully convexified objective drives bounding inside a convex Frank-Wolfe branch-and-bound in the style of Convex integer optimization with Frank-Wolfe methods and Boscia.jl: A review and tutorial. The partially convexified objective is used only to search for incumbent solutions near the vertices that Frank-Wolfe has already discovered. This resolves the tension the research file identifies between primal quality and valid pruning, because the two jobs no longer share one objective.

The new ingredient is how inexactness and memory are coupled. At a node with Frank-Wolfe iterate $x$ and Frank-Wolfe gap $g$, the node's convexified objective $\tilde f$ satisfies $\tilde f(x) - g \le \min \tilde f$ over that node's relaxation. The node can therefore be pruned whenever $\tilde f(x) - g \ge U$, where $U$ is the incumbent value. Boscia tightens its inner tolerance as nodes get deeper in the tree. We instead make the tolerance depend on memory pressure:

$$\varepsilon(m) = \varepsilon_{\max}\,\Big(1 - \tfrac{m}{M}\Big)^{\alpha} + \varepsilon_{\min},$$

where $m$ is the solver's current memory use, $M$ is the hard cap, $\alpha > 0$ controls how sharply accuracy rises as memory fills, and the node solve stops when it is pruned or when $g \le \varepsilon(m)$.

The same anytime-bound property makes eviction lossless with respect to correctness. A node's open-list record holds the scalar bound $\tilde f(x) - g$, branching information, and its Frank-Wolfe "active set", the list of vertices whose convex combination is the current iterate. Under pressure the active set can be truncated to its $k$ heaviest vertices, or dropped entirely. The bound stays valid, and only the warm start is lost. Memory-bounded search usually has to choose between storing a node and recomputing it from scratch. Here there is a graded choice, priced in Frank-Wolfe iterations.

Research Program

We will build the solver on the Boscia architecture. It reuses Boscia's mixed-integer linear minimization oracle, its warm-starting from the parent's active set, and its caching of discarded vertices. On top of this we add four components.

The first is a per-variable diagonal shift for full convexification, computed once at the root by a cheap diagonal-dominance or eigenvalue bound. We also test whether re-tightening the shift at deep nodes, where many variables are fixed, pays for itself.

The second is a hard memory accountant that tracks open-list records, active-set vertices, and the vertex cache in bytes.

The third is a best-first node order with the memory-pressure tolerance rule above. When the cap binds, eviction proceeds in a fixed order. Cached vertices go first, filtered by usefulness in the spirit of the difficulty-window caching of Using Caching to Solve Larger Probabilistic Planning Problems. Active sets are truncated next. Only as a last resort does the solver fall back to depth-first diving, the move Search Strategies for Optimal Classification and Regression Trees reports being forced into when best-first search exhausts memory.

The fourth is an incumbent search on the partially shifted objective, reusing the active-set neighborhood search of the primal-heuristic paper.

On the analysis side, we will show three things. Every pruning decision remains valid under any eviction or truncation, which follows directly from the anytime gap. With a positive floor $\varepsilon_{\min}$, the procedure terminates with a certified gap of at most $\varepsilon_{\min}$. Finally, we will characterize the trade-off on a simple model. Tightening a node by $\Delta\varepsilon$ costs about $O(1/\Delta\varepsilon)$ Frank-Wolfe iterations, the standard sublinear rate. It saves memory in proportion to the expected number of children pruned. The model should predict when memory-driven tolerance beats depth-driven tolerance, namely when the cap binds early relative to the incumbent's quality.

The inexact-solving literature supplies the method, not the motivation. The tolerance schedules of Inexact first-order primal-dual algorithms and the summable-error conditions of New inertial proximal gradient methods for unconstrained convex optimization problems concern a single outer sequence and assume compute is the only resource. Our schedule responds to a second resource. We deliberately do not use the difference-of-convex route of Revisiting Frank-Wolfe for Structured Nonconvex Optimization for bounding. Its linearization of the concave part produces an upper surrogate and only stationarity guarantees, so it cannot certify subtrees. We may borrow it for incumbent search.

Baselines

The naive reference point is Boscia applied to the fully convexified objective with its default depth-based tolerance, unlimited memory, and no eviction, then rerun under the same caps with the process terminated when the cap is hit. This shows how often memory, rather than time, is the failure mode for Frank-Wolfe branch-and-bound on these instances. MIRACLE (MIRACLE: Model-free Imitation and Reinforcement Learning for Adaptive Cut-Selection) reports this failure mode for linear solvers, where SCIP failed on 47–53% of difficult MIPLIB instances because of memory or time limits.

The strongest existing competitors are global solvers that certify nonconvex quadratics, namely Gurobi and SCIP. Both can write nodes to disk past a threshold, so they already have a memory-capping mechanism. On the incumbent side, the reference result is from A Frank-Wolfe-based primal heuristic for quadratic mixed-integer optimization. Within a five-minute limit on QPLIB's discrete instances, it found solutions better than Gurobi's on 30 instances and better than SCIP's on 94, found feasible solutions on 163 of 166 MIQP instances, and found eight new best-known solutions. That paper reports no dual gaps, so no reported certified-gap result for it was found on Lacuna. Every system will run single-threaded with the same time limit and the same process memory caps of 256 MB, 1 GB, and 4 GB, plus an uncapped reference, enforced at the operating-system level. Gurobi's and SCIP's own node-file and memory parameters will be tuned on a held-out set of 30 instances with the same tuning budget we give our three hyperparameters $\varepsilon_{\max}$, $\alpha$, and $k$.

Three ablations isolate the key ingredient. The first replaces memory-driven tolerance with Boscia's depth-driven tolerance while keeping eviction. The second replaces graded active-set truncation with all-or-nothing eviction. The third uses a single shift for both bounding and primal search, either full or partial. Beating the baselines means two things at the 256 MB and 1 GB caps. Our solver should close more instances to a certified 1% gap than every competitor, or reach a lower median final gap. Its incumbents should not be worse than the primal heuristic's on more than a small fraction of instances.

Why not just…?

Why not just solve every node to high accuracy? Tight node solves are the extreme of our own rule, so this is included as the fixed-$\varepsilon_{\min}$ setting. The inexact-solving literature (Inexact first-order primal-dual algorithms) and Boscia's design both argue that accurate early solves waste compute. We expect fixed tight tolerance to do well under severe caps and badly without them. If it matches our rule at every cap, the adaptive schedule contributes nothing, and we will report that.

Why not just let Gurobi or SCIP page nodes to disk? This is the real threat, because these solvers combine mature spatial branching with node files. The research file's evidence against disk-backed search comes from heuristic lookup tables: Compressing Pattern Databases reports up to three-orders-of-magnitude speedups from keeping compressed tables in RAM. That concerns random-access lookups. Sequential node files may suffer far less, so we cannot assume the result transfers. The head-to-head comparison under equal caps settles it. If the global solvers with node files match us on certified gaps, our contribution narrows to Frank-Wolfe-specific instance classes. Those would be instances with expensive combinatorial structure where the oracle is cheap and outer-approximation cuts are dense.

Why not just dive depth-first when memory runs out? Depth-first search needs memory proportional only to depth. However, Search Strategies for Optimal Classification and Regression Trees shows best-first search proving optimality up to 10× faster on regression trees because tight bounds propagate early. Our solver contains depth-first diving as its last-resort mode. The ablation that triggers diving immediately at the cap, without tolerance tightening or truncation, measures what the intermediate steps buy.

Why not use the partially convexified objective for bounds too, since it gives better primal solutions? Its relaxation is nonconvex. The Frank-Wolfe gap then bounds stationarity, not optimality, and pruning becomes unsound. The single-shift ablation quantifies the price in incumbent quality of insisting on validity.

Proposed Experiments

The main testbed is QPLIB's 319 instances with discrete variables, restricted to those whose discrete variables are binary so that the shift identity applies. Within that set we separate convex and nonconvex objectives and report results per class. A control suite uses the MIPLIB 2017 instances with quadratic objectives from Convex integer optimization with Frank-Wolfe methods. There, exploiting strong convexity halved some solve times and cut node counts by about 25%, so we can check that our changes do not hurt the convex case when memory is uncapped. QAPLIB's quadratic assignment instances, used by the difference-of-convex Frank-Wolfe paper, provide permutation-structured nonconvex problems where the linear oracle is the Hungarian algorithm.

Metrics are the fraction of instances certified to 1% gap, the final certified gap, the primal-dual integral, peak resident memory, Frank-Wolfe iterations per node, and node counts. All are plotted against the memory cap.

The decisive check is the shape of the curve as the cap shrinks. Under the depth-based schedule, certified-gap closure should collapse at small caps. Under the memory-driven schedule, total Frank-Wolfe iterations should rise while closure degrades gracefully. The trade-off model from the research program predicts the cap at which the two curves cross, and agreement between predicted and observed crossover is the test of whether we understand the mechanism. A second check is diagnostic. On instances where the full diagonal shift is large, the convexified bound may be too weak for any schedule to help. We will report shift magnitude against gap closed, so that failures can be traced to the convexification and not to the memory policy.