The Proxy Benders Decomposition

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

The Proxy Benders Decomposition

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

The Proxy Benders Decomposition Changkun Guan,1 El Mehdi Er Raqabi,1,2,∗ Mathieu Tanneau,1 Pascal Van Hentenryck1 1

H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA 2

Department of Operations and Decision Systems, Université Laval, Quebec, Canada

arXiv:2606.07403v1 [math.OC] 5 Jun 2026

∗

Corresponding Author: [email protected]

Abstract Benders decomposition is a fundamental framework for solving large-scale mixed-integer optimization problems with complicating variables that, when fixed, yield significantly easier subproblems. However, classical Benders decomposition repeatedly solves highly similar subproblems and often exhibits zigzagging behavior across iterations, leading to slow convergence in large-scale settings. Motivated by the repetitive structure and parametric nature of Benders subproblems, this paper introduces the proxy Benders decomposition (Proxy-BD), a new decomposition framework in which subproblem optimization is replaced by certified optimization proxies rather than repeated exact solves. The proposed proxy follows a self-supervised predict–project–and–complete mechanism that produces dual-feasible solutions for generating provably valid Benders cuts. The framework preserves the theoretical validity of the decomposition independently of prediction quality through a projection-and-completion certification layer. A formal characterization of proxy-induced cuts is established, and the framework naturally extends to modern decomposition schemes, including branch-and-Benders-cut algorithms. Computational experiments on large-scale facility location and network design problems demonstrate that Proxy-BD substantially reduces subproblem computational effort while maintaining near-optimal solution quality. On large-scale uncapacitated facility location instances up to 2000 × 2000, Proxy-BD achieves median optimality gaps below 0.5%, yields up to 161× median speedups, and reduces the number of generated cuts by more than 240× on the largest instances. The computational gains consistently increase with recourse complexity, indicating that proxy-based inference scales substantially more favorably than repeated exact subproblem optimization in large-scale decomposition settings. These results highlight the potential of certified learned inference within decomposition algorithms and position Proxy-BD as a promising direction for scalable, learning-enhanced, and real-time mixed-integer optimization under repeated decision-making settings. Keywords: Benders Decomposition, Optimization Proxy, Decomposition Algorithms, Learningbased Optimization, Large-Scale Optimization, Branch-and-Benders-Cut, Mixed-Integer Optimization

Introduction

Mixed-integer programs (MIPs) frequently exhibit a structure in which a subset of the decision variables makes the problem hard to solve, while the remaining variables define large continuous substructures. This separation naturally suggests the use of decomposition methods. Among them, Benders decomposition (BD) remains one of the most widely used approaches in large-scale settings (Benders, 1962). Consider the mixed-integer optimization problem

min

y∈Y, x∈X

f ⊤y + q⊤x

(1.1)

s.t. Ay + Bx ≥ b, where y ∈ Y ⊆ Zm denotes the complicating variables, and x ∈ X ⊆ Rn+ denotes the continuous recourse variables. Problems of this form arise in a broad range of applications, where fixing y simplifies the constraint system, enabling efficient optimization of the x-variables. For any fixed ȳ, the second-stage recourse subproblem (SP) is n o Q(ȳ) := min q ⊤ x : Bx ≥ b − Aȳ , x∈X

(1.2)

In the standard-form case X = Rn+ , its dual is given by n o Q(ȳ) = max λ⊤ (b − Aȳ) ,

n o D := λ ≥ 0 : B ⊤ λ ≤ q .

λ∈D

(1.3)

Let PD and RD denote the sets of extreme points and extreme rays of the polyhedron D, respectively. The Benders master problem introduces an auxiliary variable θ to represent the second-stage cost Q(y). If the primal subproblem (1.2) is feasible for ȳ, cuts are derived from dual-feasible multipliers: for any λ ∈ D, weak duality implies Q(y) ≥ λ⊤ (b − Ay), and therefore the inequality θ ≥ λ⊤ (b − Ay) 2

(1.4)

is a valid Benders optimality cut. In classical BD, one typically chooses λ as an optimal dual solution for ȳ, which can be taken at an extreme point λ̄ ∈ PD . If the primal subproblem (1.2) is infeasible for ȳ, then, under the standard assumption that D is nonempty, the dual problem (1.3) is unbounded, and there exists an extreme ray r̄ ∈ RD such that r̄⊤ (b − Aȳ) > 0. By Farkas’ Lemma, any y admitting feasible recourse must satisfy the feasibility cut 0 ≥ r̄⊤ (b − Ay).

(1.5)

Substituting the value function Q(y) into (1.1) yields the classical Benders master formulation min f ⊤ y + θ

(1.6)

y,θ

s.t. θ ≥ λ⊤ (b − Ay),

∀λ ∈ PD ,

(1.7)

0 ≥ r⊤ (b − Ay),

∀r ∈ RD ,

(1.8) (1.9)

y ∈ Y.

These constraints, known as Benders optimality and feasibility cuts, are not enumerated explicitly. Instead, they are generated iteratively: at each iteration, the master problem provides a trial solution ȳ to the SP, which is solved to obtain either an optimality cut or a feasibility cut, which is then added to the restricted master problem (RMP). Since the RMP contains only a subset of the cuts, it represents a relaxation of the original problem and provides a lower bound (LB) on its optimal solution. Simultaneously, if the SP is feasible, it generates a feasible solution to the original problem, yielding an upper bound (UB). The Benders algorithm iterates until the difference between the UB and LB falls below a chosen threshold ϵ ≥ 0. Compared to the full MIP formulation, which includes all complicating variables, the SP in BD contains none of these variables, making it much simpler and faster to solve. Due to its broad applicability, the BD has been successfully employed in a wide range of practical problems. These include production routing (Adulyasak et al., 2015), electric vehicle management (Zhang et al., 2021), airline scheduling (Zeighami and Soumis, 2019; Cordeau et al., 2001b), water resources planning (Cai et al., 2001), on-demand delivery systems (Liu and Luo, 2023), hub location

problems (Contreras et al., 2011), locomotive assignment (Cordeau et al., 2001a), the traveling salesman problem (Laporte et al., 1994), vessel service planning (Wu et al., 2022), capacity expansion (Bloom, 1983), budgeting applications (Keshvari Fard et al., 2022), and supply chain planning (Er Raqabi et al., 2023, 2025). Despite its widespread success, the BD can be computationally intensive, exhibits zigzagging patterns, and often converges slowly. While these limitations may be negligible for small- or mediumsized instances, they become critical in large-scale applications. Consequently, significant research efforts have focused on accelerating the Benders convergence. These approaches can be divided into two categories. The first category aims to improve the lower bounds (LBs) provided by the RMP, while the second focuses on enhancing the upper bounds (UBs) obtained from the SP. In the first category, extensive work has been devoted to generating strong or reinforced Benders cuts (Magnanti and Wong, 1981; Codato and Fischetti, 2006; Fischetti et al., 2010; Bodur et al., 2017; Fischetti et al., 2016, 2017; Rahmaniani et al., 2020), which lead to tighter LBs. Additional acceleration strategies include incorporating valid inequalities, warm-starting, careful management of the branchand-bound (B&B) tree, and two-phase solution schemes that first generate cuts from a relaxed RMP before considering integer cuts. For UBs, there is currently no systematic approach to obtaining high-quality UBs from the SP. Existing methods rely primarily on problem-specific heuristics. For example, Boland et al. (2016) combine a proximity search with BD to obtain high-quality, albeit not necessarily optimal, solutions for various stochastic programming problems. There is, then, a practical need for approaches that can quickly generate good primal solutions. A comprehensive review by Rahmaniani et al. (2017) provides an extensive overview of BD applications, challenges, and enhancement strategies. However, despite decades of research on accelerating Benders decomposition, existing approaches still fundamentally rely on repeatedly solving exact subproblems throughout the decomposition process. In classical BD and its modern variants, each SP is solved independently, even though successive SPs often differ only in the right-hand side of (1.2). As a result, a substantial portion of the computational effort is repeatedly spent solving highly similar optimization problems. This structural redundancy suggests that the response of the SP to variations in the master solution may be predictable. This observation motivates a different perspective on decomposition algorithms: rather

than repeatedly solving nearly identical optimization problems, it becomes possible to amortize part of the subproblem computation through learned inference. Recent work has explored the integration of machine learning into two-stage stochastic optimization and Benders-type decomposition algorithms. Patel et al. (2022) approximates the expected recourse function through a neural surrogate that replaces explicit second-stage optimization. While this substantially reduces online solution times, the resulting framework relies on learned valuefunction approximations whose prediction errors directly affect decision quality and are not accompanied by decomposition-level validity guarantees. Larsen et al. (2024) use supervised learning to predict second-stage values and recourse information in continuous and integer L-shaped methods. Their approach replaces expensive recourse evaluations by oracle-trained predictors and accepts small optimality losses in exchange for computational gains. As a consequence, solution quality depends directly on prediction accuracy, and no mechanism enforces the validity of the approximated recourse information. More recently, Li et al. (2025) employ reinforcement learning to adapt the inexactness level of generalized Benders decomposition throughout the optimization process. Learning therefore controls the decomposition algorithm, while subproblem optimization itself remains exact. Similarly, Cai and Yu (2026) learn cut-selection policies that reduce master-problem growth by deciding which Benders cuts to retain. Their framework improves cut management but leaves cut generation unchanged and continues to rely on exact separation. Collectively, these approaches demonstrate that learning can accelerate decomposition through recourse approximation, cut management, or algorithmic control. However, they do not replace the subproblem optimization process itself with a certified learning mechanism. This paper introduces the proxy Benders decomposition (Proxy-BD), a decomposition framework in which subproblem optimization is replaced by certified learned proxies rather than repeated exact solves. Instead of solving each SP from scratch, the proxy directly predicts dual information associated with the current master solution, thereby capturing the parametric response of the SP across iterations. The predicted dual information is then transformed into provably valid Benders cuts through a predict–project–and–complete certification mechanism. By exploiting the repetitive structure of the SPs, Proxy-BD amortizes the computational cost of repeated subproblem optimization while preserving the theoretical validity of the decomposition. The proposed frame-

work is further motivated by the growing interest in optimization proxies for repeated and nested optimization tasks (Park and Van Hentenryck, 2023; Tanneau and Van Hentenryck, 2024). The contributions of this paper are fourfold: • Proxy-BD Framework. Proxy-BD is introduced, a decomposition framework in which each subproblem solve is replaced by a predict–project–and–complete certification layer that produces provably valid Benders cuts through certified dual inference. By learning the parametric response of the subproblem to variations in the master solution, Proxy-BD amortizes repeated optimization effort. The framework unifies both optimality and feasibility cut generation within the same certification architecture. • Certification Mechanism. A projection-and-completion certification mechanism is established that preserves the theoretical validity of the decomposition independently of prediction quality. For feasibility cuts, the paper introduces a slice-normalized reformulation of Farkas certificates that converts the unbounded feasibility cone into a bounded learnable domain while preserving the extreme-ray structure of classical Benders feasibility cuts. A formal characterization of proxy-induced cuts is provided, and the resulting framework naturally extends to modern decomposition schemes, including branch-and-Benders-cut (B&BC) algorithms, cut aggregation strategies, and accelerated Benders variants. The certification layer converts arbitrary proxy outputs into dual-feasible certificates, ensuring that learning affects cut strength rather than cut validity while maintaining compatibility with modern decomposition pipelines. • Self-supervised Learning. Unlike supervised approaches requiring optimal dual labels, Proxy-BD is trained through a self-supervised objective that maximizes certified dual bounds without requiring optimal dual solutions. This design avoids the ambiguity induced by dual degeneracy, where multiple dual-optimal certificates may generate identical Benders cuts, and aligns learning directly with cut strength rather than dual prediction accuracy. The framework leverages historical optimization information across iterations and instances, enabling knowledge reuse throughout the decomposition process and supporting repeated or real-time optimization settings under evolving data. • Computational Results. Computational experiments on large-scale facility location and network design problems demonstrate that Proxy-BD attains near-optimal solutions while 6

achieving up to 161× median speedups and reducing the number of generated cuts by more than 240× against classical and accelerated Benders schemes. The computational gains consistently increase with recourse complexity, indicating it scales well to large instances where exact subproblem optimization becomes the dominant bottleneck. Moreover, the substantially smaller number of generated cuts suggests an implicit stabilization effect that may reduce the zigzagging behavior commonly observed in classical Benders decomposition. The remainder of the paper is organized as follows. Section 2 establishes the proxy optimality cuts. Section 3 handles subproblem infeasibility via slice-normalized Farkas certificates. Section 4 presents the proxy-BD framework. Section 5 and 6 present the experimental design and the computational results, respectively. Section 7 concludes with a discussion of implications and directions for future research.

Proxy Optimality Cuts

Consider the two-stage MIP (1.1) and its recourse value function Q(·) defined in (1.2). This section first focuses on the complete-recourse setting, where the recourse problem is feasible and bounded for every ȳ ∈ Y , so that Benders decomposition generates only optimality cuts. In this setting, the optimization proxy is built around three components: (i) a predict–project–and–complete mechanism that converts predicted multipliers into dual-feasible solutions at each RMP solution, (ii) structural completion procedures that are closed-form for many common recourse models, and (iii) a self-supervised training objective that maximizes certified dual bounds and backpropagates completion subgradients, eliminating the need for optimal dual labels required by standard supervised approaches. Notation. For a scalar a ∈ R, define (a)+ := max{a, 0}. For a vector v, (v)+ is applied com ponentwise: (v)+ := max{vi , 0} i . Equivalently, (v)+ is the Euclidean projection of v onto the nonnegative orthant.

2.1

Predict–Project–and–Complete

By separating and re-organizing constraints, the MIP (1.1) can be rewritten as:

min

y∈Y, x∈X

f ⊤y + q⊤x

(2.1)

s.t. Ay + Bx ≥ b, Gx ≥ g, where Gx ≥ g are y-independent structure constraints. Define d(y) := b − Ay and consider the recourse LP Q(ȳ) := min q ⊤ x : Bx ≥ d(ȳ), Gx ≥ g .

(2.2)

max d(ȳ)⊤ λ + g ⊤ µ

(2.3)

x≥0

Its dual is

λ,µ

