Source-linked AI summary
ReLU Networks as Surrogate Models in Mixed-Integer Linear Programs
Bjarne Grimstad, Henrik Andersson
TL;DR
Embedding ReLU surrogate models in MILPs requires tight big-M bounds, especially when networks are part of larger optimization problems with output constraints. The paper develops bound-tightening procedures that use both input and output bounds, finding that tightening can substantially improve solution outcomes while small ReLU networks remain practical surrogate models.
Problem
MILP formulations of ReLU networks depend on tight big-M bounds, but existing tightening approaches primarily use input bounds and single networks.
Method
The paper develops and studies bound-tightening procedures for multiple interlinked ReLU networks embedded as global surrogate models in MILPs.
Results
Bound tightening may reduce solution times considerably, and in a real application it enabled solving to optimality within the practical time limit rather than finding no feasible solution.
Takeaways & Limitations
Small-sized ReLU networks are an attractive surrogate-modeling approach for process optimization within MILPs.
Takeaways & Limitations
The MILP formulation is practically limited to small-sized ReLU networks, although many nonlinearities can be approximated at that size.
Abstract
from arXiv · showhide
We consider the embedding of piecewise-linear deep neural networks (ReLU networks) as surrogate models in mixed-integer linear programming (MILP) problems. A MILP formulation of ReLU networks has recently been applied by many authors to probe for various model properties subject to input bounds. The formulation is obtained by programming each ReLU operator with a binary variable and applying the big-M method. The efficiency of the formulation hinges on the tightness of the bounds defined by the big-M values. When ReLU networks are embedded in a larger optimization problem, the presence of output bounds can be exploited in bound tightening. To this end, we devise and study several bound tightening procedures that consider both input and output bounds. Our numerical results show that bound tightening may reduce solution times considerably, and that small-sized ReLU networks are suitable as surrogate models in mixed-integer linear programs.
1. Introduction
The paper studies ReLU networks as piecewise-linear surrogate models embedded in MILPs, focusing on how bound tightening affects formulation performance. It develops procedures that exploit both input and output bounds and reports practical benefits, including successful optimization with small networks.
- Motivation: ReLU networks provide piecewise-linear surrogate models that can represent complex nonlinear relationships within a MILP framework.Their affine and ReLU operators are sufficient for many approximation tasks, and shallow ReLU networks are universal approximators.
- Motivation: Output bounds in grey-box optimization enable stronger bound tightening than procedures that only propagate input bounds forward through one network.Multiple interlinked ReLU networks create algebraic output constraints that can be propagated backwards.
- Contributions: The paper introduces a general framework unifying bound-tightening procedures for output-bounded ReLU networks.The procedures are designed to exploit output constraints when computing big-M values.
- Contributions: Computational experiments show a trade-off between time spent tightening bounds and the resulting optimization solution time.The study evaluates tightening strength, optimization performance, and an oil-production application with ten ReLU surrogate models.
- Contributions: In a real application, bound tightening separates failure to find a feasible solution from solving the problem to optimality within the practical time limit.This result supports the practical value of exploiting output bounds in the MILP formulation.
- Scope: The study targets accurate global surrogate models for one-shot process optimization rather than iterative sampling and reoptimization.The authors note that the findings may support more sophisticated model-based global derivative-free optimization methods.
2. Piecewise-linear approximations of nonlinear functions
Piecewise-linear models provide MILP-compatible approximations for complex nonlinear functions, while ReLU networks offer adaptive, scalable, and data-flexible alternatives to structured interpolation schemes.
- Piecewise-linear approximation: For unknown, nonseparable, or highly complex functions, sampling can support construction of piecewise-linear approximations for MILP models.The sampled points may be scattered across the domain, including when they represent experiments.
- Piecewise-linear approximation: Rectilinear grids create exponentially many boxes and simplices as dimension increases, making them impractical beyond low-dimensional problems.With ten intervals per variable, the reported simplex counts and growth prohibit practical use for n > 3.
- Piecewise-linear approximation: Rectilinear sampling cannot locally adjust resolution, so refining important regions also increases sampling elsewhere.This structure can require unnecessary dense sampling in regions without important features.
- Regression-based approximations: Regression models control the number of linear pieces, helping balance approximation accuracy against MILP complexity because binary-variable counts scale with partition regions.The paper links avoiding unnecessary regions to faster optimization of surrogate models.
- ReLU networks as surrogate models: ReLU networks are continuous piecewise-linear functions that can be represented exactly in MILP, unlike sigmoid or hyperbolic networks, which require operator approximations.Their capacity can be adjusted through depth and width, with an upper bound of O(W^L n0) regions for L hidden layers of width W.
- ReLU networks as surrogate models: ReLU networks adaptively partition domains, train on scattered and noisy data, and scale to large datasets through stochastic-gradient training with regularization.Parameter updates refine regions around important features, while regularization controls complexity and generalization.
3. A 0–1 MILP model for ReLU networks
The paper formulates fully connected ReLU networks as exact 0–1 MILPs by representing layer operations and ReLU logic with linear constraints, binary activation variables, and big-M bounds.
- Network structure: A ReLU network maps x0 to xK through K + 1 fully connected layers parameterized by weight matrices W^k and bias vectors b^k.Hidden-layer outputs apply the componentwise activation σ(y) = max{0, y}, while the final layer is affine.
- Network structure: Each hidden layer computes its output from the preceding layer's vector and the parameters θk = (W^k, bk).The network structure is presented both in aggregated input-to-output form and as disaggregated layer variables and parameters.
- ReLU formulation: The ReLU operator is represented by separating its positive and negative parts and enforcing linear constraints so that the output follows ReLU logic.The formulation assumes finite lower and upper bounds for the affine input to each ReLU.
- MILP formulation: A binary activation variable is introduced for each hidden node, yielding a 0–1 MILP formulation whose binary-variable count scales linearly with the number of hidden nodes.The resulting constraint matrices have a special block-angular structure.
- MILP formulation: The formulation is exact: for a fixed input vector, its output variables equal the ReLU network output, with degeneracy only when a node input is zero.At zero input, the activation binary may be either 0 or 1 without changing the output.
- Alternative formulations: Complementary- and indicator-constraint alternatives avoid explicit big-M values but tend to produce harder mixed-integer instances for current solvers.This motivates the use of big-M formulations despite their dependence on bound quality.
4. Bound tightening procedures
The section formulates bound tightening around ReLU-network feasible sets with both input and output constraints, then develops increasingly strong relaxation-based procedures. These procedures trade computational cost against tighter bounds and can exploit backward propagation from output bounds.
- Motivation: Input and output constraints define a restricted feasible set whose tightened bounds should be used when computing ReLU big-M values.Output constraints can shrink variable domains beyond the initial network bounding boxes.
- Relaxations: The ReLU relaxation replaces binary restrictions with 0 ≤ z ≤ 1, allowing partial or complete relaxation of ReLU logic.This relaxation may permit positive outputs even when a preactivation is negative, so output bounds depend on both upper and lower network bounds.
- Relaxations: Layer relaxations remove constraints from selected layers, enabling cheaper forward propagation while retaining only part of the network structure.Removing following layers makes the target node an output node and supports forward bound propagation.
- Prototype procedure: The prototype iterates through layers and nodes, builds a procedure-specific constraint set, solves lower- and upper-bound problems, and updates the bounds.The resulting tightened bounds can identify positive neurons or dead neurons and thereby remove corresponding binary variables.
- Procedure trade-offs: Feasibility-based procedures are computationally cheap but may produce sub-optimal bounds, whereas stronger procedures include more constraints and can exploit integer information.Forward-only procedures may miss output bounds; backward bound propagation requires starting from the last layer or linking tightened variables to outputs.
- Optimization-based bound tightening: OBBT procedures use the described relaxations to solve series of optimization problems, including variants that retain or relax following layers to support stronger propagation.The SEMI-RR procedure keeps following layers while relaxing their ReLU operators, addressing a limitation of removing all subsequent layers.
5. Numerical study
The numerical study evaluates bound-tightening procedures across randomly initialized ReLU networks, quadratic-function surrogates, and an oil-production optimization problem. Results show trade-offs between bound tightness and computational cost, with output-aware procedures improving optimization performance but becoming expensive for larger networks.
- Experimental design: The study compares bound-tightening procedures by computational efficiency, output-bound propagation, and optimization solution time across several ReLU-network experiments.Experiments include randomly generated networks, increasingly challenging quadratic optimization problems, and an oil-production problem with ten surrogate networks.
- Randomly initialized networks: Ten networks with architecture (3, 20, 20, 10, 1) are tested under progressively tighter output bounds from E100=[−1,1] to E0={0}.The input bounds are fixed at B0=[−1,1]3, and average MAD and solution time are reported across the networks.
- Randomly initialized networks: NO-R is the only procedure that significantly reduces average MAD when output bounds are tightened to E0.At E100, output bounds do not tighten preceding units; LRR and RR produce the loosest bounds, while LR, SEMI-LR, and NO-R initially match.
- Randomly initialized networks: NO-R has the highest average bound-tightening time, and its solution time increases as output bounds become tighter, unlike the other procedures.Average solution time generally increases with the number of constraints and rises considerably when binary variables are included.
- Quadratic-function optimization: For quadratic surrogates, LRR performs best for low-dimensional problems with n=1,2,3, while stronger procedures can impose computational overhead.The quadratic functions are likely indefinite and non-separable, and their curvature requires many pieces for accurate piecewise-linear approximation.
- Scaling: For larger networks, interval-based LRR scales well, LP-based procedures scale moderately, and MILP-based procedures become computationally demanding.Subproblem time limits reduce bound-tightening time for larger networks but can produce looser bounds; LR may then compute the tightest bounds among MILP-based procedures.
- Oil-production optimization: In the oil-production problem, tighter bounds substantially affect optimization performance, enabling optimality-gap closure within one hour for selected procedures.For shallow networks, LR(60), NO-R(60), and NO-R close the gap; for deep networks, NO-R(60) and NO-R do so, although NO-R requires much more preprocessing.
6. Concluding remarks
The study shows that ReLU networks can serve as MILP surrogate models, but practical use is currently limited to small networks. Bound-tightening effectiveness depends on the procedure and problem size, while output bounds are exploited only by NO-R among the studied methods.
- Concluding remarks: ReLU networks scale to high-dimensional inputs, train on large noisy datasets, and can be embedded in optimization through a MILP formulation.The formulation enables state-of-the-art MILP solvers to optimize problems containing these networks.
- Concluding remarks: Deep networks can match shallow-network complexity with fewer parameters; riser networks achieved similar accuracy with 1801 versus 2851 parameters.The comparison is presented as an example supporting reduced model complexity through depth.
- Concluding remarks: Bound-tightening efficiency is problem specific: cheaper procedures tend to work best for small embedded networks, whereas more expensive procedures can benefit larger networks.The study ranges from the cheap LRR procedure to the optimal NO-R procedure.
- Concluding remarks: Output bounds can be used for tightening, but among the studied procedures only NO-R exploits them to reduce bounds.The paper reports that ReLU relaxation reduces bound tightness for both forward and backward propagation, with backward propagation less effective.
- Concluding remarks: The MILP formulation is practically limited to small-sized networks, although networks of this size can approximate many interesting nonlinearities and are attractive for process-optimization surrogate modeling.The paper identifies larger-network applicability as an open research direction.
- Future research: Potential extensions include combining tightening procedures, simultaneous multi-bound tightening, stronger formulations and cuts, tree-level tightening, sparsity, and specialized methods for larger networks.These directions are presented as ways to improve tightening efficiency or extend applicability.
Appendix A. Forward- vs backward-propagation of bounds
Forward propagation makes output bounds depend linearly on predecessor bounds, whereas backward propagation requires sufficiently large output-bound changes. For balanced wide layers, backward propagation is therefore weak.
- Forward propagation: For a node y receiving outputs x_i, forward propagation produces bounds [L_f, U_f] from the bounds of its predecessors.The setup assumes ReLU outputs have nonnegative lower bounds, with an equivalent nonnegative-weight presentation.
- Forward propagation: Tightening any predecessor upper or lower bound tightens the corresponding propagated upper or lower bound on y.The dependence is linear in the predecessor bounds.
- Backward propagation: Backward propagation from y to x_j requires a nonnegative induced tightening of x_j’s bound.The upper-bound case uses y ≤ U_f − ΔU, while an analogous condition applies to lower bounds.
- Backward propagation: A relatively large change in y’s bounds is needed for backward propagation to affect preceding nodes, especially when x_j does not dominate y’s relationship with other nodes.The relative-change analysis introduces δ ∈ [0, 1] to characterize this requirement.
- Backward propagation: For balanced nodes, δ = 1/n; with n = 100, the bound on y must be reduced by 99% to affect preceding nodes.Wide layers with many balanced nodes make backward tightening particularly weak.
Appendix B. Statistics for measuring bound tightness
The appendix measures bound quality using mean absolute distance and mean relative distance. MRD is normalized so optimal bounds score 0 and the baseline LRR bounds score 100.
- Bound-quality statistics: Mean absolute distance (MAD) measures the absolute distance of a set of bounds from the reference bounds.The appendix introduces MAD as one statistic for evaluating bound quality.
- Bound-quality statistics: Mean relative distance (MRD) measures relative tightness against the best bounds B⋆ and the suboptimal LRR bounds B−.It provides a normalized comparison between the evaluated bounds and these reference sets.
- Bound-quality statistics: MRD(B, B⋆, B−) = 0 for optimal bounds and 100 for the LRR bounds, with evaluated procedures initialized from B0.Consequently, reported MRD values lie in [0, 100], and zero is assigned when the denominator is zero.
Appendix C. Bound tightening results
Appendix C reports average bound-tightening results across model families, including Q_n, shallow and deep well networks, and shallow and deep riser networks. The reported averages cover ten Q_n models, eight well models, and two riser models.
- Q_n networks: Table C.10 reports average bound-tightening results for Q_n across ten models with n = 1, . . . , 6.The table summarizes results across the indexed Q_n model family.
- Shallow well networks: Table C.11 reports average results for eight shallow well networks with layers (1, 20, 20, 1).The table identifies the network architecture and averaging scope.
- Deep well networks: Table C.12 reports average results for eight deep well networks with layers (1, 10, 10, 10, 10, 1).The table identifies the deeper well-network architecture and averaging scope.
- Shallow riser networks: Table C.13 reports average results for two shallow riser networks with layers (4, 50, 50, 1).The table identifies the shallow riser architecture and averaging scope.
- Deep riser networks: Table C.14 reports average results for two deep riser networks with layers (4, 20, 20, 20, 20, 20, 1).The table identifies the deep riser architecture and averaging scope.