Many real optimization problems include a rule nobody can write down as an equation. Examples are "this reactor design is safe" and "this food basket is palatable." Practitioners therefore learn the rule from data with a classifier or regressor, then embed that model into a mixed-integer program, meaning an optimization problem with both continuous and integer variables that a solver such as Gurobi searches globally. The solver then behaves like an adversary. It searches for the inputs where the learned model is wrong and returns designs that satisfy the model but violate reality. The current fix, conformal calibration, adds a safety margin sized by the model's errors on held-out data. When the model is blurry near the true feasibility boundary, which is exactly where the optimum usually sits, the margin becomes wide and the solver is pushed far from good solutions.
This note proposes replacing the usual global ReLU network with a multi-resolution hash encoding. That is a stack of coarse-to-fine grids whose corner points store learned feature vectors in small hash tables, read out by a tiny decoder. The encoding is modified so that the whole learned constraint is exactly piecewise linear and can be written as a compact mixed-integer linear program. The bet has two parts. Hash grids fit sharp, non-convex boundaries far better than MLPs of similar size, so the conformal margin should shrink. And once training is done, hash lookups become fixed constants that the solver can enumerate cheaply. Under the same guaranteed feasibility rate, the outcome should be better objectives and comparable solve times.
Core Claim
At a fixed conformal feasibility guarantee $1-\alpha$, a simplex-interpolated hash-grid surrogate yields narrower calibration margins and better optimal objectives than ReLU networks, gradient-boosted trees, and dense grids of matched mixed-integer size. The effect should appear when the learned constraint lives in a low-dimensional input space, or decomposes into low-dimensional pieces, and has a sharp, non-convex boundary.
What is new is not "use a hash grid as a classifier." It is two things together. The first is an exact mixed-integer encoding of a trained multi-resolution hash surrogate. To our knowledge, the research file reports no existing formulation of this kind. The second is the claim that the grid's ability to fit fine detail translates into tighter feasibility margins inside an optimization loop.
Prior Work and Where This Sits
Two papers motivate the proposal. Mixed-Integer Optimization with Constraint Learning (OptiCL) embeds linear models, trees and MLPs into mixed-integer programs. It stops the solver from wandering into regions with no data by restricting it to the convex hull of the training data, which cannot represent concave or disconnected feasible regions. Conformal Mixed-Integer Constraint Learning with Feasibility Guarantees (C-MICL) adds conformal margins to ReLU networks and boosted trees. It meets 95% ground-truth feasibility at a 7–8% objective cost relative to uncalibrated "risky" methods. Neither paper changes the learner. We keep C-MICL's calibration machinery unchanged and swap only the model underneath it, so any gain is attributable to the surrogate.
Two other papers supply the method. How Learnable Grids Recover Fine Detail in Low Dimensions shows that learnable multigrid encodings raise the smallest eigenvalue of the neural tangent kernel by about eight orders of magnitude over plain MLPs. The neural tangent kernel governs how fast each frequency is learned, so this means fine detail is learned quickly. That paper also reports 15 dB higher PSNR than MLPs and 12 dB higher than Fourier features on 2D regression. Learning Constraints for Structured Prediction Using Rectifier Networks shows that small ReLU networks translate into linear inequalities for integer programs. It is the template we extend to grid lookups.
Two papers constrain the design. Grids Often Outperform Implicit Neural Representation at Compressing Dense Signals finds that plain interpolated grids beat Instant-NGP-style hash models on dense signals at equal parameter count. Hash hybrids win only on sparse, boundary-like signals such as 3D occupancy. A feasibility indicator is precisely a boundary signal, which is why we expect hashing to help here. Even so, a dense grid must be a first-class baseline, and we must test where the crossover lies. The same paper and the research file's analysis of corner-count growth (each lookup touches $2^d$ corners) rule out applying a single grid to the 80-variable spaces of Sudoku-style constraint acquisition. We therefore restrict the claim to constraints over $d \le 4$ inputs, plus additive sums of such low-dimensional pieces.
Efficient physics-informed neural networks using hash encoding shows that multilinear interpolation has discontinuous derivatives, which forced a switch to finite differences there. For a mixed-integer solver this non-smoothness is harmless, and piecewise linearity is in fact what makes an exact encoding possible.
Research Program
The first component is the surrogate. Standard hash encodings interpolate multilinearly inside each grid cell, which produces products of coordinates and is not linear. We instead split each cell into simplices (the Kuhn triangulation) and interpolate barycentrically, so each level is piecewise linear in $x$. Reading out the concatenated features with a linear head makes the surrogate output $g(x)=\sum_{l=1}^{L} w_l^\top \phi_l(x)+b$ exactly piecewise linear. Here $\phi_l(x)$ is the interpolated feature at level $l$ of $L$ levels, and $w_l, b$ are the head weights. A variant with a single small ReLU hidden layer adds one standard Big-M indicator per hidden unit. We will first verify that simplex interpolation does not sacrifice the fitting advantage reported for multilinear grids, by measuring boundary-fit error on synthetic masks.
The second component is the exact mixed-integer formulation. After training, every table entry is a constant. Hash collisions therefore add nothing to the program: two corners sharing an entry simply share a constant. At each level we select the active cell with logarithmically many binary variables per dimension, choose the simplex within the cell by ordering the fractional coordinates, and express $\phi_l(x)$ as a convex combination of the selected simplex's corner values. The number of binary variables then grows with $d \log_2 N_l$ per level rather than with the number of parameters, where $N_l$ is the grid resolution at level $l$. We also exploit the nesting of geometrically spaced resolutions to share cell-selection variables across levels where the resolutions align. The deliverable is an open-source translator from trained models to Gurobi or Pyomo, with a proof that the formulation is exact.
The third component is calibration and decomposition. Conformal margins are computed exactly as in C-MICL. For constraints over more than four features, we fit an additive model of hash grids on selected pairs and triples of features. The pieces are chosen by greedy search on validation error, in the spirit of the low-dimensional decompositions suggested by small-scope queries in constraint acquisition. This extension is explicitly secondary. If it fails, the claim stands only for genuinely low-dimensional constraints, and we will report that limit.
Baselines
The naive reference is uncalibrated constraint learning with the same ReLU network C-MICL uses (C-MICL's "MICL" baseline). It shows how badly the solver exploits an uncorrected model. We report its ground-truth feasibility rate and objective.
The strongest existing method is C-MICL with conformalized ReLU networks and gradient-boosted trees. It reports meeting the 0.95 feasibility target on Membrane Reactor Design and Food Basket Design, an objective cost 7–8% above risky heuristics, and runtimes two orders of magnitude below the W-MICL ensemble heuristic (Conformal Mixed-Integer Constraint Learning with Feasibility Guarantees). The file gives no absolute objective values, so we will rerun it on our splits. Fairness is enforced by matching the number of binary variables in the final program and the solver time limit, and by giving every model the same hyperparameter search budget, the same training data, and the same calibration set. Beating it means a better objective at equal or higher realized feasibility, without a slower solve beyond the matched time limit.
OptiCL's convex-hull trust region with a conformal-free MLP is run on the same tasks. Its reported MLP fit on the World Food Programme palatability constraint is MSE 0.055 (Mixed-Integer Optimization with Constraint Learning), which we take as the reference fit for that task.
Two ablations isolate the key ingredients. The first is a dense single- or multi-level simplex grid with the same encoding but no hashing, matched in binary count. It tests whether hashing itself matters or only locality. The second is a single-resolution hash grid. It tests whether the multi-scale structure matters.
Why not just…?
Why not just use gradient-boosted trees, which are already local and MILP-friendly? This is the most serious threat. Trees are piecewise constant, which fits a boundary indicator well, and C-MICL already supports them. Their splits are axis-aligned, so diagonal or curved boundaries need many leaves. Their output is a step function, so conformal residuals stay large in the band where the boundary cuts across a leaf. We expect trees to match us on axis-aligned boundaries and lose on curved or oblique ones. The synthetic suite deliberately includes both kinds, and if trees match us on the curved cases we will report that the advantage does not exist.
Why not just use a dense interpolated grid? The equal-budget results in Grids Often Outperform Implicit Neural Representation at Compressing Dense Signals make this a fair question. Inside a mixed-integer program, a dense grid and a hash grid of the same resolution cost the same number of binary variables, so hashing helps only through better generalization at a fixed parameter count. That benefit should appear for boundary-like signals with small training sets and vanish for dense ones. The dense-grid ablation, swept over training-set size, settles this. If the dense grid ties everywhere, the contribution reduces to the exact simplex-grid formulation, which is still useful but smaller.
Why not just use a wider ReLU network or Fourier features? The neural tangent kernel and PSNR gaps in How Learnable Grids Recover Fine Detail in Low Dimensions suggest these fit fine boundaries poorly at a matched size. Width also costs one binary variable per hidden unit, and Fourier features add sine and cosine terms that are not linear and need their own piecewise approximation. Matching binary counts in the baselines measures this trade-off directly.
Proposed Experiments
The synthetic stage uses 2D and 3D feasibility masks with known ground truth. These include the radial star targets, random spheres, and Sierpinski shapes from Grids Often Outperform Implicit Neural Representation at Compressing Dense Signals, together with smooth convex controls. Each mask is paired with a linear objective whose optimum lies on the boundary. We measure four things: conformal margin width at $\alpha=0.05$, realized ground-truth feasibility of the solver's returned solution, optimality gap against the true constrained optimum, and solve time.
The applied stage reruns Membrane Reactor Design and Food Basket Design from C-MICL and the World Food Programme palatability task from OptiCL. For the higher-dimensional tasks we use the additive low-dimensional decomposition.
The decisive check is a single plot of objective gap against realized feasibility for every surrogate at matched binary count. The proposal succeeds if the hash surrogate's curve dominates C-MICL's ReLU and tree curves on the non-convex synthetic masks. It also needs to be at least competitive on the applied tasks. The proposal fails if margin width does not shrink relative to those baselines, because the whole mechanism rests on tighter calibration. A secondary check plots solve time against grid depth $L$, to confirm that binary-variable growth stays logarithmic in practice.
References
- Mixed-Integer Optimization with Constraint Learning
- Conformal Mixed-Integer Constraint Learning with Feasibility Guarantees
- How Learnable Grids Recover Fine Detail in Low Dimensions: A Neural Tangent Kernel Analysis of Multigrid Parametric Encodings
- Learning Constraints for Structured Prediction Using Rectifier Networks
- Grids Often Outperform Implicit Neural Representation at Compressing Dense Signals
- Efficient physics-informed neural networks using hash encoding