s.t. B ⊤ λ + G⊤ µ ≤ q, λ ≥ 0, µ ≥ 0.

Any dual-feasible pair (λ, µ) yields the valid Benders optimality cut θ ≥ d(y)⊤ λ + g ⊤ µ = α(λ, µ) + β(λ)⊤ y,

(2.4)

with coefficients α(λ, µ) := b⊤ λ + g ⊤ µ and β(λ) := −A⊤ λ. The slope β(λ) = −A⊤ λ depends only on λ, while µ enters only the intercept α. The linking-row multipliers therefore govern the cut geometry in the master space, while µ adjusts the intercept to the strongest value compatible with a fixed λ. The predict–project–complete pipeline below mirrors this asymmetry, letting the network learn λ and recovering the optimal µ for any fixed λ via linear-programming duality. Predict–and–Project. Given a solution ȳ from the RMP, the proxy predicts λ̃ ∈ Rnλ , where nλ denotes the number of predicted constraints associated with Bx ≥ d(ȳ). The predicted multiplier is then projected onto the nonnegative orthant: λ̂ := (λ̃)+ ∈ Rn+λ . Complete. Since λ̂ ≥ 0 alone does not ensure dual feasibility, λ̂ is completed by solving the 8

strongest-completion LP in µ as follows. Given a projected multiplier λ̂ ≥ 0, the remaining dual multiplier µ is recovered by solving n o µ̂(λ̂) ∈ arg max g ⊤ µ : G⊤ µ ≤ q − B ⊤ λ̂ . µ≥0

(2.5)

Any feasible µ̂(λ̂) makes (λ̂, µ̂) dual-feasible for (2.3). The next proposition shows that choosing an optimizer yields the strongest bound among all dual-feasible completions of the fixed λ̂. Assumption 1. For every projected multiplier λ̂ ≥ 0, the completion LP (2.5) is feasible and bounded. Theorem 1. Under Assumption 1, for any predicted output λ̃, there exists a completion µ̂(λ̂) solving (2.5) such that (λ̂, µ̂(λ̂)) is dual-feasible for (2.3). Consequently, the cut θ ≥ d(y)⊤ λ̂ + g ⊤ µ̂(λ̂) is valid for all y. Proof. Fix any predicted output λ̃ ∈ Rnλ and let λ̂ = (λ̃)+ ≥ 0. By Assumption 1, the completion LP (2.5) is feasible and bounded, and therefore admits an optimal solution. Let µ̂(λ̂) be any optimizer. Then µ̂(λ̂) ≥ 0 and satisfies G⊤ µ̂(λ̂) ≤ q − B ⊤ λ̂, hence B ⊤ λ̂ + G⊤ µ̂(λ̂) ≤ q. Therefore (λ̂, µ̂(λ̂)) is dual-feasible for (2.3). Finally, weak duality between the primal recourse LP (2.2) and its dual (2.3) implies d(y)⊤ λ̂ + g ⊤ µ̂(λ̂) ≤ Q(y) for all y, which proves that the cut θ ≥ d(y)⊤ λ̂ + g ⊤ µ̂(λ̂) is valid. Theorem 2. Fix ȳ and a projected multiplier λ̂ ≥ 0. Any optimizer µ⋆ (λ̂) of (2.5) maximizes g ⊤ µ among all µ ≥ 0 satisfying G⊤ µ ≤ q − B ⊤ λ̂, and therefore maximizes the cut right-hand side d(ȳ)⊤ λ̂ + g ⊤ µ among all dual-feasible completions of λ̂. Proof. Fix λ̂ ≥ 0 and define the completion feasible region M(λ̂) := {µ ≥ 0 : G⊤ µ ≤ q − B ⊤ λ̂}. Problem (2.5) is exactly max{g ⊤ µ : µ ∈ M(λ̂)}, so any optimizer maximizes g ⊤ µ over all dualfeasible completions. Since d(ȳ)⊤ λ̂ is constant in µ, maximizing g ⊤ µ also maximizes the cut righthand side d(ȳ)⊤ λ̂ + g ⊤ µ among all completions of the same λ̂. Assumption 1 makes the completion map well-defined for all projected multipliers. Theorems 1 and 2 formalize that predict–project–and–complete always yields a valid Benders optimality cut that is strongest among all dual-feasible completions of a fixed projected multiplier. 9

Remark 1 (Choice of the predicted block). Partitioning the system into predicted-and-projected rows (Bx ≥ d(ȳ)) and completed rows (Gx ≥ g) is a flexible modeling choice rather than a rigid restriction. Generally, the recourse dual can be split into any two blocks where the network predicts one and the completion problem recovers the other. Furthermore, either block can feature a ydependent right-hand side. When completed rows depend on y, their corresponding dual multipliers contribute directly to the cut slope β, rather than just the constant α. This specific configuration is illustrated in the facility-location derivation in Appendix B, where the network predicts the demand multipliers, and the completion step recovers the y-dependent capacity and bound multipliers that shape β. Ultimately, while the choice of partition heavily influences computational tractability and completion efficiency, it never compromises the validity of the resulting Benders cuts, which remains guaranteed by weak duality and Theorem 1.

2.2

Closed-form Completion

The completion step (2.5) generally requires solving an LP. However, many recourse models arising in practice involve bounded resources, such as capacity-constrained flows, inventories with storage limits, production with rate limits, and assignment fractions in [0, 1]. In these settings, the completion map often admits a closed-form solution, similarly to the DLL-style completion framework of Tanneau and Van Hentenryck (2024). Consider the bounded recourse problem Q(ȳ) := min q ⊤ x : Bx ≥ d(ȳ), l ≤ x ≤ u , x

(2.6)

where l < u are finite componentwise bounds. A dual form introduces bound multipliers z l , z u ≥ 0 with coupling constraint B ⊤ λ + z l − z u = q. For any projected λ ≥ 0, the optimal completion is closed-form: z l = (q − B ⊤ λ)+ ,

z u = (B ⊤ λ − q)+ .

(2.7)

Thus, in bounded settings, enforcing feasibility reduces to elementwise operations. The closed-form completion is illustrated in Example 1. Remark 2. The choice of which dual multipliers to predict can be guided by the property that the

remaining dual variables admit a closed-form completion. In this way, the proxy can efficiently produce the strongest feasible completion associated with the predicted multiplier without solving an additional LP. This closed-form property is central to computational efficiency and enables end-toend gradient-based self-supervised training through the completion map. Example 1. Consider the capacitated facility location problem (CFLP) in (2.8). Using the scaling xij ∈ [0, 1] for the fraction of client demand di served by facility j, CFLP can be written compactly as

min

            X

X fj yj +

  j           where Y := {y ∈ {0, 1}n :

xij ≥ 1

di cij xij :

di xij ≤ sj yj

0 ≤ xij ≤ yj y ∈ Y, j=1 sj yj ≥

(2.8)

     ∀i, j,      

i,j

  ∀i,           ∀j, 

i=1 di },.

In a classical Benders master for CFLP, let θ P be a scalar that represents the second-stage assignment cost and solve min{ j fj yj + θ : y ∈ Y, θ ∈ R, Benders cuts}. Benders uses optimality cuts of the form θ ≥ α(t) + β (t)

⊤

(2.9)

t = 1, 2, . . . , T

where t indexes the cut-generation iteration. Predict–and–Project. Let λi ≥ 0 denote multipliers for the client constraints

j xij ≥ 1.

The

proxy predicts λ̃ and projects to λ̂ = (λ̃)+ . Complete. For a fixed projected λ̂ ≥ 0, the strongest completion decomposes by facility. For facility j, define the continuous knapsack value ( ) X X κj (λ) := max (λi − di cij )ai : 0 ≤ ai ≤ 1, di ai ≤ sj . i

(2.10)

This is finite and attained for all λ ≥ 0 because the feasible set is a compact polytope. It admits a closed-form completion: discard items with λi − di cij ≤ 0, sort the remainder by decreasing profitto-weight ratio, and fill capacity until exhausted. The resulting knapsack-lifted cut coefficients for

the θ-master are

α(λ̂) =

λ̂i ,

βj (λ̂) = −κj (λ̂),

θ ≥ α(λ̂) +

(2.11)

βj (λ̂)yj .

Equivalently, writing the cut in terms of the total-objective epigraph variable η := θ +

η≥

X i

λ̂i +

j fj yj yields

fj − κj (λ̂) yj .

Thus, for the CFLP above, the completion map is closed-form, inexpensive, and yields the strongest completion value for each predicted multiplier λ̃.

Proxy Feasibility Cuts

This section considers the case where the subproblem is infeasible at a trial solution ȳ. In such a case, Benders decomposition produces a feasibility cut that separates ȳ while remaining valid for all feasible y. The primary challenge in learning feasibility certificates is scale invariance. Classical Farkas certificates live in an unbounded cone and are defined only up to scaling. To resolve this, a slicenormalized reformulation bounds the certificate set using a single linear constraint. Consequently, generating the proxy feasibility cut relies on the same predict-project-and-complete approach as the proxy optimality cut (Section 2), requiring exactly one additional bounded constraint during the projection step.

3.1

Slice Normalization

For a candidate first-stage solution ȳ, the recourse feasibility system is

∃ x ≥ 0 : Bx ≥ d(ȳ),

(F)

with d(y) := b − Ay as in (2.2). When (F) is infeasible, classical Benders derives a feasibility cut from a Farkas certificate, i.e., an extreme ray of the dual cone R := {λ ≥ 0 : B ⊤ λ ≤ 0}. Rays are scale invariant, so a normalization must be chosen to anchor the certificate. Let t ≥ 0 be a scalar

slack and consider the uniform-relaxation problem t⋆ (ȳ) :=

min

x≥0, t≥0

s.t. Bx + t e ≥ d(ȳ),

(Primal-slice)

where e is the all-ones vector. The dual of (Primal-slice) is max d(ȳ)⊤ λ λ

s.t. B ⊤ λ ≤ 0,

λ ≥ 0,

e⊤ λ ≤ 1,

(Dual-slice)

which optimizes over a bounded slice of the Farkas cone R. Theorem 3. The system (F) is feasible if and only if t⋆ (ȳ) = 0. Moreover, if t⋆ (ȳ) > 0, then any dual optimizer λ⋆ of (Dual-slice) satisfies e⊤ λ⋆ = 1 and yields the valid Benders feasibility cut (b − Ay)⊤ λ⋆ ≤ 0,

(3.1)

which separates ȳ. Proof. The equivalence t⋆ (ȳ) = 0 ⇔ (F) is immediate: t = 0 is feasible for (Primal-slice) exactly when there exists x ≥ 0 such that Bx ≥ d(ȳ). For t⋆ (ȳ) > 0, the primal is feasible and the dual has a nonempty, bounded feasible region, so strong duality holds and t⋆ (ȳ) = d(ȳ)⊤ λ⋆ > 0 at any dual optimizer. Complementary slackness on the uniform slack variable t gives t⋆ (ȳ)(1 − e⊤ λ⋆ ) = 0, hence e⊤ λ⋆ = 1. Validity of (3.1) follows from λ⋆ ∈ R and weak duality. Separation follows from (b − Aȳ)⊤ λ⋆ = t⋆ (ȳ) > 0. Lemma 1. When t⋆ (ȳ) > 0, every optimal solution of (Dual-slice) saturates e⊤ λ = 1 and can be chosen at an extreme point of the slice Se := {λ : λ ≥ 0, B ⊤ λ ≤ 0, e⊤ λ = 1}, which corresponds, up to scaling, to an extreme ray of the Farkas cone R. Proof. Since λ ≥ 0, every nonzero λ ∈ R satisfies e⊤ λ > 0. Let t⋆ (ȳ) > 0 and let λ⋆ be optimal for (Dual-slice). If e⊤ λ⋆ < 1, then λ̃ := λ⋆ /(e⊤ λ⋆ ) remains feasible (since R is a cone) and satisfies

e⊤ λ̃ = 1, with d(ȳ)⊤ λ̃ > d(ȳ)⊤ λ⋆ , contradicting optimality. Hence e⊤ λ⋆ = 1. Let r generate an extreme ray of R and define λ := r/(e⊤ r) ∈ Se . If λ = αλ1 + (1 − α)λ2 with λ1 , λ2 ∈ Se and α ∈ (0, 1), then r = α(e⊤ r)λ1 +(1−α)(e⊤ r)λ2 with both terms in R; extremality of the ray forces λ1 and λ2 colinear with r, and the normalization e⊤ λ1 = e⊤ λ2 = 1 forces λ1 = λ2 = λ, so λ is an extreme point. Conversely, if λ ∈ Se is an extreme point but not on an extreme ray of R, write λ = u1 + u2 for nonzero, non-colinear u1 , u2 ∈ R; setting αi := e⊤ ui and λi := ui /αi ∈ Se gives λ = α1 λ1 + α2 λ2 with α1 + α2 = 1, a nontrivial convex combination of two distinct points in Se , contradicting extremality.

3.2

Predict–Project–and–Complete Pipeline

The slice-normalized certificate set in (Dual-slice) is bounded. This makes the certificate-generation problem structurally similar to the optimality case in Section 2, and allows the same proxy design to apply, with a single additional bounded constraint in the projection step. To match the LP-recourse setting used elsewhere in the paper, assume the recourse set also contains y-independent structure constraints Gx ≥ g in addition to x ≥ 0, and that set {x ≥ 0 : Gx ≥ g} is nonempty. A slice-normalized reformulation is then

F (ȳ) :=

min

x≥0, t≥0

n o t : Bx + t e ≥ d(ȳ), Gx ≥ g ,

which is always feasible and satisfies the augmented-recourse equivalence “∃ x ≥ 0 :

(3.2)

Bx ≥

d(ȳ), Gx ≥ g” holds at ȳ ⇔ F (ȳ) = 0. This is the extension of Theorem 3 to the augmented slice, proved by the same complementary-slackness argument on the uniform slack t. The Gx ≥ g block is carried unchanged and does not affect the t = 0 characterization. The dual of (3.2) is max d(ȳ)⊤ λ + g ⊤ µ λ,µ

s.t. B ⊤ λ + G⊤ µ ≤ 0, λ ≥ 0, µ ≥ 0, e⊤ λ ≤ 1.

(3.3)

Any dual-feasible (λ, µ) yields the valid feasibility inequality 0 ≥ d(y)⊤ λ + g ⊤ µ.

