Neural Network Embedding#
This tutorial shows how to embed a trained neural network as algebraic constraints in a discopt optimization model, enabling optimization over ML surrogates with global optimality guarantees.
The approach follows the ideas from OMLT [Ceccon et al., 2022] and the
strong MIP formulations of [Anderson et al., 2020], adapted to discopt’s
expression DAG, the POUNCE AD tape in the Rust core, and McCormick
relaxations for spatial branch-and-bound. (JAX is not on the default solve
path; a plain solve() imports no jax module.)
Overview#
The discopt.ml module provides:
NetworkDefinition: An intermediate representation for sequential feedforward networks.NNFormulation: A builder that embeds the network into adiscopt.Modelas variables and constraints.Five formulation strategies:
full_space— Explicit pre/post-activation variables with smooth activation constraints (sigmoid, tanh, softplus, squareplus, Swish/SiLU, GELU; the last four take a sharpnessbeta, e.g.DenseLayer(W, b, Activation.SOFTPLUS, beta=10.0)).relu_bigm— Big-M MILP formulation for ReLU networks using binary variables.relu_partition— Partition-based MILP [Kronqvist et al., 2021, Tsay et al., 2021]: each neuron’s sum is split inton_partitionspieces, giving relaxations between big-M (P = 1) and the convex hull.relu_extended— The per-neuron convex hull (extended formulation) of Anderson et al. [2020]. Big-M plusideal_cuts=Truereaches the same hull by separating Anderson et al.’s ideal inequalities throughmodel.solve(cut_callback=nn.cut_callback).reduced_space— Nested expressions with no intermediate variables (small networks).
load_onnx: Load trained models from ONNX format (covers scikit-learn, PyTorch, Keras exports).
Example: Optimize over a trained neural network#
We’ll train a small neural network to approximate a function, then find the input that minimizes the network’s output subject to constraints.
import discopt.modeling as dm
import numpy as np
from discopt.ml import (
Activation,
DenseLayer,
NetworkDefinition,
NNFormulation,
)
Step 1: Define a trained network#
Here we manually specify a small 2-layer ReLU network.
In practice, you would train this with scikit-learn, PyTorch, etc.
and load via load_onnx().
# A small 2-input, 4-hidden, 1-output ReLU network
np.random.seed(0)
W1 = np.random.randn(2, 4) * 0.5
b1 = np.random.randn(4) * 0.1
W2 = np.random.randn(4, 1) * 0.5
b2 = np.random.randn(1) * 0.1
net = NetworkDefinition(
layers=[
DenseLayer(W1, b1, Activation.RELU),
DenseLayer(W2, b2, Activation.LINEAR),
],
input_bounds=(np.array([-2.0, -2.0]), np.array([2.0, 2.0])),
)
print(f"Network: {net.input_size} -> {net.layers[0].n_outputs} -> {net.output_size}")
print(f"Forward pass at [0, 0]: {net.forward(np.array([0.0, 0.0]))}")
Network: 2 -> 4 -> 1
Forward pass at [0, 0]: [0.17936536]
Step 2: Embed in a discopt model with big-M formulation#
The relu_bigm strategy introduces binary variables for each ReLU neuron
where the pre-activation value can be positive or negative.
Interval arithmetic bound propagation computes tight big-M constants.
m = dm.Model("nn_optimization")
nn = NNFormulation(m, net, strategy="relu_bigm", prefix="surrogate")
nn.formulate()
# Minimize the network output
m.minimize(nn.outputs[0])
# Add constraints on the inputs
m.subject_to(nn.inputs[0] + nn.inputs[1] >= -1.0, name="sum_lb")
print(m.summary())
Model: nn_optimization
Variables: 15 (11 continuous, 4 integer/binary)
Constraints: 19
Objective: minimize surrogate_zhat_1[0]
Parameters: 0
result = m.solve(time_limit=60)
print(f"Status: {result.status}")
print(f"Optimal objective: {result.objective:.6f}")
print(f"Optimal inputs: {result.value(nn.inputs)}")
print(f"Network output: {result.value(nn.outputs)}")
# Verify against numpy forward pass
x_opt = result.value(nn.inputs)
nn_check = net.forward(x_opt)
print(f"NumPy forward check: {nn_check}")
# ...and against an independent dense grid over the feasible input box, so
# "optimal" is checked rather than taken on trust.
g = np.linspace(-2, 2, 1201)
a, b = np.meshgrid(g, g, indexing="ij")
pts = np.stack([a.ravel(), b.ravel()], axis=1)
pts = pts[pts[:, 0] + pts[:, 1] >= -1.0] # the sum_lb constraint
grid_min = float((np.maximum(pts @ W1 + b1, 0) @ W2 + b2).min())
print(f"Grid reference (1201x1201): {grid_min:.6f}")
assert abs(result.objective - grid_min) < 1e-5, (
f"{result.objective} != grid reference {grid_min}"
)
Status: optimal
Optimal objective: 0.149408
Optimal inputs: [-0.15139554 0.12563868]
Network output: [0.14940791]
NumPy forward check: [0.14940791]
Grid reference (1201x1201): 0.149408
Step 3: Compare with smooth formulation#
For networks with smooth activations (sigmoid, tanh, softplus, and the ReLU-like activations below),
the full_space strategy creates nonlinear constraints that get McCormick
relaxations, differentiated by the POUNCE AD tape.
Note
The full_space route on a scalar-output network exercises an axis reduction:
a width-1 affine layer is emitted as dm.sum(W.T * prev, axis=1) with a single
row. Until #1364 that
reduction was mishandled in two places — the Rust FBBT read a reduction’s
enclosure as its operand’s hull (narrow rather than conservative, so the
tightening could cut the optimum out of the box) and the scalarizer could not
expand it at all (so the per-node LP came back status="error") — and this
cell returned -0.230589 as optimal with gap_certified=True against a true
minimum of -0.579405. Both are fixed, so the cell below now asserts
against an independent dense grid instead of merely printing the gap.
# Same network structure but with tanh activation
net_smooth = NetworkDefinition(
layers=[
DenseLayer(W1, b1, Activation.TANH),
DenseLayer(W2, b2, Activation.LINEAR),
],
input_bounds=(np.array([-2.0, -2.0]), np.array([2.0, 2.0])),
)
m2 = dm.Model("smooth_nn")
nn2 = NNFormulation(m2, net_smooth, strategy="full_space")
nn2.formulate()
m2.minimize(nn2.outputs[0])
result2 = m2.solve(time_limit=60)
print(f"Status: {result2.status} (gap_certified={result2.gap_certified})")
print(f"Reported objective: {result2.objective:.6f} bound: {result2.bound:.6f}")
print(f"Reported inputs: {result2.value(nn2.inputs)}")
# Independent dense grid over the same input box (no constraints on this model).
g2 = np.linspace(-2, 2, 1201)
a2, b2_ = np.meshgrid(g2, g2, indexing="ij")
pts2 = np.stack([a2.ravel(), b2_.ravel()], axis=1)
vals2 = np.tanh(pts2 @ W1 + b1) @ W2 + b2
grid_min2 = float(vals2.min())
print(f"Grid reference: {grid_min2:.6f} at {pts2[vals2.argmin()]}")
assert abs(result2.objective - grid_min2) < 1e-4, (
f"{result2.objective} != grid reference {grid_min2}"
)
# The certificate itself: a valid dual bound never rises above the true optimum.
assert result2.bound <= grid_min2 + 1e-6, (
f"bound {result2.bound} is ABOVE the true optimum {grid_min2}"
)
Status: optimal (gap_certified=True)
Reported objective: -0.579405 bound: -0.579454
Reported inputs: [-2. -0.90869638]
Grid reference: -0.579405 at [-2. -0.91]
Smooth ReLU-like activations and the sharpness parameter beta#
Besides sigmoid and tanh, discopt.ml embeds four smooth, ReLU-like
activations. Each takes a sharpness (inverse temperature) beta > 0, given as
DenseLayer(W, b, activation, beta=...), and they all scale the same way:
\(f_\beta(z) = g(\beta z)/\beta\). As \(\beta \to \infty\) each one tends to
ReLU, and \(\beta = 1\) is the textbook form.
|
\(f_\beta(z)\) |
Monotone? |
|---|---|---|
|
\(\log(1 + e^{\beta z})/\beta\) ( |
yes |
|
\(\tfrac12\left(z + \sqrt{z^2 + 4/\beta^2}\right)\) |
yes |
|
\(z\,\sigma(\beta z)\) |
no |
|
\(z\,\Phi(\beta z)\), with \(\Phi\) the standard normal CDF |
no |
Squareplus [Barron, 2021] is the Chen–Harker–Kanzow–Smale
smoothing of \(\max(z, 0)\) [Chen and Harker, 1993, Kanzow, 1996] with smoothing
parameter \(b = 4/\beta^2\). Swish [Ramachandran et al., 2017] is the SiLU of
Elfwing et al. [2018] at \(\beta = 1\), and GELU is from
Hendrycks and Gimpel [2016]. Every formulation (full_space, reduced_space,
and the smooth layers of relu_bigm), interval bound propagation and
NetworkDefinition.forward use the same beta. LINEAR, RELU, SIGMOID and
TANH have no sharpness parameter and raise an error for beta != 1 instead of
ignoring it.
Folding beta into the weights (scaling W, b by beta and the next layer by
1/beta) gives the same function. But it changes the pre-activation bounds,
and the model no longer reads as a softplus with sharpness beta, so passing
beta directly is preferred.
from discopt.ml.activations import activation_interval, activation_minimizer, evaluate
def row(label, values):
print(f"{label:>20s}:" + "".join(f"{v:9.4f}" for v in values))
z = np.array([-2.0, -0.5, 0.0, 0.5, 2.0])
row("z", z)
for act in [Activation.SOFTPLUS, Activation.SQUAREPLUS, Activation.SWISH, Activation.GELU]:
for beta in [1.0, 10.0]:
row(f"{act.value} beta={beta:g}", evaluate(act, z, beta))
row("relu", np.maximum(z, 0))
z: -2.0000 -0.5000 0.0000 0.5000 2.0000
softplus beta=1: 0.1269 0.4741 0.6931 0.9741 2.1269
softplus beta=10: 0.0000 0.0007 0.0693 0.5007 2.0000
squareplus beta=1: 0.4142 0.7808 1.0000 1.2808 2.4142
squareplus beta=10: 0.0050 0.0193 0.1000 0.5193 2.0050
swish beta=1: -0.2384 -0.1888 0.0000 0.3112 1.7616
swish beta=10: -0.0000 -0.0033 0.0000 0.4967 2.0000
gelu beta=1: -0.0455 -0.1543 0.0000 0.3457 1.9545
gelu beta=10: -0.0000 -0.0000 0.0000 0.5000 2.0000
relu: 0.0000 0.0000 0.0000 0.5000 2.0000
Bounds for non-monotone activations#
Swish and GELU decrease and then increase, with a single negative minimum at
\(z^\star = u^\star/\beta\) (\(u^\star \approx -1.2785\) for Swish and
\(-0.7518\) for GELU). So the image of a pre-activation interval
\([\ell, u]\) is not \([f(\ell), f(u)]\): when the interval contains
\(z^\star\), the lower end is \(f(z^\star)\). Bound propagation
(propagate_bounds, and with it every formulation’s post-activation box and
big-M constants) uses this exact image. The rule for monotone activations
would cut reachable values out of the box:
lo, hi = -2.0, 0.0
for act in [Activation.SWISH, Activation.GELU]:
z_star, f_star = activation_minimizer(act, beta=1.0)
naive = sorted([float(evaluate(act, lo)), float(evaluate(act, hi))])
lb, ub = activation_interval(act, np.array([lo]), np.array([hi]))
sampled = evaluate(act, np.linspace(lo, hi, 100_001))
print(f"{act.value}: minimizer z* = {z_star:.6f}, f(z*) = {f_star:.6f}")
print(f" monotone rule [f(lo), f(hi)] = [{naive[0]:.6f}, {naive[1]:.6f}]")
print(f" exact image = [{lb[0]:.6f}, {ub[0]:.6f}]")
print(f" sampled range = [{sampled.min():.6f}, {sampled.max():.6f}]")
swish: minimizer z* = -1.278465, f(z*) = -0.278465
monotone rule [f(lo), f(hi)] = [-0.238406, 0.000000]
exact image = [-0.278465, 0.000000]
sampled range = [-0.278465, 0.000000]
gelu: minimizer z* = -0.751792, f(z*) = -0.169971
monotone rule [f(lo), f(hi)] = [-0.045500, 0.000000]
exact image = [-0.169971, 0.000000]
sampled range = [-0.169971, 0.000000]
Example: a sharpened Swish network#
The same weights as the ReLU example, with a Swish hidden layer at
beta = 3, solved to global optimality with the full_space formulation and
checked against a dense grid:
# The same weights as above, now with a sharpened Swish hidden layer.
net_swish = NetworkDefinition(
layers=[
DenseLayer(W1, b1, Activation.SWISH, beta=3.0),
DenseLayer(W2, b2, Activation.LINEAR),
],
input_bounds=(np.array([-2.0, -2.0]), np.array([2.0, 2.0])),
)
m3 = dm.Model("swish_nn")
nn3 = NNFormulation(m3, net_swish, strategy="full_space")
nn3.formulate()
m3.minimize(nn3.outputs[0])
result3 = m3.solve(time_limit=60)
print(f"Status: {result3.status} (gap_certified={result3.gap_certified})")
print(f"Reported objective: {result3.objective:.6f} bound: {result3.bound:.6f}")
x3 = np.asarray(result3.value(nn3.inputs))
print(f"Optimal inputs: {x3} forward check: {net_swish.forward(x3)[0]:.6f}")
# Independent check: dense grid over the input box.
g = np.linspace(-2, 2, 1201)
a, b = np.meshgrid(g, g, indexing="ij")
pts = np.stack([a.ravel(), b.ravel()], axis=1)
print(f"Dense-grid minimum: {net_swish.forward(pts).min():.6f}")
Status: optimal (gap_certified=True)
Reported objective: 0.078812 bound: 0.078805
Optimal inputs: [-0.63081113 0.10443406] forward check: 0.078812
Dense-grid minimum: 0.078812
Reading beta from trained models#
load_torch_sequential keeps each activation’s parameters.
nn.Softplus(beta=10) becomes DenseLayer(..., Activation.SOFTPLUS, beta=10.0),
nn.SiLU becomes SWISH, and nn.GELU() becomes GELU. A parameter that
cannot be embedded raises an error rather than being dropped:
nn.GELU(approximate="tanh") is refused, and so is an nn.Softplus whose
threshold (where torch switches to the linear tail) is low enough to make
torch’s function differ from the smooth softplus by more than 1e-8. Torch’s
default threshold=20 is accepted. The ONNX Softplus operator has no beta
and is read as beta = 1. Torch exports nn.Softplus(beta != 1) as
Mul -> Softplus -> Div, which load_onnx refuses because the graph is not a
plain sequence of dense and activation layers. The exact (approximate="none")
ONNX Gelu operator is supported.
Formulation strategies#
Strategy |
Activations |
Variables |
Method |
|---|---|---|---|
|
sigmoid, tanh, softplus, squareplus, swish, gelu |
Explicit per neuron |
NLP with McCormick relaxations |
|
ReLU (+ smooth) |
Binary per ReLU neuron |
MILP big-M constraints |
|
ReLU (+ smooth) |
Binary + |
MILP, partition-based [Tsay et al., 2021] |
|
ReLU (+ smooth) |
Binary + |
MILP, per-neuron convex hull [Anderson et al., 2020] |
|
All |
None (nested expressions) |
NLP, best for small nets |
Choose relu_bigm for ReLU networks (most common in practice). The three
ReLU MILPs have the same feasible set; their LP relaxations are ordered
big-M ≤ partition ≤ extended, at the price of more variables and rows.
Partitions that are not nested need not be ordered among themselves (P = 3 can
be looser than P = 2).
Choose full_space for smooth networks when you want tight McCormick
relaxations for global optimization. Choose reduced_space for very
small networks where compilation overhead matters.