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 a discopt.Model as 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 sharpness beta, 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 into n_partitions pieces, 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 plus ideal_cuts=True reaches the same hull by separating Anderson et al.’s ideal inequalities through model.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.

Activation

\(f_\beta(z)\)

Monotone?

SOFTPLUS

\(\log(1 + e^{\beta z})/\beta\) (torch.nn.Softplus(beta))

yes

SQUAREPLUS

\(\tfrac12\left(z + \sqrt{z^2 + 4/\beta^2}\right)\)

yes

SWISH (alias "silu")

\(z\,\sigma(\beta z)\)

no

GELU

\(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

full_space

sigmoid, tanh, softplus, squareplus, swish, gelu

Explicit per neuron

NLP with McCormick relaxations

relu_bigm

ReLU (+ smooth)

Binary per ReLU neuron

MILP big-M constraints

relu_partition

ReLU (+ smooth)

Binary + P continuous per ReLU neuron

MILP, partition-based [Tsay et al., 2021]

relu_extended

ReLU (+ smooth)

Binary + n_in continuous per ReLU neuron

MILP, per-neuron convex hull [Anderson et al., 2020]

reduced_space

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.