(3.4)

The scalar certified value of the slice-Farkas certificate at ȳ is Lfeas (ξ, ȳ) := d(ȳ)⊤ λ̂ + g ⊤ µ̂,

(3.5)

which lower-bounds F (ȳ) by weak duality. Moreover, if Lfeas (ξ, ȳ) > 0, then F (ȳ) > 0 and the recourse is infeasible at ȳ (formalized as Proposition 2 below). Denote by V1 (B) :=

λ ≥ 0 : B ⊤ λ ≤ 0, e⊤ λ ≤ 1

(3.6)

the slice of the Farkas cone used as the projection target for the predicted multiplier. For each λ̂ ∈ V1 (B), the feasibility-mode completion in µ is the LP µ̂(λ̂) ∈ arg max g ⊤ µ : G⊤ µ ≤ −B ⊤ λ̂ . µ≥0

(3.7)

Assumption 2. For every λ̂ ∈ V1 (B), the feasibility completion LP (3.7) is feasible and attains an optimum. This holds whenever the y-independent recourse set {x ≥ 0 : Gx ≥ g} is nonempty: since λ̂ ∈ V1 (B) gives −B ⊤ λ̂ ≥ 0, the point µ = 0 is feasible for (3.7), and by LP duality the completion LP is bounded above precisely when {x ≥ 0 : Gx ≥ g} ̸= ∅, e.g., the CFLP formulation (2.8). Theorem 4. Under Assumption 2, for any network output λ̃ the projected multiplier λ̂ = ΠV1 (B) (λ̃) admits a completion µ̂ given by (3.7), and the pair (λ̂, µ̂) is dual-feasible for (3.3). Proof. By construction of the projection, λ̂ ∈ V1 (B), so λ̂ ≥ 0, B ⊤ λ̂ ≤ 0, and e⊤ λ̂ ≤ 1. By Assumption 2, problem (3.7) attains an optimum µ̂ ≥ 0 satisfying G⊤ µ̂ ≤ −B ⊤ λ̂. Rearranging gives B ⊤ λ̂ + G⊤ µ̂ ≤ 0, which together with the slice normalization is exactly the dual-feasibility region of (3.3). Theorem 5. For any fixed λ̂ ∈ V1 (B), every optimizer µ̂ of (3.7) maximizes the certificate value 15

d(ȳ)⊤ λ̂ + g ⊤ µ̂ among all dual-feasible completions of λ̂ for (3.3). Proof. The objective g ⊤ µ is linear and d(ȳ)⊤ λ̂ is constant in µ, so any arg max over the completion set in (3.7) also maximizes d(ȳ)⊤ λ̂ + g ⊤ µ. Comparing (3.3) with the proxy optimality dual (2.3) in Section 2, the structure is the same: a nonnegative multiplier µ coupled to λ through a linear inequality, and a linear objective that becomes the cut’s certified bound. The only new feature is the additional slice-normalization constraint e⊤ λ ≤ 1, which removes the scale ambiguity of ray certificates. Therefore, feasibility-cut learning uses the same building blocks as the proxy optimality cuts: the proxy predicts λ̃, the projection enforces λ̂ = ΠV1 (B) (λ̃), and the completion in µ proceeds via (3.7). Validity of the resulting cut is then a direct consequence of weak duality and Theorem 4: Proposition 1. Let (λ̂, µ̂) be any dual-feasible pair for (3.3). Then the feasibility inequality (3.4) is valid for every y whose recourse (F) is feasible. Proof. If recourse is feasible at y then F (y) = 0 in (3.2). Weak duality between (3.2) and (3.3) gives d(y)⊤ λ̂ + g ⊤ µ̂ ≤ F (y) = 0, which is exactly (3.4). Proposition 1 guarantees the emitted cut is never violated by a recourse-feasible y. The converse direction, i.e., that a positive certified value certifies recourse infeasibility, is the one-sided guarantee of the slice-Farkas certificate. Proposition 2. If Lfeas (ξ, ȳ) > 0 at (3.5), then the recourse problem (2.2) is infeasible at ȳ. The converse does not hold: a nonpositive certificate value does not certify feasibility. Proof. Let (λ̂, µ̂) be dual-feasible for (3.3). By weak duality, Lfeas (ξ, ȳ) = d(ȳ)⊤ λ̂ + g ⊤ µ̂ ≤ F (ȳ). If Lfeas > 0 then F (ȳ) > 0, by the augmented-recourse equivalence established below (3.2) (the extension of Theorem 3 to the Gx ≥ g block), F (ȳ) > 0 iff the recourse (2.2) is infeasible at ȳ. The non-converse follows since a particular dual-feasible certificate can be too weak to attain F (ȳ). Example 2. Take m = 2, B = −I2 , and X = R2+ . The recourse-feasible cone in the right-hand-side space is K = {d ∈ R2 : d1 ≤ 0, d2 ≤ 0}, 16

λ2 R

d2 d1 ≤ 0

⊤ λ

= 1

d(ȳ) = (1, 12 )

λ1

d = (1, −2)

(a) d-space.

slice

= (1, 0)

(b) λ-space.

Figure 1: Slice-normalized geometry: the slice certificate λslice = (1, 0) maximizes d(ȳ)⊤ λ over {λ ≥ 0, e⊤ λ ≤ 1} (right) and induces the facet cut d1 ≤ 0 separating the infeasible d = (1, −2) from K (left). whose facet inequalities are d1 ≤ 0 and d2 ≤ 0. The certificate cone is R = {λ ≥ 0, B ⊤ λ ≤ 0} = R2+ . Under slice normalization, the proxy optimizes over Se = {λ ∈ R : e⊤ λ ≤ 1}. For d(ȳ) = (1, 12 ), Lemma 1 implies that an optimal certificate can be chosen at an extreme point of Se , equivalently, on an extreme ray of R. The unique optimizer here is λslice = (1, 0), and the induced feasibility cut is d(y)⊤ λslice ≤ 0

⇐⇒

d1 (y) ≤ 0,

which is exactly a facet of K. Figure 1 shows this certificate in λ-space and the corresponding facet cut in d-space. The slice constraint e⊤ λ ≤ 1 removes the scaling ambiguity of ray certificates, lets the proxy target a bounded certificate set, and makes the separation value d(ȳ)⊤ λ comparable across instances and RMP solutions. More generally, one may normalize with another positive linear functional r⊤ λ ≤ 1. Appendix A discusses box normalization as a contrasting alternative under which the optimizer may yield a valid but non-facet cut.

3.3

Deployment repair

The proxy’s slice-Farkas cut (3.4) can be shallow at ȳ when the predicted λ̂ under-prices the recourse, so the master can converge at an incumbent that is not strictly feasible for the original problem. When a strictly feasible design is required, a problem-specific repair procedure is applied to the returned design. The repair strategy depends on the structure of the problem: when feasibility is monotone in the design variables (e.g., as in network design where opening more arcs improves feasibility), a greedy procedure guided by the proxy’s dual prices can restore feasibility. The repair is therefore optional and problem-specific, invoked only when an exactly feasible design must be returned. At each separation invocation, the feasibility certificate (3.5) is evaluated first. If Lfeas (ξ, ȳ) > 0, the associated slice-Farkas inequality (3.4) is emitted (the recourse is infeasible at ȳ by Proposition 2), otherwise, the optimality certificate is evaluated, and the optimality cut (2.4) is added when violated. No recourse LP is solved during proxy deployment. An exact solve is invoked only afterward, outside the timed comparison, to compute the true optimality gap.

The Proxy Benders Decomposition Framework

Sections 2 and 3 established the predict–project–and–complete layer for generating proxy optimality cuts and, when the recourse can be infeasible, proxy feasibility cuts via the slice-normalized reformulation. This section presents the Proxy-BD framework: an optimization proxy that replaces repeated exact Benders subproblem optimization by a forward pass through a certification layer, producing provably valid Benders cuts without requiring exact subproblem separation during deployment. Although Proxy-BD is first introduced within the classical Benders framework to isolate and analyze the proxy separation mechanism, its main motivation is modern large-scale decomposition schemes such as B&BC algorithms, where subproblem separation is repeatedly invoked throughout the branch-and-bound tree (Moreno et al., 2019; Satici and Dayarian, 2026). In such settings, the cumulative cost of exact recourse solves becomes substantial, making amortized proxy inference particularly advantageous. This section proceeds as follows. Section 4.1 presents the self-supervised training framework. Sec-

tion 4.2 describes the unified proxy architecture that handles both optimality and feasibility cases. Sections 4.2.1 and 4.2.2 present the offline training pipeline and the online deployment procedure, respectively. Section 4.3 highlights theoretical guarantees that ensure every proxy-generated cut is valid.

4.1

Self-supervised Learning

Self-supervised learning is a central component of Proxy-BD. Unlike supervised learning, which would require optimal dual labels λ⋆ , Proxy-BD is trained by maximizing a certified dual bound. This choice is motivated by the fact that the objective of Proxy-BD is not to recover a particular optimal dual solution, but to generate strong Benders cuts. Furthermore, since Benders subproblems are often dual-degenerate, multiple dual-optimal certificates may generate identical cuts, making dual vectors ambiguous supervision targets. A supervised loss would therefore optimize dual imitation rather than decomposition performance. A Benders state is defined as the pair (ξ, ȳ), where ξ denotes the instance data features encoding (A, B, G, b, g, q) and ȳ is the current master solution at which the algorithm attempts to generate a violated cut. During training, oracle Benders runs are used only to generate representative Benders states (ξ, ȳ) and not to provide dual supervision labels. The certification layer returns a dual-feasible pair (λ̂, µ̂) and the certified scalar value L(ξ, ȳ) := d(ȳ)⊤ λ̂ + g ⊤ µ̂,

(4.1)

which coincides with L in (4.6). By weak duality, L(ξ, ȳ) is the right-hand side of the certified Benders cut generated by the proxy. Consequently, maximizing L directly maximizes the strength of the generated cuts. The self-supervised objective therefore optimizes the quantity that drives decomposition performance, rather than the recovery of a specific dual certificate. The combined training objective is given in (4.8). The completion problem (2.5) admits the primal representation

min

x≥0, Gx≥g

(q − B ⊤ λ̂)⊤ x.

The certified value L is concave in λ̂, as it is the optimal value of a linear program whose objective

coefficients depend affinely on λ̂. Let x̂ denote an optimizer of the completion primal. Then a supergradient of L with respect to the projected multiplier is ∂ + L(ξ, ȳ) ∋ d(ȳ) − B x̂, λ̂

(4.2)

i.e., the residual of the linking constraints evaluated at the completion solution; equivalently, B x̂ − d(ȳ) is a subgradient of the convex training loss −L. This is the dual-ascent mechanism emphasized by DLL (Tanneau and Van Hentenryck, 2024): training network parameters to yield larger certified values, even when no dual-optimal labels are provided. At inference time, no parameter updates are performed. Given ȳ, the network is evaluated, projection and, when needed, completion are applied, and the resulting certified optimality cut is added to the master.

4.2

Proxy Architecture

Proxy-BD consists of three interconnected components: (i) an inference module that maps a Benders state (ξ, ȳ) to a partial dual prediction, (ii) a certification layer that transforms the prediction into a dual-feasible certificate through projection and completion, and (iii) a deployment procedure that integrates certified cuts into a Benders decomposition framework. The certification mechanisms for optimality and feasibility cuts were established in Sections 2 and 3. The present section focuses on how these components interact during training and deployment. Predict. The proxy network maps a Benders state to a partial dual prediction: λ̃ = gθ (ξ, ȳ) ∈ Rnλ .

(4.3)

Project. The prediction is projected onto the nonnegative orthant:

λ̂ = Π{λ≥0} (λ̃) = (λ̃)+ ,

(4.4)

Stage 1

Stage 2

Training instances

Predict λ̃ = gθ (ξ, ŷ)

Benders states S = {(ξ, ȳ)}

Oracle Benders

Project λ̂ + Complete µ̂

Certified value L(ξ, ŷ)

Feature extraction & normalization

SGD update ∇θ L

Trained Proxy gθ⋆

repeat for each mini-batch / epoch

Figure 2: Offline pipeline for Proxy-BD. Stage 1: Oracle Benders is run on training instances to collect states (ξ, ȳ). Stage 2: the proxy is trained self-supervised by minimizing L(θ) in (4.8), with gradients flowing through the completion map via (4.2). Complete. The remaining dual variables are recovered through the completion problem: µ̂(λ̂) ∈ arg max g ⊤ µ : G⊤ µ ≤ q − B ⊤ λ̂ ,

(4.5)

µ≥0

which is often available in closed form for structured recourse models (see Example 1). Certification. The certification layer returns the certified scalar value L(ξ, ȳ) = d(ȳ)⊤ λ̂ + g ⊤ µ̂,

(4.6)

where d(ȳ) := b − Aȳ. The resulting cut coefficients are α = b⊤ λ̂ + g ⊤ µ̂,

β = −A⊤ λ̂,

(4.7)

defining the optimality cut θ ≥ α + β ⊤ y. Proxy-BD operates through two phases: an offline phase that generates Benders states and trains the proxy through self-supervised learning, and an online phase that uses the trained proxy to generate cuts inside Benders decomposition.

4.2.1

Offline Phase

The offline phase produces a trained proxy gθ⋆ . It consists of two stages (see Figure 2). Stage 1: State Generation. An oracle Benders procedure with exact subproblem separation is (t)

(t)

run on each training instance to collect Benders states {(ξn , ȳn )}, where ȳn is the separation point 21

at iteration t. These states form the dataset S. Stage 2: Self-supervised Training. The proxy parameters θ are optimized by maximizing the certified dual bound over S. The self-supervised training maximizes certified bounds over the collected Benders states, encouraging the proxy to generate strong dual certificates throughout the decomposition process. The loss takes the general form: L(θ) = E(ξ,ȳ)∈S ℓ(ξ, ȳ; θ) ,

(4.8)

where ℓ promotes strong certified cuts over the distribution of Benders states encountered during training. The loss is defined through the optimality certificate L. The specific loss formulations address problem-specific challenges, such as invariances, and are detailed in the appendices. The training is self-supervised in that no optimal dual solutions are required. The proxy learns to generate strong cuts using only the completion’s certificate value and gradient. The gradient signal comes from the completion subgradient ∂ + Lθ ∋ d(ȳ) − B x̂ (cf. (4.2)), which flows through λ̂

the projection layer and into the network parameters via backpropagation.

4.2.2

Online Phase

At deployment, the trained proxy is queried in place of each exact subproblem solve within a classical outer-loop Benders framework. At each iteration t: 1. Solve the RMP to obtain (ȳ (t) , θ̄(t) ). 2. Evaluate the proxy at the solution ȳ (t) using predict–project–and–complete in (4.3)–(4.5). 3. Form the certified cut coefficients (4.7). 4. If the cut is violated at (ȳ (t) , θ̄(t) ), add it to the RMP and go to Step 1. Otherwise, terminate. Figure 3 illustrates Proxy-BD within a classical outer-loop Benders framework, where the restricted master problem and the proxy alternate. In modern decomposition frameworks such as B&BC algorithms, the same Proxy-BD deployment mechanism is invoked repeatedly at nodes of the branch-and-bound tree, replacing repeated exact recourse optimization with amortized proxy inference. Figure 4 illustrates this setup. 22

Yes: add cut to RMP

Initialize RMP (y, θ)

Instance ξ + Proxy gθ⋆

Solve RMP (ȳ (t) , θ̄(t) )

Predict–Project –and–Complete

Certified cut (α(t) , β (t) )

Cut violated?

Proxy fixed point y ⋆ = ȳ (t)

Figure 3: Online Proxy-BD loop. At each iteration, the RMP is solved, and the proxy generates a certified cut via predict–project–complete. The loop terminates at a proxy fixed point (Definition 1). Proxy Master MIP (branch and bound)

ck lba cal

f at

n tio rac

ȳ

Predict λ̃ = gθ (ξ, ȳ)

Project onto dual-feasible region

Complete closed-form completion

int eg

er ȳ

root

y1 =1

Optimality cut θ ≥ α + β⊤y

Feasibility cut 0 ≥ α + β⊤y

(recourse feasible)

(slice-Farkas certificate)

ca ll

y1 =0

fath.

open

Violated at ȳ?

No: return to B&B continue search

Yes: add cut to master B&B node

Figure 4: Online B&BC Proxy-BD loop. The master MIP is solved once. The proxy is invoked as a separation callback at selected fractional or integer nodes. If the certified cut is violated, it is added to the current B&B node; otherwise, control returns to the branch-and-bound search.

4.3

Theoretical Guarantees

Sections 2 and 3 established the local certification properties of the predict–project–and–complete mechanism, including the existence of dual-feasible completions, strongest-completion optimality for fixed projected multipliers, and construction of certified dual inequalities. This section interprets these properties at the framework level and studies their implications for Proxy-BD deployment. The following proposition establishes that every proxy-generated inequality defines a valid Benders cut. Proposition 3. Every dual-feasible pair (λ̂, µ̂) returned by the certification layer defines a valid

Benders optimality cut. Proof. Fix any y for which the recourse LP (2.2) is feasible and bounded with optimal value Q(y), and let (λ̂, µ̂) be any dual-feasible pair for (2.3). By weak duality between (2.2) and (2.3), d(y)⊤ λ̂ + g ⊤ µ̂ ≤ Q(y). Using d(y) = b − Ay and the definitions (4.7), this is equivalent to Q(y) ≥ α + β ⊤ y, so θ ≥ α + β ⊤ y is a valid Benders optimality cut. Proposition 3 holds for any network parameters θ, i.e., before, during, and after training. The projection–completion pipeline is the structural mechanism that converts arbitrary neural outputs into provably valid cuts. Training controls only how strong those cuts are. With validity established, it is now possible to characterize the termination behavior of the online Proxy-BD loop (Section 4.2.2). Definition 1. A master solution (ȳ ⋆ , θ̄⋆ ) is called a proxy fixed point if no proxy-generated cut is violated at (ȳ ⋆ , θ̄⋆ ). Since the proxy only approximates the oracle, a proxy fixed point is generally not a global optimum of the original problem. The following remark clarifies the relationship between conditional completion optimality and global dual optimality. Remark 3. Theorem 2 guarantees that, for a fixed projected λ̂, the completion µ̂⋆ (λ̂) yields the strongest dual-feasible completion associated with λ̂. However, this optimality is conditional on the projected multiplier λ̂, since the overall dual problem jointly optimizes over (λ, µ). The proxy cut matches an oracle optimality cut when (λ̂, µ̂) is an optimal dual solution of (2.3); dual nonuniqueness means many such λ̂ can yield the same cut. The gap between the proxy bound and Q(ȳ) is precisely what the self-supervised training objective (4.8) seeks to reduce: increasing L drives (λ̂, µ̂) toward stronger dual solutions, tightening the resulting cuts without requiring dual-solution labels. Optional deployment refinement. Because Proxy-BD relies on approximate separation, the master ranks integer incumbents using an underestimate of their true two-stage cost since the proxy bound lower-bounds Q, and can terminate at an incumbent that is not the cheapest one it visited. When the exact recourse value Q(ȳ) of an integer master solution is inexpensive to evaluate, Proxy-BD may re-price the integer incumbents generated during the search by their exact total cost f ⊤ y + Q(y) and return the cheapest. This true-cost selection ranks only solutions visited 24

during the run. It adds no oracle call inside the search and leaves the cut machinery and validity guarantees unchanged, yet it recovers the cheapest fully evaluated design encountered during the search whenever the proxy ranks them in the wrong order. The refinement is optional and orthogonal to cut generation (see Section 6.3 for deployment in large-scale facility location and Table 6.4 for effect quantification). Proxy-BD Termination. Proxy-BD terminates after finitely many iterations under mild assumptions on the separator and deployment environment. In the outer-loop implementation, finite termination follows from the finiteness of the first-stage design space and deterministic proxy separation. In branch-and-Benders-cut deployments, Proposition 4 shows that the proxy separator cannot generate infinitely many cuts under standard numerical separation assumptions. Combined with the finite termination of the underlying branch-and-bound search, this yields finite termination of the B&BC deployment. The following results formalize these termination properties. Remark 4 (Finite termination of outer-loop Proxy-BD). Suppose the first-stage set Y is finite, every restricted master problem has a finite optimum and is solved to global optimality, and the proxy separator is deterministic, producing at most one distinct cut for each design y ∈ Y . Then the outer-loop Proxy-BD algorithm of Section 4.2.2 adds at most |Y | cuts and terminates after finitely many iterations at a proxy fixed point. The result follows immediately from the finiteness of Y and the fact that at most one proxy cut can be generated for each design. Consequently, only finitely many cuts can ever be added. Proposition 4 (Finite proxy-cut generation in B&BC). Consider a B&BC deployment in which every proxy cut is retained in the master relaxation. If the proxy is invoked only at integer incumbents y ∈ Y , then under the assumptions of Remark 4, at most |Y | proxy cuts are added. If the proxy is also invoked at fractional callback points, assume in addition that: (i) a cut is added only when violated by at least ϵsep > 0, (ii) all callback points lie in a compact set S, and (iii) all generated cuts have uniformly bounded coefficients. Then only finitely many additional fractional proxy cuts are added. Proof. The integer-incumbent case follows directly from the finiteness of Y and Remark 4. Consider now fractional callback points. Write the cut generated at callback point zt as ht (z) ≤ 0, where ht is

affine and z = (y, θ) for optimality cuts, while z = y for feasibility cuts. By the uniform coefficient bound, there exists L < ∞ such that every generated cut is L-Lipschitz on S: |ht (z) − ht (z ′ )| ≤ L ∥z − z ′ ∥,

∀z, z ′ ∈ S, ∀t.

Let zt and zs be two callback points at which cuts are generated, with s > t. Since cut t is added only if it is violated by at least ϵsep , then ht (zt ) ≥ ϵsep . Since every proxy cut is globally valid and retained in the master relaxation, every later callback point satisfies all previously generated cuts. Hence, ht (zs ) ≤ 0. Therefore,

ϵsep ≤ ht (zt ) − ht (zs ) ≤ |ht (zt ) − ht (zs )| ≤ L ∥zt − zs ∥, which gives ∥zt − zs ∥ ≥ ϵsep /L. Thus, any two callback points that generate fractional cuts are separated by at least ϵsep /L. A compact set cannot contain infinitely many points that are pairwise separated by a positive distance. Hence, only finitely many fractional proxy cuts can be added. Proposition 4 establishes finite proxy-cut generation under standard numerical separation assumptions. Stopping criterion. In the outer-loop implementation, Proxy-BD terminates when a proxy fixed point is reached. In B&BC deployments, termination occurs when the branch-and-bound search completes and no further proxy cuts are generated by the callback mechanism. Additional stopping criteria such as time limits, iteration budgets, or, whenever available, primal-dual gap tolerances may also be used.

Experimental Design

The experiments evaluate Proxy-BD on three benchmark families and investigate two main questions: whether the certification mechanism consistently produces valid Benders cuts independently of prediction quality, and whether amortized proxy separation delivers substantial computational gains while maintaining near-optimal solutions as the recourse becomes more expensive. The remainder of this section is organized as follows. Section 5.1 describes the implementation environment.

Shape

CAP CAP CAP CAP

50 × 16 50 × 25 50 × 50 1000 × 100

50 50 50 1000

16 25 50 100

1200 1200 1200 1660

UFL UFL UFL UFL UFL

200 × 200 300 × 300 500 × 500 1000 × 1000 2000 × 2000

200 300 500 1000 2000

100 100 100 20 20

Family

Table 5.1: Held-out instance dimensions, facility-location families. m: clients; n: facilities; N : paired test instances. Section 5.2 introduces the benchmark instances. Section 5.3 presents the solution methods and evaluation criteria.

5.1

Implementation Environment

All experiments run on exclusive Intel Cascade Lake Gold 6226 compute nodes with 64 GB of memory. Optimization uses Gurobi 12.0.3 in single-threaded mode (Threads = 1) with default presolve, cuts, heuristics, and tolerances and a fixed seed; only the parameters below change. Each held-out evaluation instance runs with MIPGap = 10−4 and a one-hour wall-clock limit. Proxy training and held-out evaluation are separate Slurm jobs and use the same hardware class. Offline state generation solves each training instance with the exact oracle at MIPGap = 0 under a generous limit and records its master, subproblem, dual, and cut sequence; since no reported runtime uses state-generation time, these runs use shared compute. Held-out evaluation compares the exact oracle against the proxy-only run, which replaces every subproblem solve with the learned predict– project–complete proxy and never falls back to an exact solve. The two share the same master and Benders scheme and differ only in how each cut is separated.

5.2

Instances

Instance Overview. The benchmark draws on three families chosen for complementary recourse structures. The first family is the capacitated facility location problem (CAP) drawn from the ORLibrary (Beasley, 1988). CAP instances have a cheap transportation recourse. The second family is the uncapacitated facility location problem (UFL) drawn from UflLib. UFL instances have a 27

Class

Shape

|V |

|E|

|I|

r03 r06 r09

10 × 35 10 × 60 10 × 83

10 10 10

35 60 83

50 50 50

120 120 120

Table 5.2: Held-out instance dimensions, network design (MCNDP). |V |: nodes; |E|: arcs; |I|: commodities; N : paired test instances. Family

Benders scheme

Cut families

CAP UFL MCNDP

Outer-loop B&BC (Fischetti et al., 2017) B&BC

Optimality Optimality Optimality & Feasibility

0.5 — 0.1

Master side constraint P P s y ≥ i di Pj j j j yj ≥ 1 —

Table 5.3: Exact Benders oracle per family with w being the in-out stabilization mixing weight. closed-form per-client recourse that scales to 2000 × 2000. The third family is the multicommodity capacitated network design problem (MCNDP) drawn from the R set (Crainic et al., 2001). MCNDP instances have a coupled, capacitated routing recourse that can be infeasible. Instance Generation. For each base instance from the CAP, UFL, and MCNDP, perturbed variants are generated by independent lognormal noise on the cost and capacity data, then split 50/25/25 into train/validation/test by a fixed seed with no base instance shared across partitions. Tables 5.1 and 5.2 report the held-out instance dimensions per shape: the number of clients m and facilities n for the facility-location families, and the number of nodes |V |, arcs |E|, and commodities |I| for MCNDP. The paired test count N is the last column of each table. The three families span two orders of magnitude in instance dimension. CAP ranges from 50 × 16 to 1000 × 100, with the largest CAP shape evaluating master-bound behavior at instance dimensions comparable to small UFL. UFL ranges from 200 × 200 to 2000 × 2000, with the two largest shapes used to stress the case in which the recourse, not the master search, drives the wall-clock cost. MCNDP fixes the node count at 10, and the commodity count at 50, while expanding arc density from 35 to 83, thereby increasing the coupling of the capacitated routing recourse. The differences across families in recourse structure, not in raw dimension alone, determine where the proxy helps most. Training and validation perturbations drive offline state generation. The test perturbations are reserved for held-out evaluation.

5.3

Solution Methods and Evaluation Criteria

The families differ in how the proxy is invoked. CAPs are solved using a classical Benders decomposition, with one proxy call generating a cut (see Figure 3). UFL and MCNDP use B&BC (Fischetti et al., 2017; Moreno et al., 2019; Satici and Dayarian, 2026) (see Figure 4). In both, the proxy is the same predict–project–and–complete pipeline of Section 4.2. Exact Oracles and Baselines. The baseline is a fully configured exact Benders oracle. It both generates the offline training states and provides the performance benchmark. Each oracle separates cuts from exact subproblem duals, stabilizes the separation point by in-out stabilization, and uses Gurobi 12.0.3 with lazy callbacks and warm-started dual reuse. The three oracles differ only in the recourse structure and the resulting cut (Table 5.3). For CAP, each subproblem is a transportation LP whose dual yields a knapsack-lifted optimality cut. For UFL, the recourse decomposes by client P in closed form, Q(y) = i minj: yj =1 cij . The state-of-the-art (SOTA) scheme of Fischetti et al. (2017) is used as the UFL baseline. For MCNDP, the coupled multicommodity-flow recourse can be infeasible at a candidate design. In such a case, the oracle emits a knapsack-lifted optimality cut at feasible incumbents and a slice-normalized Farkas feasibility cut at infeasible ones (see Appendix B for more details). At each separation t, the oracle records a Benders state (ξ, ŷ (t) ), with ŷ (t) the stabilized separation point and ξ the instance data. The states accumulated over all training instances form the dataset S. Proxy Models, Repair, and Training. Each family has its own proxy, but all three share the same certification layer of Section 4.2, and it is this shared layer, not per-family tuning, that makes the cuts valid. Because the projection and completion return a dual-feasible certificate for any network output, every emitted cut is a valid Benders cut (Proposition 3). The experiments, therefore, measure only what varies, including cut strength, speed, and, for MCNDP, feasibility restoration. Only the predict step differs (Table 5.4). CAP uses a full-state MLP whose input concatenates the instance data and separation point ŷ (dimension 3n + m + mn), with a Softplus output absorbing the nonnegativity projection. UFL uses a row-wise predictor. The multiplier for client i depends only on that client’s cost row and ŷ, so one network is shared across clients (Appendix B). MCNDP uses a structured MLP for the per-(commodity, node) flow-conservation multipliers û where arcs are ordered by cost for index-invariance. A one-line penalty projection 29

enforcing ûi,oi − ûi,ti ≤ P di keeps the induced optimality cut valid, after which the same continuousknapsack completion as CAP lifts it to the binary design (Appendix B). A separate model is trained per instance shape, since feature and output dimensions scale with the instance. The UFL row-wise proxy is deployed within the framework of Fischetti et al. (2017) and trained on the states generated by that scheme. During deployment, two rules, which do not alter how the cuts are derived, are applied. First, the per-client cuts are aggregated into a single optimality cut for each integer incumbent. This ensures the master problem grows by only one cut per incumbent, rather than one per client. Second, the proxy uses its predictions directly. To choose the final solution, a true-cost selection rule is applied. This rule ranks all the integer designs visited during the run and returns the one with the lowest exact two-stage cost, f ⊤ y + Q(y). Because the subproblem P cost Q(y) = i minj: yj =1 cij can be evaluated in closed form, this final selection simply evaluates known designs and requires no additional oracle calls. For the MCNDP, if the proxy’s predicted multiplier under-prices the recourse, the resulting sliceFarkas feasibility cut at ȳ might not separate an infeasible design. As a result, the master problem might converge on a design that lacks the capacity to route all demand. Note that this is an issue of primal feasibility, not cut validity.To restore feasibility, we use a LP-free repair process. First, a primal-flow certificate checks whether the currently open arcs can route every commodity. If they cannot, we greedily open additional arcs and rank them by the proxy’s predicted dual prices, and recheck the certificate. This loop repeats until all demand is successfully routed (a process guaranteed to terminate, since opening all arcs is always feasible). Finally, we perform a single exact solve on the repaired design to measure its true gap. Training. All proxies use the self-supervised objective (4.8) with Adam (learning rate 10−3 , plateau decay to a 10−5 floor, early stopping after eight non-improving validation checks, best checkpoint retained) on a fixed optimizer-step budget (Table 5.4). MCNDP batches mix optimality and feasibility states. The optimality head is trained on feasible-incumbent states by maximizing the certified dual bound, and the feasibility head is trained on infeasible-incumbent states by maximizing the slicenormalized Farkas separation value (3.3), both with the multipliers passed through their respective projection step before the cut is formed (Appendix B). Evaluation Metrics. The following metrics are reported. The true optimality gap of a design ȳ is 30

Family CAP UFL MCNDP

Proxy model Full-state MLP Row-wise MLP Structured MLP

Hidden units 512, 512 512, 512 256, 256

Batch

Step budget

Val. every

512 512 256

2048 2048 4096

2 220 217

Table 5.4: Proxy model and training budget per family (Adam, lr 10−3 , plateau decay, early stopping). (f ⊤ ȳ + Q(ȳ) − z ⋆ )/z ⋆ , where Q(ȳ) is the exact recourse value from a solve performed after the run (outside the timed comparison), f ⊤ ȳ + Q(ȳ) the resulting exact two-stage cost, and z ⋆ the exact optimum. When the oracle hits the one-hour limit, and no exact optimum is available, the gap to the oracle’s one-hour design is reported, and mark such entries. The true gap on the Oraclecertified subset is reported alongside. For MCNDP, the post-repair feasibility rate and the repair’s activation frequency and cost are also reported. The speedup is the per-instance oracle/proxy wallclock ratio, reported as median and mean. The warm speedup (model-load time amortized) is used throughout. Under one-hour censoring, note that the per-instance median can differ from the ratio of median times. For the accelerated UFL deployment, the number of cuts added is reported, a hardware-independent measure of solver effort.

Computational Results

This section reports the held-out computational results across the three benchmark families. The study is organized into two parts. The first evaluates Proxy-BD in the classical Benders setting to analyze cut quality, certification behavior, and approximation properties relative to exact separation. The second evaluates Proxy-BD within modern large-scale decomposition schemes, where repeated node-level separation makes amortized proxy inference particularly effective computationally.

6.1

Summary of Results

Table 6.1 summarizes the held-out computational performance across all benchmark families, highlighting the relationship between recourse complexity, approximation quality, and amortized speedup. In the cheap-recourse CAP regime, Proxy-BD closely matches the exact oracle with sub-1% median true gaps, but acceleration remains limited because master re-optimization dominates the runtime. As the recourse becomes more computationally expensive, the proxy’s speed advantage 31

Family CAP UFL MCNDP

Test shapes

Test N

Median true gap (%)

Peak speedup

50×16–1000×100 200×200–2000×2000 10×35–10×83

1200–1660 20–100 120

0.00–0.58 0.00–0.50 0.012–2.65

3.6× 161× 27.05×

Baseline Outer-loop SOTA B&BC B&BC

Table 6.1: Held-out summary: median true optimality gap of the proxy against each family’s exact oracle, and peak per-instance speedup. The recourse is feasible at every visited design, and the optimality gap is taken against the exact optimum on every test instance. grows. On the large-scale UFL family, where repeated separation is the dominant bottleneck, ProxyBD achieves up to 161× speedups while maintaining near-optimal solutions with median gaps below 0.5%. MCNDP falls in between: the coupled network recourse is substantially harder than CAP and benefits from proxy acceleration, but the stronger coupling structure also makes cut approximation more challenging, producing a wider gap range while still preserving validity and feasibility throughout all held-out runs. Overall, the summary confirms the central empirical finding of the paper: the computational benefit of Proxy-BD increases with recourse complexity, while the certification layer keeps the cuts valid regardless of prediction quality.

6.2

CAP Instances

CAP has a cheap recourse: each transportation subproblem is inexpensive relative to the master problem, so the proxy has the least opportunity to reduce solve time. The family, therefore, serves primarily as a calibration benchmark: whether Proxy-BD can closely mimic exact separation when there is little computational burden to amortize. On the three small shapes in Table 6.2, the proxy attains a median true gap of 0.39–0.58% at median speedups of 2.4–3.6×; the means exceed the medians (e.g. 4.43% gap and 28.7× speedup on 50 × 25) because the distributions are right-skewed: a small subset of instances is simultaneously harder for the proxy and more expensive for the oracle. Both statistics are therefore reported. Figure 5 gives the full distribution. On the largest CAP shape, 1000 × 100, over 1660 held-out instances the proxy is exact at the median (0.00% median, 0.11% mean true gap) yet does not accelerate (slower at the median, 0.64×, though faster on average, 1.83×), because in outer-loop Benders at this size the repeated master re-solve, not the cheap transportation subproblem, is the bottleneck, so replacing the subproblem yields no net speedup. Solution quality is therefore

Gap (%) Shape 50 × 16 50 × 25 50 × 50 1000 × 100

N 1200 1200 1200 1800

med mean 0.44 0.58 0.39 0.00

Oracle time (s) Proxy time (s) med

1.65 0.22 4.43 2.56 0.92 6.79 0.11 149.60

mean

med

mean

Speedup med

Oracle cuts

Proxy cuts

mean med mean med mean

0.42 0.08 0.18 2.4× 8.5× 3.74 1.00 2.04 2.4× 28.7× 28.32 2.16 3.93 3.6× 36.5× 386.71 410.93 876.72 0.6× 1.8×

18 44 42 87

21 50 68 102

11 27 27 148

13 32 31 144

Table 6.2: Held-out proxy vs. the exact outer-loop oracle on CAP. Gap is the true optimality gap. Time reports both median and mean wall-clock per instance. Speedup the per-instance oracle/proxy ratio (median and mean). Cuts the per-instance optimality cut count (median and mean). The oracle column is listed first throughout. Bold marks < 1.5% gap, > 1× speedup, and the proxy cut count.

Figure 5: Per-shape distribution of the proxy’s true optimality gap on held-out CAP instances, (Q(ȳ) − Q⋆ )/Q⋆ with the recourse evaluated exactly. preserved even at the largest CAP scale. Speedup, however, is not. The two large-scale families examined next have far more expensive recourse, where the proxy’s advantage is largest.

6.3

UFL Instances

UFL is the family on which the recourse, not the master search, dominates the wall-clock cost, and is where the proxy’s advantage is largest. The UFL is deployed within the SOTA B&BC scheme of Fischetti et al. (2017). Table 6.3 reports the comparison and Figure 6 the per-shape distributions. On every shape from 200 × 200 to 2000 × 2000, the accelerated proxy returns designs with mean true gaps below 0.7%, and at the exact optimum for at least half the instances on the two smallest shapes: median gap 0.00%, rising to 0.50% at 500 × 500. The 200 × 200 and 300 × 300 rows serve as calibration: accuracy is preserved while the speedups are modest because the accelerated oracle is itself inexpensive at these sizes. The key entries are the two largest shapes, left at ∼ 70% gap under the classic B&BC scheme (see Appendix C). The speedup broadly increases with the cost of 33

Shape

Gap (%)

Oracle time (s) Proxy time (s)

Speedup

Oracle cuts

med mean

med

200 × 200 100 0.00 300 × 300 100 0.00 500 × 500 100 0.50 1000 × 1000 20 0.36 2000 × 2000 20 0.48 †

0.32 3.11 0.16 5.67 0.61 98.8 0.57 484.9 0.49 3600†

mean med

mean

3.26 8.43 123.4 440.7 3600†

4.70 1.8× 5.5× 2797 2825 122 8.40 2.2× 3.0× 4147 4196 170 9.13 20.7× 34.1× 7171 7164 133 45.7 13.5× 47.3× 13467 13470 362 24.0 161× 183× 27819 27839 115

1.30 2.69 3.52 35.1 22.6

mean

Proxy cuts

mean med mean 184 218 180 346 123

The accelerated oracle reached the one-hour limit on a majority of 2000 × 2000 instances; the gap is then relative to the oracle’s best incumbent, and the speedup is a lower bound.

Table 6.3: Held-out accelerated proxy (true-cost selection) vs. the exact SOTA oracle on UFL. For Time, Speedup, and Cuts, both median and mean across the N matched instances are reported. Bold marks < 1.5% gap, > 1× speedup, and the proxy cut count. Without selection (%) With selection (%) Proxy time (s) Shape

med

mean

med

mean

med

200 × 200 100 9.56 300 × 300 100 6.74 500 × 500 100 7.47 1000 × 1000 20 16.56 2000 × 2000 20 5.93

11.40 7.09 8.19 15.80 7.42

0.00 0.00 0.50 0.36 0.48

0.32 1.30 0.16 2.69 0.61 3.52 0.57 35.07 0.49 22.60

Proxy cuts

mean med mean 4.70 8.40 9.13 45.73 23.97

122 170 133 362 115

184 218 180 346 123

Table 6.4: Ablation of true-cost selection on the SOTA proxy. Without: return the master’s terminal incumbent. With: return the visited integer master solution of the least exact cost. Selection is a closed-form re-pricing of visited solutions, so the per-instance proxy time and cut count are identical under the two treatments and are reported as shared columns. Bold marks the better gap column. exact node-level separation, reaching 161× median at 2000×2000 where the oracle hits the one-hour limit, and the proxy attains it while adding one to two orders of magnitude fewer cuts: a median of 115 aggregated cuts versus 27,819 for the oracle at 2000 × 2000. The benefit of true-cost selection on the same runs is measured by comparing the master’s final incumbent against the design chosen by the selection rule (see Table 6.4). If the master’s final incumbent is solely relied on, essentially deploying the aggregated cuts without the selection step, the median true gap remains high, between 5.9% and 16.6%. However, applying true-cost selection to those identical runs brings the gap down to 0.0–0.5%. The reason is that the branch-and-bound process does discover near-optimal solutions during the search, but the approximate cuts misprice them, causing the solver to rank them incorrectly. By re-pricing all the visited integer solutions using their exact cost, this error is corrected, and the true best design is recovered. This exact P re-pricing uses the closed-form Q(y) = i minj: yj =1 cij (Appendix B). Figure 7 renders the same comparison as a trajectory. Because true-cost selection returns the vis34

Figure 6: Held-out SOTA proxy on UFL. Top: per-shape distribution of the proxy’s true optimality gap, within 1% of the optimum in navy. Bottom: scaling with instance size of solve time (left; the accelerated oracle reaches the one-hour limit at 2000 × 2000) and of the proxy’s true gap (right), which stays below 0.7% on every shape. ited integer design of least exact cost, the accelerated proxy’s best-incumbent true gap is monotone over the search and terminates exactly at the returned design’s gap, unlike the single-shot proxy of Figure 9, reported as one marker. On every shape, the proxy reaches a near-optimal design while separating one to two orders of magnitude fewer cuts than the accelerated oracle needs to close its provable gap.

Figure 7: Convergence under the SOTA deployment on a representative (median-speedup) instance per UFL shape, against the number of cuts separated. The accelerated oracle traces its provable gap 1 − LB/UB. The accelerated proxy traces the true gap of its best incumbent under true-cost selection (Section 6.3), which is monotone and terminates at the returned design’s gap. The proxy reaches a near-optimal design at one to two orders of magnitude fewer cuts.

6.4

MCNDP Instances

MCNDP adds the harder test: a coupled, capacitated recourse that can be infeasible, handled at separation time by the slice-normalized Farkas feasibility cut of Section 3.2, with primal feasibility restored at deployment by the LP-free repair. On all 360 held-out instances, the repair raises postrepair feasibility to 100% on every shape, activating on 24.2% of 10 × 35 instances (median one arc, 0.09 s) up to 75.8% of 10 × 83 instances (median four arcs, 3.2 s). The three shapes trace the same scaling pattern as UFL. On the smallest, 10 × 35, the coupled recourse LP solves in milliseconds, so the proxy stays close to the oracle runtime at 1.42× median speedup with a true median gap of 0.012% certified against the exact optimum on all 120 instances. On the two largest shapes, the recourse is costly: the exact oracle hits the one-hour limit on 66.7% of 10×60 and 66.7% of 10×83 instances, certifying optimality on the other third where the proxy’s true median gap is 0.567% (n = 40) and 2.65% (n = 40) as per Table 6.5. The deployment refinement here is master-side cut-set separation: at every integer master incumbent, the most-violated cut-set P P inequalities of the form e∈δ + (S) ue ye ≥ i:oi ∈S,ti ∈S / di are added as valid master cuts (proxyindependent, vectorized at instance load). This strengthens the master without touching the proxy and yields a speedup that grows with arc count: 1.42×, 9.37×, 27.05× as the shape scales from 10 × 35 to 10 × 83. The largest gaps fall on the instances that the exact oracle also cannot certify within one hour. Table 6.6 reports the gap and speedup. Table 6.7 reframes the MCNDP comparison at the returned-incumbent level for paired proxy and oracle runs, both under the cut-set deployment. The smallest shape is nearly tied: 56 of 113 pairs 36

Shape

Test N

Median gap vs. 1 h design (%)

Median true gap (%, certified)

Peak speedup

10×35 10×60 10×83

120 120 120

0.012 3.97‡ 7.42‡

0.012 (n=120) 0.567 (n=40) 2.65 (n=40)

1.42× 9.37× 27.05×

‡

The exact oracle reached the 1 h limit on 66.7% (10×60) and 66.7% (10×83) of instances; on the censored complement, the true optimum is unknown, and the gap is reported against the oracle’s 1 h design.

Table 6.5: Held-out summary on MCNDP (slice-Farkas B&BC with LP-free repair and master-side cut-set separation at integer master incumbents): the exact oracle reaches the 1 h limit on the two larger shapes, so the all-instances gap is reported against the oracle’s 1 h design and the true optimality gap is reported only on the oracle-certified subset. Gap (%)

Oracle time (s) Proxy time (s)

Speedup

Oracle cuts

Proxy cuts

med

mean med

mean

med

med mean

10 × 35 120 0.012 0.450 2.41 10 × 60 120 3.97† 5.20 3600† 10 × 83 120 7.42† 8.39 3600†

2.95 1.75 2611† 119 2567† 73

2.23 1.42× 1.42× 74 403 9.37× 32.04× 9053 102 27.05× 33.84× 11273

Shape

mean

87 70 8548 1984 8458 1132

81 2210 1185

†

The oracle hits the one-hour limit on most instances of the shape; the gap is then against its best incumbent, and the speedup is a lower bound. On the oracle-certified subset, the true median gap is 0.567% (10 × 60, n = 40) and 2.65% (10 × 83, n = 40).

Table 6.6: Held-out proxy vs. exact oracle on MCNDP under the cut-set deployment. Gap is the true optimality gap on 10 × 35 and the gap to the oracle’s one-hour design on the larger shapes; proxy time includes the LP-free repair. Bold marks < 1.5% gap and > 1× speedup. Shape

Paired N

P <O

P =O

P >O

Mean ∆ UB (%)

10 × 35 10 × 60 10 × 83

113 110 108

0 1 0

56 9 1

57 100 107

+0.461 +5.768 +9.697

Table 6.7: Paired MCNDP upper-bound comparison under the deployment of Table 6.6. P <O, P =O, P >O count instances where the proxy UB is below, equal to (within 10−6 ), or above the oracle UB; ∆UB = 100(UBP − UBO )/UBO . Paired N excludes instances where the oracle returns no feasible UB at the one-hour limit. match the oracle upper bound, and the mean proxy increase is only +0.461%. On 10×60 and 10×83, the proxy upper bound is usually above the oracle upper bound, with mean increases of +5.768% and +9.697%, respectively, although one 10 × 60 pair has a strictly better proxy incumbent. This is consistent with the one-hour oracle censoring in Table 6.6: the large-shape comparison is against the oracle’s returned incumbent rather than a uniformly certified optimum.

Figure 8: Scaling of solve time and optimality gap with instance size for CAP: exact outer-loop Benders versus the proxy. The UFL counterpart under the SOTA deployment is Figure 6 (bottom).

6.5

Mechanisms of the Proxy Advantage

Figure 8 quantifies the scaling argument for CAP, and Figure 6 does so for UFL under the SOTA deployment. Across the small CAP shapes, the proxy’s solve time is nearly flat in the instance dimension while the oracle’s grows by orders of magnitude with the master-bound 1000 × 100 CAP shape constituting the exception noted in Section 6.2. Thus, the speedup is set by the cost of exact Benders, and the true gap stays in a 0.0–1.5% band with no upward trend in size. Structurally, proxy separation consists of a fixed-cost forward pass followed by a closed-form completion. Its cost is set by the network rather than the instance, whereas the exact subproblem solve scales with the recourse. As instance size increases, the computational gap between amortized proxy inference and exact recourse optimization widens. Convergence behavior. Figure 9 contrasts the two solvers on a representative (median-speedup) CAP instance per shape, against the number of cuts separated. The exact solver drives its provable gap 1 − LB/UB down one separation at a time, tracing the familiar decreasing curve and proving optimality costs in tens of cuts on the small CAP shapes. The proxy follows the same branchand-cut logic, replacing each exact separation call with a fixed-cost forward pass. On every CAP shape, the marker sits close to the optimal axis at a small fraction of the oracle’s cut count. The companion convergence figure for UFL is Figure 7 in Section 6.3. Validity and cut tightness. Across the held-out runs, no proxy cut removed the true optimum or rendered the master infeasible. The quality of a proxy-only run therefore tracks how tightly 38

Figure 9: Convergence of the optimality gap against the number of cuts separated for CAP. The exact solver traces its provable gap 1 − LB/UB; the proxy is shown as a single marker at the number of cuts it adds and the true gap of the design it returns. The UFL counterpart under the SOTA deployment is Figure 7. the proxy’s certified cuts approximate the exact ones. When the proxy-generated cuts closely approximate the oracle cuts, the resulting proxy fixed point lies within about 1% of the optimum. When the cuts remain valid but loose, the resulting fixed point becomes suboptimal but never infeasible or invalid. The MCNDP UB comparison in Table 6.7 instead compares cut-set deployment with the oracle incumbent: 10 × 35 is nearly tied, whereas 10 × 60 and 10 × 83 have larger mean UB gaps. The remaining limitation is the looseness of the MCNDP proxy’s predicted duals at the larger shapes. Developing size-aware or more expressive MCNDP predictors, therefore, constitutes the natural next step for improving large-scale performance.

6.6

Practical Insights

Three observations summarize when and how Proxy-BD helps a practitioner considering it in their own decomposition pipeline. Validity is structural. Across the held-out evaluations, no proxy cut removed the true optimum or rendered the master infeasible, and the LP-free repair returned a demand-satisfying design on all 360 MCNDP instances. A poor proxy prediction, therefore, affects solution quality rather than validity or feasibility. The worst possible outcome is a suboptimal design returned with a valid bound. This separates Proxy-BD from heuristic learning-based decompositions whose outputs must be verified case by case. 39

Speedup follows the cost of the recourse. The proxy’s per-cut cost is a single forward pass plus a closed-form completion, near-constant in instance dimension, whereas an exact subproblem solve grows with the recourse. When the recourse dominates, e.g., the two largest UFL shapes and the two largest MCNDP shapes in this study, the proxy delivers a two- to three-order-of-magnitude acceleration. When the master search dominates, e.g., the 1000 × 100 CAP shape, the proxy is neutral or slower at the median because there is little subproblem cost to save. Practitioners should therefore expect the proxy to deliver speedup precisely on the instances where exact Benders is most expensive, and to be near-neutral elsewhere. Deployment refinements address the right tail of the gap distribution. When a single proxy cut is loose, e.g., under-trained large-scale UFL under the standard scheme (see Appendix C) or MCNDP at 10 × 60 and 10 × 83 where the predicted duals under-price the coupled recourse, the deployment can compensate for cut looseness without retraining the underlying model. For UFL, aggregated cuts with true-cost selection (Section 6.3) restore the failing shapes to sub-0.7% mean true gap. For MCNDP, the proxy-versus-oracle UB comparison in Table 6.7 shows near-parity on 10 × 35 and growing UB deltas on 10 × 60 and 10 × 83, so improving predictor tightness is the main way to help the large shapes. The UFL refinement and MCNDP cut-set deployment preserve validity by construction. The MCNDP table is an incumbent-quality diagnostic rather than a cut-count trade-off study.

Conclusions and Future Directions

This paper introduced the Proxy-BD, in which the second-stage subproblem of a two-stage MIP is replaced by an optimization proxy that emits provably valid Benders cuts. The predict–project– complete certification layer of Section 4.2 converts any neural output into a dual-feasible certificate, so every emitted cut is a valid Benders cut by construction. Self-supervised training of the proxy (Section 4.1) maximizes the certified dual bound on oracle states without requiring optimal dual labels. For problems where the subproblem can be infeasible, a slice-normalized reformulation (Section 3) bounds the Farkas certificate set with a single linear constraint, after which the same predict–project–and–complete pipeline applies with exactly one extra bounded constraint in the projection step. An optional LP-free repair restores demand feasibility on the returned design when 40

an exactly feasible solution must be returned. The held-out evaluation on capacitated facility location, uncapacitated facility location, and multicommodity capacitated network design (Section 6) shows that the speedup over the exact oracle grows with the cost of the recourse, while the true optimality gap stays small wherever the proxy’s cuts are tight. The B&BC scheme of Fischetti et al. (2017) serves as the UFL deployment, and the MCNDP cut-set deployment gives a scalable valid-cut baseline whose paired UB comparison shows small 10 × 35 deltas and larger 10 × 60 and 10 × 83 deltas.

7.1

Summary of Contributions

The contributions are summarized below. 1. Proxy Benders cuts with structural validity. The predict–project–complete certification layer of Section 4.2 converts any network output into a dual-feasible certificate; the resulting Benders cut is valid for every y (Proposition 3), so training controls only the strength of the cut, not its validity. 2. Self-supervised training without dual labels. Section 4.1 formulates the training objective as the certified dual bound and supplies its completion subgradient, so the proxy learns from oracle states alone, with no exact-dual labels required. 3. Feasibility handling via slice-normalized Farkas certificates. Section 3 emits a separate feasibility cut from a slice-normalized certificate, with validity by linear programming duality and the slice constraint e⊤ λ ≤ 1 guaranteeing the optimal certificate is supported on an extreme ray of the Farkas cone (Lemma 1). An optional problem-specific LP-free repair restores demand feasibility on the returned design when needed. 4. Held-out evaluation across three problem families. Section 6 reports the proxy’s true optimality gap and speedup against fully configured exact oracles on CAP, UFL, and MCNDP under a uniform protocol, identifying the families and shapes on which the proxy accelerates Benders and the deployment refinements and diagnostics (cut aggregation with true-cost selection for UFL, cut-set-separated UB comparisons for MCNDP) that isolate where cut tightness controls incumbent quality.

7.2

Future Research Directions

Several directions extend this work. 1. Approximation analysis. Characterizing the approximation quality of proxy fixed points relative to exact Benders solutions, and understanding how bounded cut error propagates through the decomposition process, remain important theoretical directions for future work. 2. Size-invariant proxy architectures. The current per-shape MCNDP models are undertrained at the larger shapes (Section 6.4). Graph neural networks that share parameters across instance dimensions would amortize training and may close the gap on shapes the per-shape MLP cannot reach. 3. Stochastic and multi-stage decomposition. The predict–project–complete pipeline extends directly to stochastic Benders, where a single proxy can serve many scenario subproblems, and to multi-stage problems with nested recourse, where the gain of replacing repeated LP solves is amplified. 4. Hybrid proxy–exact deployments. Adaptive schemes that invoke exact separation selectively while relying on the proxy elsewhere could combine the scalability of amortized inference with occasional oracle refinement inside large-scale decomposition frameworks.

7.3

Closing Remarks

The Proxy-BD shows that an optimization proxy can replace the subproblem solve in classical Benders without losing cut validity, and that the speedup so obtained grows with the cost of the recourse. The framework integrates with the various B&BC variants (Fischetti et al., 2017; Moreno et al., 2019; Satici and Dayarian, 2026), and admits deployment refinements that tighten cuts without retraining the model. The combination of structural validity guarantees and selfsupervised training without labels is intended to serve as a basis for further work that integrates optimization proxies into classical operations research decomposition methods.

Acknowledgments This research was partly supported by the NSF AI Institute for Advances in Optimization (Award 2112533).

Code and Data Disclosure The code and data supporting the numerical experiments will be made available upon publication.

References Adulyasak, Y., Cordeau, J.-F., and Jans, R. (2015). Benders decomposition for production routing under demand uncertainty. Operations Research, 63(4):851–867. Beasley, J. E. (1988). An algorithm for solving large capacitated warehouse location problems. European Journal of Operational Research, 33(3):314–325. Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische mathematik, 4(1):238–252. Bloom, J. A. (1983). Solving an electricity generating capacity expansion planning problem by generalized Benders’ decomposition. Operations Research, 31(1):84–100. Bodur, M., Dash, S., Günlük, O., and Luedtke, J. (2017). Strengthened Benders cuts for stochastic integer programs with continuous recourse. INFORMS Journal on Computing, 29(1):77–91. Boland, N., Fischetti, M., Monaci, M., and Savelsbergh, M. (2016). Proximity benders: a decomposition heuristic for stochastic programs. Journal of Heuristics, 22(2):181–198. Cai, H. and Yu, X. (2026). Learning to cut: Reinforcement learning for benders decomposition. arXiv preprint arXiv:2605.06516. Cai, X., McKinney, D. C., Lasdon, L. S., and Watkins Jr, D. W. (2001). Solving large nonconvex water resources management models using generalized Benders decomposition. Operations Research, 49(2):235–245. Codato, G. and Fischetti, M. (2006). Combinatorial Benders’ cuts for mixed-integer linear programming. Operations Research, 54(4):756–766. Contreras, I., Cordeau, J.-F., and Laporte, G. (2011). Benders decomposition for large-scale uncapacitated hub location. Operations research, 59(6):1477–1490. Cordeau, J.-F., Soumis, F., and Desrosiers, J. (2001a). Simultaneous assignment of locomotives and cars to passenger trains. Operations research, 49(4):531–548. Cordeau, J.-F., Stojković, G., Soumis, F., and Desrosiers, J. (2001b). Benders decomposition for simultaneous aircraft routing and crew scheduling. Transportation science, 35(4):375–388.

Crainic, T. G., Frangioni, A., and Gendron, B. (2001). Bundle-based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Applied Mathematics, 112(1-3):73– 99. Er Raqabi, E. M., Beljadid, A., Bennouna, M. A., Bennouna, R., Boussaadi, L., El Hachemi, N., El Hallaoui, I., Fender, M., Jamali, M. A., Si Hammou, N., et al. (2025). OCP optimizes its supply chain for Africa. INFORMS Journal on Applied Analytics. Er Raqabi, E. M., El Hallaoui, I., and Soumis, F. (2023). The Primal Benders Decomposition. Les Cahiers du GERAD, G-2023-27. Fischetti, M., Ljubić, I., and Sinnl, M. (2016). Benders decomposition without separability: A computational study for capacitated facility location problems. European Journal of Operational Research, 253(3):557–569. Fischetti, M., Ljubić, I., and Sinnl, M. (2017). Redesigning Benders decomposition for large-scale facility location. Management Science, 63(7):2146–2162. Fischetti, M., Salvagnin, D., and Zanette, A. (2010). A note on the selection of Benders’ cuts. Mathematical Programming, 124(1):175–182. Keshvari Fard, M., Ljubić, I., and Papier, F. (2022). Budgeting in international humanitarian organizations. Manufacturing & Service Operations Management, 24(3):1562–1577. Laporte, G., Louveaux, F. V., and Mercure, H. (1994). A priori optimization of the probabilistic traveling salesman problem. Operations research, 42(3):543–549. Larsen, E., Frejinger, E., Gendron, B., and Lodi, A. (2024). Fast continuous and integer l-shaped heuristics through supervised learning. INFORMS Journal on Computing, 36(1):203–223. Li, Z., Agyeman, B. T., Mitrai, I., and Daoutidis, P. (2025). Learning to control inexact benders decomposition via reinforcement learning. Computers & Chemical Engineering, page 109461. Liu, S. and Luo, Z. (2023). On-demand delivery from stores: Dynamic dispatching and routing with random demand. Manufacturing & Service Operations Management, 25(2):595–612. Magnanti, T. L. and Wong, R. T. (1981). Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Operations research, 29(3):464–484. Moreno, A., Munari, P., and Alem, D. (2019). A branch-and-benders-cut algorithm for the crew scheduling and routing problem in road restoration. European Journal of Operational Research, 275(1):16–34. Park, S. and Van Hentenryck, P. (2023). Self-supervised primal-dual learning for constrained optimization. In AAAI Conference on Artificial Intelligence. Patel, R. M., Dumouchelle, J., Khalil, E., and Bodur, M. (2022). Neur2sp: Neural two-stage stochastic programming. Advances in neural information processing systems, 35:23992–24005. Rahmaniani, R., Ahmed, S., Crainic, T. G., Gendreau, M., and Rei, W. (2020). The benders dual decomposition method. Operations Research, 68(3):878–895. Rahmaniani, R., Crainic, T. G., Gendreau, M., and Rei, W. (2017). The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259(3):801–817. 44

Satici, O. and Dayarian, I. (2026). A branch-and-benders cut algorithm for a stochastic service network design with crowdsourced capacity. Transportation Science, 60(2):316–342. Tanneau, M. and Van Hentenryck, P. (2024). Dual lagrangian learning for conic optimization. Advances in Neural Information Processing Systems, 37:55538–55561. Wu, L., Adulyasak, Y., Cordeau, J.-F., and Wang, S. (2022). Vessel service planning in seaports. Operations Research, 70(4):2032–2053. Zeighami, V. and Soumis, F. (2019). Combining Benders’ decomposition and column generation for integrated crew pairing and personalized crew assignment problems. Transportation Science, 53(5):1479–1499. Zhang, Y., Lu, M., and Shen, S. (2021). On the values of vehicle-to-grid electricity selling in electric vehicle sharing. Manufacturing & Service Operations Management, 23(2):488–507.

Appendix A

Box Normalization

Setup. Section 3 resolves the scaling ambiguity of Farkas certificates by intersecting the cone R = {λ ≥ 0 : B ⊤ λ ≤ 0} with the slice e⊤ λ ≤ 1. A natural alternative is to bound each multiplier individually, i.e., replace the single linear functional by a box 0 ≤ λ ≤ w with w ∈ Rm + . This section records the box normalization, proves cut validity, and explains, on the two-dimensional geometry of Example 2, why box certificates need not lie on extreme rays of R and therefore can yield strictly weaker cuts than the slice variant. Box Normalization. Introduce row-wise slacks s ≥ 0 and minimize a weighted violation of the recourse system (F): vbox (ȳ) :=

min

x≥0, s≥0

w⊤ s : Bx + s ≥ d(ȳ) .

(A.1)

By construction (A.1) is always feasible, and vbox (ȳ) = 0 iff (F) is feasible at ȳ. Its LP dual is max d(ȳ)⊤ λ : B ⊤ λ ≤ 0, 0 ≤ λ ≤ w . λ

(A.2)

The box constraint makes the dual feasible region a nonempty compact polytope, so (A.2) admits an optimizer λ⋆ ∈ R(w) := {λ ∈ R : λ ≤ w} ⊆ R. Proposition 5. Let λ⋆ be any optimal solution of (A.2). If vbox (ȳ) > 0, then (F) is infeasible at ȳ, the inequality d(y)⊤ λ⋆ ≤ 0 is valid for every y admitting feasible recourse, and it separates ȳ with value d(ȳ)⊤ λ⋆ = vbox (ȳ) > 0. 45

d2 λ2

d1 + d2 ≤ 0

d2 ≤ 0 0

λbox = (1, 1)

d1 R(1)

d1 ≤ 0

d(ȳ) = (1, 21 )

K λ1 (a) d-space (cut).

(b) λ-space (certificate).

Figure 10: Left: the recourse-feasible cone K in d-space and the induced (non-facet) cut d1 + d2 ≤ 0 obtained from λbox = (1, 1). Right: the certificate cone R and the box-normalized feasible region R(1); maximizing d(ȳ)⊤ λ yields λbox = (1, 1), which maps to the red cut on the left. Proof. The primal (A.1) is feasible and the dual (A.2) has a nonempty compact feasible region, so strong duality yields d(ȳ)⊤ λ⋆ = vbox (ȳ). If vbox (ȳ) > 0, then (F) is infeasible at ȳ by the same primal–dual equivalence used in Theorem 3. Since λ⋆ ∈ R(w) ⊆ R, weak duality applied to (F) at any recourse-feasible y gives d(y)⊤ λ⋆ ≤ 0, exactly the structural form of the slice cut (3.4) with the box-induced certificate. Geometry on Example 2. Take m = 2, B = −I2 , X = R2+ , w = 1, and d(ȳ) = (1, 12 ) as in Example 2. Maximizing d(ȳ)⊤ λ = λ1 + 21 λ2 over R(1) = [0, 1]2 yields the unique optimizer λbox = (1, 1), sitting at the corner of the box rather than on an extreme ray of R = R2+ . The induced feasibility cut is d1 (y) + d2 (y) ≤ 0, which is valid by Proposition 5 but strictly dominated by the facet system {d1 ≤ 0, d2 ≤ 0} of the recourse-feasible cone K = {d : d1 ≤ 0, d2 ≤ 0}: the point d = (1, −2) violates feasibility yet satisfies d1 + d2 ≤ 0. In contrast, the slice certificate λslice = (1, 0) from Example 2 hits an extreme ray of R via Lemma 1 and recovers the facet cut d1 (y) ≤ 0. The box and slice certificates therefore deliver different certified separation values, vbox (ȳ) = λbox + 12 λbox = 32 at λbox = (1, 1) versus t⋆ (ȳ) = 1 at λslice = (1, 0); the larger box 1 2 separation value does not translate into a stronger cut, but only the slice variant is guaranteed 46

by Lemma 1 to anchor the proxy (3.5) on a facet of K. Figure 10 illustrates the cut geometry in d-space.

Appendix B

Explicit Predict–Project–Complete Derivations

This appendix carries out the predict–project–complete pipeline of Section 4.2 explicitly on the dual block of each recourse subproblem, for the deployments evaluated in Section 6: CAP, UFL under the plain B&BC scheme, UFL under the accelerated scheme of Fischetti et al. (2017), and MCNDP with slice-normalized Farkas feasibility cuts. A tilde denotes the raw network output and a hat denotes the sign-cone projection. Cut validity holds for any network output by Proposition 3, so each derivation needs only to exhibit a dual-feasible completion.

2.1

CAP: Classic Benders Decomposition

Recourse subproblem. For the CFLP primal in (2.8) and fixed ȳ ∈ Y , write each constraint with its dual multiplier in a dedicated column: Q(ȳ) = min

s.t.

∀i

(λi ≥ 0),

∀j

(µj ≥ 0),

xij ≤ ȳj

∀i, j

(νij ≥ 0).

i,j di cij xij

x≥0

j xij ≥ 1

i di xij ≤ sj ȳj

Associating the listed multipliers with the rows and applying linear-programming duality, each primal column contributes one dual inequality: the variable xij ≥ 0 appears in the demand row i (coefficient 1), the capacity row j (coefficient di , a ≤-row, so µj enters with a minus sign), and its box row (i, j) (coefficient 1, multiplier νij ), giving λi − di µj − νij ≤ di cij . The dual objective collects the right-hand sides of the three constraint families (1, sj ȳj , and ȳj ):

Q(ȳ) = max

λ,µ,ν≥0

i λi −

j sj ȳj µj −

o ȳ ν : λ − d µ − ν ≤ d c ∀i, j . i i j ij i ij i,j j ij

(B.1)

Predict. The proxy outputs λ̃ ∈ Rm , one component per client. The unconstrained network has 47

no built-in sign guarantee, so dual feasibility of λ̃ is not assured. Project. Set λ̂ = (λ̃)+ , the componentwise ReLU. This projects the prediction onto the nonnegative orthant λ ≥ 0 that the demand constraints impose on the demand multipliers. Cut validity (Proposition 3) requires only dual feasibility, so the projection step enforces the sign condition that the network output may otherwise violate; the remaining capacity and box inequalities λi − di µj − νij ≤ di cij are not enforced here but are deferred to the completion step. Complete. For fixed λ̂, the dual (B.1) decouples by facility j in the remaining (µj , ν·j ) block:

min

n o P sj µj + i νij : di µj + νij ≥ λ̂i − di cij ∀i ,

µj ,ν·j ≥0

which is the LP dual of the continuous knapsack nP o P κj (λ̂) := max i (λ̂i − di cij ) ai : 0 ≤ ai ≤ 1, i di ai ≤ sj . The continuous knapsack admits the standard greedy closed form: writing rij := λ̂i − di cij and densities qij := rij /di , sort the items with rij > 0 by decreasing qij and fill capacity sj until exhausted, with the breaking item b taken fractionally. The completion variables are then read off from the knapsack KKT threshold density qbj : µ̂⋆j = qbj =

λ̂b −db cbj , db

⋆ ν̂ij = rij − di µ̂⋆j + = di qij − qbj +

∀i.

⋆ . If every positive-profit item Only customers with density strictly above qbj receive a positive ν̂ij ⋆ = [r ] . fits within sj , the capacity is slack and one takes µ̂⋆j = 0 and ν̂ij ij +

Cut. By strong duality of the per-facility completion, κj (λ̂) = sj µ̂⋆j +

⋆ i ν̂ij ,

(µ̂⋆ , ν̂ ⋆ ) into the ȳ-dependent terms of (B.1) gives the cut slope βj = −(sj µ̂⋆j + P and intercept α = i λ̂i . The proxy optimality cut at any y is therefore θ ≥

i λ̂i −

which matches Example 1.

j κj (λ̂) yj ,

so substituting

⋆ i ν̂ij ) = −κj (λ̂)

2.2

UFL: Classic B&BC

Proxy architecture (row-wise). CAP uses a full-state representation because its capacity rows tie all clients together through the shared facility multiplier µj . UFL has no such coupling: conditional on a fixed Benders state ŷ, the canonical oracle multiplier πi⋆ (ŷ) for client i, i.e, the optimal assignment cost minj:ŷj =1 cij , depends only on that client’s cost row ci,: and on ŷ, not on the other rows and not on the opening costs f . The natural proxy is therefore a single network shared across clients and applied row by row, hθ (ci,: , ŷ) = π̂i , The opening costs f only appear in the master objective, where they determine which designs to explore. Once the decisions ŷ are fixed, the subproblem and its certificate no longer depend on f . As a result, the proxy model never needs f as an input. Additionally, because the certified bound is simply a sum across all clients, this speeds up training on large instances. Instead of evaluating every client, a sum over a random subset I takes place before multiplying by m/|I| to get an unbiased estimate of the full bound. During deployment, however, the generated cut evaluates all clients. Recourse subproblem. The M -instance UFL has no capacity constraint and nonnegative asP signment costs cij ≥ 0; a master side constraint j yj ≥ 1 keeps at least one facility open, so the recourse is feasible at every visited design. At fixed ȳ,

Q(ȳ) = min

s.t.

∀i

(πi ≥ 0),

xij ≤ ȳj

∀i, j

(νij ≥ 0).

x≥0

i,j cij xij j xij ≥ 1

Associating the listed multipliers and applying linear-programming duality, the column of xij ≥ 0 appears in the demand row i (coefficient 1) and its box row (i, j) (coefficient 1, a ≤-row, so νij enters with a minus sign), giving the single inequality πi − νij ≤ cij ; the dual objective collects the right-hand sides 1 and ȳj :

Q(ȳ) = max

π,ν≥0

i πi −

o ȳ ν : π − ν ≤ c ∀i, j . j ij i ij ij i,j

(B.2)

Predict. The proxy outputs π̃ ∈ Rm , one component per client, unconstrained in sign. Project. Set π̂ = (π̃)+ , projecting onto the nonnegative orthant π ≥ 0 induced by the assignmentdemand constraints. As in CAP, validity needs only dual feasibility; the linking inequalities πi −νij ≤ cij are deferred to completion. Complete. With no facility-capacity row there is no shared multiplier and no coupling across clients, so the completion decouples into one trivial program per pair (i, j), i.e., the smallest νij ≥ 0 with νij ≥ π̂i − cij , i.e. the linear program minνij ≥0 {νij : νij ≥ π̂i − cij }, whose optimizer is

ν̂ij (π̂) = (π̂i − cij )+ , a single elementwise pass with no LP solve and no sort: the continuous-knapsack completion of CAP with the capacity row absent. Cut (disaggregated). Under the plain B&BC deployment the recourse decomposes by client, P P P Q(y) = i Qi (y), where Qi (y) = min{ j cij xij : j xij ≥ 1, 0 ≤ xij ≤ yj } is the per-client assignment LP (equal to minj: yj =1 cij at integer y). The proxy emits one cut per client on a per-client epigraph variable θi , θi ≥ π̂i −

X (π̂i − cij )+ yj , j

which lower-bounds Qi (y) for all y (Proposition 3); the master represents the total recourse by P i θi . It therefore grows by one cut per client at each separated state. Appendix B extends this derivation to the SOTA deployment, where the per-client certificates are aggregated into a single cut per integer incumbent.

2.3

UFL: SOTA deployment

The accelerated deployment of Section 6.3 solves the same M -instance UFL recourse as Appendix B, but inside the single-tree B&BC scheme of Fischetti et al. (2017) and with the per-client certificates aggregated into one cut per incumbent. For completeness, the full pipeline is written below; the recourse, predict, project, and complete steps coincide with Appendix B, and only the cut assembly and the deployment rule differ.

Recourse subproblem. At a fixed integer incumbent ȳ (with

j yj ≥ 1 and assignment costs

cij ≥ 0, as in Appendix B), the recourse and its dual are

Q(ȳ) = min

i,j cij xij

x≥0

Q(ȳ) = max

j xij ≥ 1 (πi ≥ 0) ∀i,

i πi −

π,ν≥0

o xij ≤ ȳj (νij ≥ 0) ∀i, j ,

o ȳ ν : π − ν ≤ c ∀i, j , j ij i ij ij i,j

where the dual is obtained column-by-column exactly as in Appendix B, and the recourse decomP poses by client, Q(ȳ) = i Qi (ȳ) with Qi (ȳ) = minj:ȳj =1 cij . Predict. The row-wise network outputs one multiplier per client, π̃i = hθ (ci,: , ȳ), stacked into π̃ ∈ Rm . Project. π̂ = (π̃)+ , the componentwise ReLU onto the nonnegative orthant π ≥ 0. The SOTA proxy uses this projected prediction as is. Complete. As in Appendix B, with no facility-capacity row, each linking multiplier is completed independently and in closed form, ν̂ij (π̂) = (π̂i − cij )+ , a single elementwise pass with no LP solve and no sort. Cut (aggregated). The plain deployment of Appendix B keeps a per-client epigraph θi and emits P the m cuts θi ≥ π̂i − j (π̂i − cij )+ yj . The accelerated deployment instead introduces a single P aggregate recourse epigraph θ (master objective min j fj yj + θ, with θ standing for the total P recourse i Qi (y)) and sums the per-client certificates into one cut with coefficients

α=

i π̂i ,

βj = −

Each per-client summand π̂i −

summing over clients gives α +

i (π̂i − cij )+ ,

j (π̂i − cij )+ yj

j βj yj ≤

θ ≥ α+

j βj yj .

lower-bounds Qi (y) for every y (Appendix B);

i Qi (y) = Q(y), so the aggregate inequality is a valid

optimality cut by Proposition 3. The master therefore grows by one cut per integer incumbent rather than one per client, which is the source of the one to two orders of magnitude reduction in

cut count in Table 6.3. Deployment (SOTA driver, true-cost selection). The aggregate cut is separated only at integer incumbents within a single branch-and-bound tree, in the accelerated style of Fischetti et al. (2017), with no explicit cutting-plane warmup. The returned design is not the master’s P terminal incumbent but the visited integer design of least exact total cost j fj yj + Q(y), with P Q(y) = i minj: yj =1 cij evaluated in closed form; this ranks only designs already visited during the run and requires no additional oracle calls.

2.4

MCNDP: Classic B&BC

Recourse subproblem. The network is a directed graph with node set V and arc set E. Let I be the commodity set; commodity i has origin oi , destination ti , and demand di . Arc j has tail tail(j), head head(j), capacity sj , variable unit cost cj , and fixed cost fj . The variable xij ∈ [0, ȳj ] is the fraction of commodity i routed on arc j, and δ + (v), δ − (v) denote the arcs leaving and entering node v. Write biv for the net supply of commodity i at node v: bi,oi = 1, bi,ti = −1, and biv = 0 otherwise. For fixed ȳ the recourse is

Q(ȳ) = min

i,j di cj xij

s.t.

j∈δ + (v) xij −

i di xij ≤ sj ȳj

x≥0

j∈δ − (v) xij

≥ biv

xij ≤ ȳj

∀i, v

(uiv ≥ 0),

∀j

(ρj ≥ 0),

∀i, j

(τij ≥ 0).

The first line is flow conservation for commodity i, written as outgoing minus incoming with a “≥” sense (so the duals satisfy uiv ≥ 0): one unit must leave the origin, one unit must reach the destination, and every other node is balanced. The last two lines are the shared arc capacity and P the per-arc open bound. The fixed design cost j fj yj is not part of Q(ȳ); it is folded into the cut below. The recourse is feasible at ȳ if and only if the open arcs can route every commodity within their capacities; otherwise, the master separates a feasibility cut. Associating the listed multipliers and applying linear-programming duality, the routing variable xij ≥ 0 enters the tail flow row tail(j) (coefficient +1), the head flow row head(j) (coefficient −1), the 52

shared capacity row j (coefficient di , a ≤-row, so ρj enters with a minus sign), and its box row (i, j) (coefficient 1, multiplier τij ), giving the dual feasibility row ui,tail(j) − ui,head(j) − di ρj − τij ≤ di cj . P The dual objective collects the constraint right-hand sides: i,v biv uiv from the flow rows and P P − j sj ȳj ρj − i,j ȳj τij from the capacity and box rows. Two dual programs: optimality cone and slice-Farkas certificate. Two related dual programs share the dual cone of the recourse. The first is the standard recourse dual, used to derive optimality cuts at feasible ȳ:

Q(ȳ) = max

u,ρ,τ ≥0

i,v biv uiv −

j sj ȳj ρj −

o ȳ τ : u − u − d ρ − τ ≤ d c ∀i, j . i j ij i j i,tail(j) i,head(j) i,j j ij

(B.3) The second is the slice-normalized (Farkas) LP, used to derive feasibility cuts at infeasible ȳ. It optimizes over the same recourse-feasibility recession cone as (3.3), but with a problem-specific bounded normalization rather than the single functional e⊤ λ ≤ 1 of (Dual-slice): the recoursefeasibility recession cone (the cost-side row drops out, replaced by the homogeneous bound ≤ 0), P with a per-commodity normalization v ui,v ≤ 1 (one per commodity i) that bounds the Farkas certificate set:

max

u,ρ,τ ≥0

i (ui,oi − ui,ti ) −

j sj ȳj ρj −

i,j ȳj τij

: ui,tail(j) − ui,head(j) − di ρj − τij ≤ 0 ∀i, j, o P (B.4) v uiv ≤ 1 ∀i .

Cut validity follows solely from (u, ρ, τ ) lying in this homogeneous recession cone, independently of the choice of normalization. When ȳ is infeasible for the recourse, the LP (B.4) has a strictly positive optimum, and the corresponding (u⋆ , ρ⋆ , τ ⋆ ) furnishes a separating feasibility cut α + β ⊤ y ≤ 0 valid P at every y admitting feasible recourse. The per-commodity cap v uiv ≤ 1 is not a verbatim instance of the single-functional slice e⊤ λ ≤ 1 of Theorem 3, but exact detection still loses nothing: P any positive Farkas ray (u, ρ, τ ) can be rescaled by the single scalar γ = 1/ maxi v uiv > 0, which preserves the homogeneous arc inequalities (so the shared ρj scales consistently), meets every cap P γ v uiv ≤ 1, and keeps the objective strictly positive; hence infeasible recourse still yields a strictly P positive optimum. This uses the cap as an inequality (≤ 1): the equality simplex v uiv = 1 would 53

break the argument when a commodity has zero row-sum. The one-sided qualification therefore attaches only to a proxy-predicted certificate, which may be too weak to separate (Proposition 2). Predict. The dual-tower proxy outputs two flow-conservation predictions, ũopt , ũfeas ∈ R|I|·|V | , one per cut family. Both heads share the same encoder of the Benders state ξ = (instance features, ȳ) and differ only in their final linear layers. opt Project. For the optimality head the projection is elementwise ReLU, ûopt iv = (ũiv )+ . For the P feas feasibility head the projection enforces nonnegativity and the per-slice constraint ≤ 1: v ûiv

first the elementwise ReLU on ũfeas , then the closed-form Euclidean projection of each row (ûfeas i,v )v P onto the capped simplex {u ≥ 0 : v uiv ≤ 1} (the “≤ 1” slice in (B.4), not the equality simplex P v uiv = 1). Each projection enforces only the sign (optimality head) or sign-and-slice (feasibility head) restrictions on the predicted u-block; it does not by itself place (û, ρ, τ ) in the recourse dual cone, since the arc inequalities ui,tail(j) − ui,head(j) − di ρj − τij ≤ di cj (optimality) or ≤ 0 (feasibility) are enforced only after the (ρ, τ ) completion below. Once completed, the full certificate is dualfeasible, and the emitted cut is valid by Proposition 3 (optimality head) and Theorem 3 (feasibility head), regardless of network parameters. Complete. The per-arc (ρj , τ·j ) completion has the same closed form for both heads. For fixed û, the inner block of the dual decouples by arc; writing the per-commodity profit pij (û) = ûi,tail(j) −ûi,head(j) − di cj (optimality head),

or pij (û) = ûi,tail(j) −ûi,head(j) (feasibility head),

the completion solves

min

n o P sj ρj + i τij : di ρj + τij ≥ pij (û) ∀i ,

ρj ,τ·j ≥0

the LP dual of the continuous knapsack

κj (û) := max

i pij (û) ai :

0 ≤ ai ≤ 1,

i di ai ≤ sj

o .

This is the standard continuous knapsack with profit pij , weight di , and capacity sj , solved in closed form: writing densities qij := pij (û)/di , discard the items with pij ≤ 0, sort the rest by decreasing qij , 54

and fill sj until exhausted, with the breaking item b taken fractionally. The completion multipliers are then read off from the knapsack KKT threshold density qbj , ρ̂⋆j = qbj =

pbj (û) db ,

τ̂ij⋆ = pij (û) − di ρ̂⋆j + = di qij − qbj + ∀i,

exactly as in the CAP construction. By strong duality κj (û) = sj ρ̂⋆j +

⋆ i τ̂ij .

Cut. For the optimality head, substituting (ρ̂⋆ , τ̂ ⋆ ) into the ȳ-dependent terms of (B.3) gives slope P P opt ) y . Folding the design cost βj = −κj (ûopt ) and intercept α̂ = i,v biv ûopt j j κj (û iv , i.e. θ ≥ α̂ − P through the total-objective epigraph η = θ + j fj yj yields the knapsack-lifted optimality cut η ≥ α̂ +

fj − κj (ûopt ) yj .

For the feasibility head, substituting (ρ̂⋆ , τ̂ ⋆ ) into (B.4) gives slope βj = −κj (ûfeas ) and intercept P feas α(ûfeas ) = i (ûfeas i,oi − ûi,ti ), i.e. the slice-Farkas feasibility cut α(ûfeas ) +

−κj (ûfeas ) yj ≤ 0,

valid by Theorem 3 for every ûfeas in the slice cone. At deployment, both heads are queried at each integer incumbent, and only the violated cut (if any) is added to the master.

Appendix C

UFL Instances under Classic B&BC

Under classical B&BC deployment, UFL shows the scaling effect over two orders of magnitude (see Table C.1). On the four shapes from 100 × 100 to 500 × 500 the proxy holds a median true gap of 0.86–1.48% while the median speedup climbs from 36× to 672×. The exact oracle reaches the one-hour limit on much of 300 × 300 and 500 × 500, whereas the proxy returns its design in ≤ 0.18 s up to 300 × 300 and in 6.94 s at 500 × 500. The two largest shapes, 1000 × 1000 and 2000 × 2000, are a boundary case: the proxy returns a design in under a second but at 70–71% true gap. By the validity guarantee, these cuts remain correct, so the degradation is one of cut strength: the per-shape model is undertrained at these sizes and emits cuts too loose to drive the master, and the search halts at a poor proxy fixed point. This is a limitation of the trained model, not the cut 55

Gap (%) Shape 200 × 200 300 × 300 500 × 500 1000 × 1000 2000 × 2000 †

Time (s)

Speedup

median

mean

oracle

proxy

median

mean

100 100 100 20 20

1.41 1.48 0.86 71.4 70.1

1.44 1.34 0.91 71.3 70.1

153.6 90.6† 3600† 3600† 3600†

0.18 0.18 6.94 0.05 0.20

646× 672× 505× — —

737× 1776× 663× — —

Oracle hit the one-hour limit on some or all instances of the shape; the gap is then against its best incumbent and the speedup a lower bound.

Table C.1: Held-out proxy vs. exact oracle. Gap is the true optimality gap; Time the median solve time; Speedup the oracle/proxy ratio; N paired instances. Bold marks entries where the proxy improves on the oracle (< 1.5% gap, > 1× speedup). machinery.

Record · ID 266170 · SHA-256 eeffb24cdf1ed9cf
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.