Learning Generalized Linear Programming Value Functions
Authors: Tu Anh-Nguyen
Joey Huchette
Christian Tjandraatmadja
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Linear Programming; Mixed-Integer Programming; Neural Networks; Constrained Optimization
Primary area: optimization
TL;DR: We develop a theoretically-grounded method for learning approximations of Generalized Linear Programming Value Functions, and use it to construct a heuristic for large-scale two-stage Mixed-Integer Linear Programs.

Abstract: We develop a theoretically-grounded learning method for the Generalized Linear Programming Value Function (GVF), which models the optimal value of a linear programming (LP) problem as its objective and constraint bounds vary. This function plays a fundamental role in algorithmic techniques for large-scale optimization, particularly in decomposition for two-stage mixed-integer linear programs (MILPs). This paper establishes a structural characterization of the GVF that enables it to be modeled as a particular neural network architecture, which we then use to learn the GVF in a way that benefits from three notable properties. First, our method produces a true under-approximation of the value function with respect to the constraint bounds. Second, the model is input-convex in the constraint bounds, which not only matches the structure of the GVF but also enables the trained model to be efficiently optimized over using LP. Finally, our learning method is unsupervised, meaning that training data generation does not require computing LP optimal values, which can be prohibitively expensive at large scales.  We numerically show that our method can approximate the GVF well, even when compared to supervised methods that collect training data by solving an LP for each data point. Furthermore, as an application of our framework, we develop a fast heuristic method for large-scale two-stage MILPs with continuous second-stage variables, via a compact reformulation that can be solved faster than the full model linear relaxation at large scales and orders of magnitude faster than the original model.

Learning Generalized Linear Programming Value Functions
Tu Anh-Nguyen
Joey Huchette Google Research Cambridge, MA
Google Research and Rice University Houston, TX tu nu.na@rice.eem
jhuchette@googgle.co
Christian Tjandraatmadja
Google Research Cambridge, MA ct jaindra@@gogge..comm com com
Abstract
We develop theoretically-grounee learning method for the Generalized Linear Programming Value Function (GVF), which models the optimal value of a linear programming (LP) problem its objective and constraint bounds vary. This func- tion plays a fundamental role in algorithmic techniques for large-scale optimization, particularly in decomposition for two-stage mixed-ine -nttger linear programs (MILPs). This paper establishes structural characterization of the GVF that enables it to be modeled particular neural network architecture, which the GVF in a way that benefits from three notable properties. First, our method produces a true under-approxxmmation of the value function with respect the constraint bounds. Second, the model is input-convex in the constraint bounds, which not only matches the structure of the GVF but also enables the trained model to be efficiently optimized over using LP. Finally, our learning method is unsupervised, meaning that training data generation does not require computing LP optimal values, which can be prohibitively expensive at large scales. We numer- ically show that our method can approximate the GVF well, even when compared to supervised methods that collect training data by solving an LP for each data point. Furthermore, as an application of our framework, we develop a fast heuristic method for large-scale two-stage MILPs with continuous second-stage variables, via a compact reformulation that can be solved faster than the full model linear relaxation at large scales and orders of magnitude faster than the original model.
then to learn
Introduction
The linear programming (LP) value function models the optimal value of an LP as problem data in that problem varies. Value functions are fundamental abstraction used in many algorithms for large- scale optimization. More concretely. many problems where decisions are made sequentially-en two-stage stochastic programs [46], facility location problem [17], multi-commodity problems [19], or network interdiction problems [49]-can be modeled as two-stage mixed-integer linear programs (MILPs). To pick one common technique as a motivating example: Benders' decomposition is an algorithmic technique that decomposes such a large problem into many smaller ones [21, 42, 51]. At a high level, Benders' decomposition abstracts each LP subproblem away by replacing with a value function. If we somehow had a good approximation of these value functions that we could efficiently optimize over, this reformulation would be straightforward to approximately solve. Benders' decomposition however, we do not have such representation priori, and thus we iteratively
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

construct an approximation of it via cutting planes; this is often the most computationally expensive part of the algorithm [36, 57]. In this paper, we focus on learning such representations.
Separately, it is well-known that neural networks (NNs) are "universal approximators" in theory [4, 23, 26, 35] and incredibly adept modeling complex behaviors in practice [1, 7, 9, 37]. Taken together, we can state two natural questions that motivate this work:
What are the meaningful structural properties of a value function, and what are suitable neural network architectures for encoding these properties?
How good are these approximations in practice, and how can we leverage them to solve real-world problems?
Contributions. Our work studies the Generalized Linear Programming Value Function (GVF), defined as the function that models an LP's optimal value both its objective and its constraint bounds vary, and shows how machine learning techniques can be used to build practical approximations of this function. In partieular, our contributions are as follows.
1. A GVF Representation theorem. We study the structure of the GVF and show that it can be exactly modeled as a maximum of bilinear functions, where each function is the dot product of two piecewise linear functions that depends only the objective coefficients or constraint bounds, respectively.
2. A theoretically-groun neural network architecture which mimics the structural property of the GVF exposed by our representation theorem.
NN architecture for GVE We present the Dual-Stack Model, a
3. An unsupervised learning approach. We show that the GVF can be written as the unique optimal solution of a constrained optimization problem that does not require solving any LPs to write down. We use this as inspiration for an unsupervised learning method that can be implemented using standard NN training constructs and libraries.
4. Empirical justification. We present a computational study showing that our unsupervised training approach can perform comparably with supervised training in terms of approximat- ing a GVF, without the expensive data generation phase that supervised training requires.
5. A fast heuristic for large-scale two-stage MILPs. Due to the properties of the Dual-Stack Model, we can easily embed it as an LP within a larger optimization problem. As an application of our framework, we leverage this fact produce a heuristic for two-stage MILPs with continuous second-stage variables, which includes a provable duality gap.
2 Preliminaries
Linear Program (LP) is a mathematical optimization problem of the form:
(1) where x the decision variables, R is the vector of objective coefficients, A E Rmx" is the constraint matrix, and E IR is the vector of constraint bounds (often called the "right-hand side" in such representation).
min(c- x Ax < b, 2 0, E R"),
Duality is a fundamental concept in linear programming that establishes a relationship between the primal (original) linear program and its dual (related) linear program. This relationship provides insights into the optimal solutions, and it is valuable for both theoretical understanding and practical applications. The dual problem of (1) is
max(b y A
y S c, 0,ye
(2)
The typical LP Value Function (LPVF) is ( minz (c. Ar S B, 2 0, E R As corollary of strong duality, the LPVF is piecewise linear convex function, which the maximum of a finite number of affine functions. Note that the LPVF only considers varying constraint bounds; we also permit the objective coefficients to vary, we obtain the Generalized LP Value Function (GVF) [52]. Formally, we define a GVF associated with a fixed constraint matrix A E RR as:
ha B) min { y Ar S 8, 2 2).
(3)

---

Many typical decomposition methods only need to consider LPVFs of fixed objective vectors However, learning the entire GVF once means that we can reuse the same learned model for many different objectives, potentially saving computation and allowing for a broader generalization.
We use (P (8) to denote the linear program in (3) for fixed values of 7 and (9. Conventionally, when LP 3) is infeasible, h17,88 3) = +00, and when LP () is unbounded from below, we have h(,, 8) -00. Let B = { E R" Ex E R² s. Ar S 3, 2 0} and C = { E R By R s.I A S 7. < 0}. By strong duality and the definitions of and C: h(7, () is finite if and
only if y E and 3 E B. We define ((3) = far R. Ax I 3, Z 0} as the set of feasible solutions of (P( for a fixed B E B.
In this work, we will consider two-stage MILPs with continuous second-stage variables, where fixing the first-stage variables results in the problem decomposing into K' independent LPs. In particular, these have the form:
min
C. x
Σ d 1 Ex, Thxx Ax S <b. 2. 2A E [K] KE[K]
(4)
where r E R" are the first-stage variables, is the first-stage feasible set, K = is the number of second-stage subproblems, and [K] denotes the set f K}. ,K. For example, in the context of stochastic programming. K' is the number of scenarios, or in facility location problem, K is the number of customers. Each subproblem & is associated with corresponding continuous second-stage variables z2 E R We assume that the second stage constraint matrices are the same, denoted as A E IR2 x while the constraint matrices first-stage and the constraint bounds constraints vector can vary among second-stages, denoted as T and bt, respectively. We can rewrite (4) using GVF as
mün
C. x
+ Σ ha - x² E
(5)
AE[K]
Within the context of GVFs, we can reformulate equation (3) to elide the requirement for second-stage variables. The large number of these variables can impede computational efficiency [18], which motivates compact representation of GVFs.
Related Work
3.1 Value function learning for multi-stage problems
Neural networks are well-known to be powerful "universal approximators" [35]. This has motivated a line of research focused on learning value functions, particularly those based on constraint bounds such as LPVF and their MILP analogues, with the main goal of improving methods for two-stage or multi-stage optimization problems. Dai et al. [13], Lee al. [34], and Bae et al. [5] propose various methods to learn the LPVF with the aim to solve multi-stage stochastic programming problems more quickly. Similar to our work, they use models that are convex on constraint bounds to match the structure of the LPVF. Beyond the LP value function, neural networks have also been used to learn IP value functions to improve the integer L-shaped method [33]. Moreover, to tackle difficult mixed-integer problems with a large number of scenarios, Dumouchelle et al. [14, 15] devise NN architectures that learn MILP value functions of constraint bounds and scenarios.
Our method differs from the above in that we directly learn the GVF rather than the LPVF (though [14] learns the GVF indirectly), we do not require solving optimization subproblems (LPs in our case) to obtain training data. Furthermore, we aim to not only generalize across second-stage subproblems (scenarios), but also across instances. In particular, by allowing the objective coefficients to vary, we learn single value function that encompasses all subproblems, rather than learning one per subproblem. Of course, learning a single GVF generally harder than learning a single LPVF, but a core thesis of this work is that there is underlying structure tying together those many related LPVF's that we can exploit when learning the GVE.
3.2 Other learning- based approaches
related research direction in learning for stochastic optimization is scenario reduction, which seeks smaller set of "representative scenarios". Many of these approaches perform some form
3

---

of clustering to reduce the number of scenarios and then solve a smaller surrogate problem with these scenarios [10, 16, 30, 41, 44]. Wu et al. [55] uses conditional variational autoencoder to learn scenario embeddings and cluster them. Bengio et al. [8] predicts a representative scenario for smaller surrogate problem, but relies on problem structure to build scenarios for training.
Other learning-basee based methods for tackling two-stage stochastic problems include reinforcement learn- ing for local search [38] and Benders cut classification [28]. More generally, ML-based approaches have also been applied for bilevel optimization [29, 47, 48, 56] where value functions are relevant, though unlike in our case, these only have a single inner optimization subproblem. Finally, there an extensive stream of work focusing on applying ML to support decisions within MILP solvers, such as branching and cutting plane decisions (e.g,, [2, 24, 39, 50)).
3.3 Computing value functions
LP value functions are well-studied (e.g., see [45, Chapter 19]), as they play crucial roles in sensitivity analysis and Benders' decomposition. On the other hand, GVFs are considerably less well-studied. While much is known about its structure [22, 27], to the best of our knowledge our method is the first that aims to learn it directly based on its theoretical properties. The computation of value functions has also been studied for ILPs and MILPs using superadditive duality [32, 43, 52, 53J. However, they are less tractable to compute and thus more difficult to leverage into practical algorithm.
4
A Neural Network Representation for Generalized Linear Programming Value Functions
In this section, we will develop a characterization of the GVF that, in the sequel, we will use as inspiration for neural network architecture that is well-suited to approximate the GVF.
4.1 A Characterization of Generalized Linear Programming Value Function
is known that B can be partitioned into distinct invariancy regions, within each of which the GVF is bilinear with respect to B and y [27]. This can be reformulated as the following proposition.
Proposition Fix a matrix A E RR and define SB) as the set of all bases of A which are feasible with respect to fixed constraint bounds E B. Then, ha(r, B) min Te B-B-1p Furthermore, ha(-,b) is piecewise linear concave for every fixed B and ha(c,-) is piecewise linear convex every fixed E C.
While Proposition tells us that each invariancy region defined by B can be decomposed into product of functions that depend only on and 3, it does not provide us with global decomposition that is valid across all invariancy regions. We now show that there does indeed exist structured, global decomposition of a GVF terms of piecewise linear functions that consider either or 3, but not both.
Theorem 2. (GVF Representation Theorem) For fixed matrix A Rm there exists set of p piecewise linear functions (Fp RD + RR K p=1 and a piecewise linear convex function
G R. + RKK such that
ha(7, B) = max (F())T WEC,BEB
(6)
PE[M
We refer the reader to Appendix A for a proof of this result.
4.2 The Dual-Stack Model
We now use Theorem 2 as inspiration for a neural network architecture that we dub the Dual-Stack Model (DSM). For simplicity, in the remainder will consider LPs written in the form of (1); see Appendix F for analogous models for other LP representations.
The architecture of a DSM is depicted in Figure 1. It consists of two stacks of feedforward fully- connected neural networks of depth N and M corresponding the objective vector y and the constraint bounds vector 3; we name them the 7-stack and the B-stack, respectively. Each layer

---

has piecewise linear activation function to ensure that the entire stack itself is piecewise linear; either ReLU or Max-pon Max-pooling is suitable choice. We denote the output matrix of the 7-stack as Φ and the output vector of the f-stack as V, respectively. To model the outer maximization in (6), the output of the model is the maximum element of the dot product between + and V. Finally, the 3-stack is constrained so that the first layer has non-positive weights and each subsequent layer has non-negative weights; this enforces the desired properties of a GVP listed in Theorem 3, such as convexity on 8 [3]. In general, the y-stack represents the functions {Fp p=1 and the 3-stack models the function G' from Theorem 2.
We can summarize the properties of DSM as follows. Let a' the i-th column of the matrix A. Then we may define H(AA) == (+ AA is DSM and (7(7,, a²) S 7 Vy E C E [ to be the class of functions that can be rep- resented by a DSM, subject to what we might call dual feasibility constraints
value function 7A (output)
max
Thiorrm
their outputs.
Nx
linear projection
lincar transform
xM
Theorem 3. Any function TI E H(A) has the following properties:
Theowen
objective vector (input)
1. na(T:)) is piecewise linear, convex, and mono- tonically decreasing for every fixed y E C.
linear transform
positive wiigt constrairt
2. nA(,BB) is piecewise linear for every fixed 3 E B.
regative weight conerriint
B rhs vector (input)
ReLU pooling Marri Multptictiion
3. 74(1,3) S hall, for every fixed B E B and
7 E C.
Figure 1: Dual-Stack Model (DSM)
This result shows that, for fixed inputs, ha is upper-bounded by the true GVF. In fact, we can show something even stronger.
Theorem 4. For any fixed A E Rm*X,, hA E H())), and moreover A is pointwise larger than all other elements of (A).
One way to interpret Theorem 4 that there exists some DSM architecture whereby we can recover the GVF by setting the weights in such way that we recover the pointwise maximum across infinitely many points in x C. We can now sharpen this result to show that suffices to restrict attention to some finite subset of these points. For any given M Z and V Z define DSM(M,,N) be the class of functions represented by DSM whose 7-stack and B-stack have layers with M and / neurons each, respectively.
Theorem 5. There exists some M M. some N E ZN,, a finite set č Ç C, finite set B & B, and some n E DSM(M,N such that (1,,,, B) h for all B E B, E C. Moreover, this same of necessarily satisfies n (7, hA(7, () for all B E B and YodyEE C..
Finally, we reframe this existential result as an optimization problem; this will form the basis for the unsupervised training framework we develop in Section 5.
Corollary 6. Take the M, N. B, and Ć that Theorem guarantees must exist. Denote the parameters of DSM model with 0. Then, A is the unique solution of
max n EDSMM.
ΣΣ (7,
(7a)
JEC BEB
s.t. 17 (7, a²) sw V7 VY [n].
(7b)
We refer the reader to Figure 2 for an illustration of how. taken together, the results of this section permit us to learn good approximation of the GVP. In addition. we highlight that typical "universal approximation theorems" [35] apply over bounded input domains, whereas here C and B may be attain h without this assumption.
unbounded. However, the above approach shows that
5 Learning Generalized Linear Programming Value Functions
For context, we begin by describing a standard supervised training method to approximate the function h using a neural network with parameters 0. First, generate some training data set
5

---

4)
6)
Axft..P)
Auti P)
innal opproddrttoo
memrssmmnn appronination
conwes approsmmatio
good appros
Value for
Auf1.
Duality constraints
Weight sign constraints
Enough poins
Nalts
19:33
lwees lourd
good
approsimaaion
approsmmaiio
7
Duality constraints penalty torm
Enough data points
Figure 2: An illustration of how we learn a GVF, looking at slices along the constraint bounds (Top) and objective coefficients (Bottom). Given only data points B x C and no constraints, either (7b) or weight-sign, maximizing Enec EBES 17" 7 (?r,, B3 will yield a poor initial approximation. Adding constraints (7b) will force the function to be smaller than hΛ at certain "anchor" points which are distinct from the input data points, at which the function will still tend to be large. Adding the weight-sign constraints will force the function to convex in terms of the constraint bounds, and will therefore produce an approximation that lower bounds A. Theorem 5 then tells us that, with sufficiently many data points to start, we will eventually recover A directly.
Then, optimize our parameters 0 by minimizing loss function (such as an f2-distance) between the output of the NN with our data. Notably, this is an unconstrained optimization problem. However, data generation may be expensive: in general, we must solve an linear programming problem, LP('', B²)). for every training data point E [[D[]]
D: (17 (" ()))
5.1 An Unsupervised Learning Approach
Corollary 6 tells that we do not actually need labeled data to learn the GVF. Of course, there is trade-off here: directly applying the result requires somehow compute the sets B and C, and also requires solving a constrained optimization problem in (7) (as opposed to typical unconstrained learning problem). To address the first issue, we propose using two subsets D, Ç B and D. Ç C to use in lieu of B and C respectively, which may come from training data or be randomly generated; this further detailed for a specific application in Section To address the second issue, we introduce penalty term to the objective to model the constraints (7b) in a "soft" manner. This leaves us with the following unconstrained, unsupervised learning problem:
min EDSM((M..)
-
Σ Σ DEDeGEIM]
max(1/ - -
(8)
YED. SED,
where μ E R. is the penalty coefficient. We can motivate both of the alterations introduced above with the following corollary Theorem 5. To enforce the constraint 17" DSM(M,N),, take the positive (respectively, negative) absolute value of the weights for a nonnegative (resp. nonpositive) weight-sign constraint.
Corollary 7. Given any nonempty subsets D, C B and D. C C, there exists a sufficient large i such that A is an optimal solution of (8).
Note that, while (7) has AA its unique optimal solution, in general cannot guarantee that (8) has an unique optimal solution, meaning that we may recover an optimal solution that deviates from hy on points outside the training set. However, Corollary 7 ensures that any solution of (8) is at least as good as h at () E D. x DD! Moreover, in Section 5.2 we will provide computational evidence that a near-optimal solution of (8) is empirically good approximation of h. Corollary 7 also justifies why we elect to use an L penalty term in (8), rather than a smooth penalty or Lagrangian
In fact, because of Theorem 3, any solution of (8) is at least as good as hA at every point of [t(r, B) (7,8) () D. Ds).

---

multipliers. If we were to modify (8) to use an e² penalty term, for example, an analogous version of Corollary 7 need hold: roughly speaking, a is the function that satisfies most of (7b) at equality, whereas an l penalty term would tend to push optimal solutions away from the boundary of the feasible region of (7). We refer the interested reader [40, Chapter 17] for a detailed discussion of exact-inexact or smooth-nonsmoott penalty terms.
5.2 Penalty Coefficient Update Strategies
Now, we use standard techniques from nonlinear optimization [40, Chapter 17] develop a heuristic scheme for updating our penalty term μ., depicted in Algorithm 1. In practice, the optimization problem (7) might be numerically unstable. For example, we initialize μ4 to small value, then " (7, B) is weighed far more than the penalty term, and so the optimal solution will tend towards -oo. We resolve this by using upper bounds, u, on h as "tether" points. For each training data point, we choose a simple upper bound of the optimal objective (see Section and Appendix E for details).
the first term EEE.,
We parameterize our scheme on the penalty update strategy, which is perhaps the most important factor. A common choice would be the linear update strategy, which means μ is scaled up by constant factor / at each step, i.e., update(μ) effective "adaptive update" strategy where we update based on how many constraints (7b) the current solution 1/' satisfies. particular, update(p) (2 percentage cons satisfied) μ.
vp. However, we propose more computationally
Algorithm 1 Learning GVF with objective upper bounds procedure LEARNIGGENERRLLZEDDPPEEE De. Do, u, T, No. update)
2: Initialize 17
3: for t ..... - do
4:
1/- t- argmin Σ Σ (uy,3 77 1/ (7, E E pe max (1) EED.BED,
TED. [|[]]
M4+1 + update(u)) 5:
6:
Returnin"
Note that, since the minimization problem in line 4 of Algorithm is non-convex, we cannot guarantee globally optimal solution r/*+1. Therefore, in practice, we solve the minimization subproblem until some criterion is met, e.g., the gradient sufficiently small or we reach a prescribed iteration limit.
5.3 Guaranteeing an Under-Approximation
By Theorem 3, any feasible solution for (7) lower bounds the GVF we are attempting to learn. However, our methods laid in this section do not guarantee this property for two reasons. First, the penalty method treats the constraints (7b) as soft constraints rather than hard constraints, and thus they may not fully satisfied. Second, we are approximating the set C from Corollary 6 with a training set D., and therefore our solution may not provide a lower bound at other objective vectors y. To resolve this, we can scale the function down as much as needed to guarantee the constraints (7b), with the expectation that our learning method produces solution that is not too far off from being dual feasible. However, we can do better we only need to provide a valid lower bound for single objective y, which is often the case (see Section 6 below). In this way, can train a single DSM approximation and reuse it across many objectives by suitably postprocessing it for each. We describe this procedure in Algorithm 2.
Algorithm 2 Post- processru to guarantee the lower-bounding property
procedure POST- PROCESSING(C, Vp ,
2: th +- (c) E RPXN
3: for j - 1....,P. do
4: D 5 (1/ m/xx, ~
(0g) 2 at)
return th
7

---

6 A GVF-Based Heuristic for Two-Stage MILPs
As an application of the learning method we developed in Section 5, we propose a heuristic method for two-stage MILPs with continuous second-stage stage variables (4). The main idea is to replace each of the second-stage subproblems with the corresponding LPVFs from our learned function: that is, we our approximation to represent (d b² Thx² in (5) for each k. This yields fast heuristic for two reasons. First, our learned approximation is piecewise linear convex when restricted to a fixed objective, meaning that it can be efficiently modeled inside a larger optimization problem an LP [3]. Second, the number of variables of this I.P scales with the number of neurons in the DSM, typically much smaller than a second-stage subproblem L.P. In practice, this enables the heuristic to run faster than solving the LP relaxation of (5), despite maintaining integrality of the first-stage variables.
Given a learned DSM representing the function n denote by W w W the weights the constraint bounds stack, where W S and w W 2 0. For a fixed objective coefficient E C and the output of the objective-stack th (post-processed as in Section 5.3), we can model the set {cl ç 2 v/a (c, B)} as
{
DSM (c
3z s.t. 21 2 (WW3), 2+11 2 (W))) vi [M], < of AM Vi E [p]
Our heuristic is then to solve the following problem to obtain a solution for the first-stage variables:
x--0++ Σ
min 21 2t.
x* x* E (dt 8 - TT E [ x EX
RE[K]
Note that (9) is simply (5) with the LPVFs replaced by our learned model. Since 7 (c, 3) S (e for all e E C, C, the objective value of (9) is dual bound for the original problem. Once we compute optimal values of the first-stage variables x=, we can then recover the second-stage variable values by solving each of the second-stage LP subproblems independently with fixed x², yielding the full solution. Algorithm 3 describes the full method.
Algorithm 3 GVF-based heuristic for two-stage MILPs with continuous second-stage variables ]e]]K] (b*)KEKK] (1+) }kElK] V. ())
1: procedure CVFBAASEDHEURRSTICCCACCCCCCC
2: for 4 ,,...,K K do कx* PROCESSROC Φ)
3: ((x*)), [ ((* [k] + optimal solution of (9) with Wv, (Ødd }[E]K]
4: for + ,,..,, do
5: (z*) +- arg m fdt g x2,1| Ax < b² x x,2, 2 0}
return x²'
Computational Results
In this section, we computationally evaluate? both the approximation quality of the learning method described in Section 5 and the effectiveness of the heuristic for two-stage problems from Section 6.
We evaluate these methods on the uncapacitated two-stage problem, in which we first select n, facilities to open, and allocate each of n. customers to an open facilities. We consider two classes of instances, Euclidean and KG, both with n. = ny. In both cases, we take set of objective and right-hand side vectors from one instance for training and second, different, set from five instances for testing (more details are provided in Appendix C).
location (UFL) [54]. This is a deterministic
To produce the training data, we take all or some customer allocation costs from the UFL training instances as our objective coefficient dataset D... Then, for each such cost vector, we generate [10] points uniformly random between [0, 1] for our constraint bound dataset Dr. Thus, the total size of the training data is [[De] n 10]. all customer costs are selected for D., this is
Alll code for the experiments can be found at moogle-researee wtt.://aaarceeeeeeeeeeee/aaaaaea
com moogle-reseeree
8

---

[|]| - ne" nn / where I is the set of training instances. Note that we do not use the facility costs at all for training. To improve training stability, we normalize the customer allocation costs by their mean in the training data. For the training dataset, we choose an upper bound of the GVF to be 2, which an upper bound for the largest possible assignment cost the training dataset after normalization.
To learn each GVF, we run total of 40 iterations in Algorithm 1, each iteration, we solve (8) by performing 100 steps of the Adam algorithm [31]. For DSM, we select the model within the T itteaations that satisfies at least 98% of the constraints (7b) from the training dataset with lowest training objective function (8). Details of hyperparameter tuning for DSMs and DenseNets are provided in Appendix E. In addition to the numerical study for UFL, we include experiments on the Stochastic Capacitated Facility Location (SCFL) in Appendix D.
7.1 Learning Method
Arguably, we would expect that the lack of supervised data would make the Dual-Stack Model more difficult to train than a standard supervised learning approach, especially considering that it also has training constraints and convexity requirements. On the other hand, our theoretical results suggest that these same requirements can help the model take the general shape of a GVF, Indeed, we observe in Table that our approach produces model that is comparable or better than a standard ReLUU network (see Appendix E. for DenseNet) and Random Forest Regressors in terms of how well it approximates the GVE. Unlike with DSM, these baselines require solving an LP for each training point to produce labels. The number of LPs can grow large, though they can be solved in embarassingly parallel manner, and in the case of UFL we can use an efficient greedy algorithm given that the LP reduces to fractional knapsack. We report an posteriori metric, the True Relative Error, defined as the gap between the model and the GVF, i.e. (n)(,, 3) - h (7, 3)1/ max( 3), {)), averaged across all 7, 3 in the test set. The Lower Bound in Table 1 shows the percentage of constraints (7b) satisfied for either the training or test set.
We see that, on all but one instance family, we are able to train a DSM that attains a lower True Relative Error than both DenseNet and Random Forest. Moreover, the training times between DSM and DenseNet are roughly comparable. We also highlight that the Euclidean instances are relatively harder to learn than the KG instances; this is observable for all models.
Table I: Comparison between Dual-Stack Model and DenseNet in Learning GVE
Clas GVF
Duul-Stack Mudel
DesneNet
Randece Foent
250
155.3 30
4thh
25.71 5 5:1
166.11
1 %
13.4
611 5
KG
1.54
%
1439-27
1.54
5.15
100
7.57
33 9g
05
$8.0 &
1.17
2.34
39.29
$7.58
4141%
161.25
31,89
94.1
16.0%% 9:
3.38
200.11
31.25
335.00
39.16/5
Table 1 examines the capacity of the DSM model to learn GVFs. To illustrate the scalability of DSMs, we train the model on LPs of various sizes. We use the allocation cost vectors of all customers for De in all cases, except for KG 750 where we select 200 eustomers for D. due to memory limitations. Although training time naturally increases with instance size, both the True Relative Error and Lower Bounds remain stable for KG instances and exhibit only a slight increase in the Euclidean cases. This observation supports the scalability of the DSM approach.
7.2 Heuristic for Two-Stage Problems
We evaluate our heuristic on our generated UFL instances by comparing its performance against that of ttate-of-the-art open-source MILP solver, SCIP [20]. We compare with the best feasible solution found by the solver within the time limit specified in the column "MIP Solve Time (s)" in Table 2 for KG, or the optimal solution for Euclidean instances. For KG, even solving the LP relaxation for the full model can take a few minutes. On the other hand, despite being an MILP, solving the model (9) is very fast, often taking less than a second, particularly because we only require binary constraints on the first-stage variables. After solving this MILP, the second-stage solutions are recovered by simply taking the closest open facility. Denoting the objective value of the heuristic feasible solution by v" and the optimal value of (9) by W-hhich is a dual bound to the original problem due to our under-approximation guarantec- the Provable Gap is computed as (v" VV/v", which is an upper

---

bound of the true gap. The Gap to MILP is computed as (v" 0 where ö is the objective value of the MILP baseline. A negative value of Gap MILP means that the solution returned by our heuristic is better than the solution returned by SCIP within the time limit. We solve 5 instances from each class and report the mean and standard deviation for each metric across these selected instances in each class. When reporting time, we use ">' to signal the solver reaches a time limit. We also compare our method with a heuristic based on Benders Decomposition, which mimics the DSM heuristic except that we use Benders cuts instead of the GVF. For each instance, we first iteratively generate a number of Benders cuts for all subproblems, and then solve one MILP with the inclusion of all generated optimality cuts. For each UFL instance, we set the maximum number of Benders LP iterations to match the total number of facilities, while the time limit for solving the MILPs with cuts is fixed at minute. In the Euclidean case, the Benders heuristic was able to produce optimal solution for all instances tested. We observe from Table 2 that our approach produces significantly better solutions than our full model baseline for large KG instances, though not for Fuclidean ones. This may be because the Euclidean instances are more difficult to learn as observed in Table 1, both for DSM and the dense model. We also note that the Euclidean instances are much easier solve to optimality than the KG instances, meaning that a fast heuristic for them is of relatively lesser value.
Table 2: DSM Heuristic Solver on UFL Instances.
Instances
Salve
Provuble Cap
Solver Gap
Gap Benders
Robossation
Model
MILP
Benders Heuristc
3.5
0.020
D1301
21.34 0.16
12.55 0.30
11:56 0.01
5-43, (1:1
-10
63.5 0.7 92.1 + 0.5
KG
500
0.111
0.008
14455534 0.54
3.79 = 1.05
13.14 0.01
36,07 1.52
>050
750
0.313
+ 0.004
17.56 0.40
-55.4 1.34
16.25 a 0.01
>
5:00
189 + 3.6
100
0.01%
B1001
3:30
21.12
23.32
0159
0.30 440
0CM 0.001
Eudidian
<9..52
0.015
Conclusion
JIn this study, we provide a structural characterization of the GVF, inspiring an NN architecture and unsupervised method that approximate it well. Additionally, we utilize this framework to develop a fast heuristic method for two-stage MILPs with continuous secged-stage variables, effective for some large-scale instances. We will conclude this paper by highlighting two areas for future work, where we believe that the techniques presented in this paper could be sharpened or otherwise improved.
First, we believe that our training objective could be further improved. During training, we must balance two terms in our loss function: one that rewards fitting the data well, and another one that (softly) constrains the function to be below the true value function. Finding stable balance between these two terms appears to be one of the most challenging parts of training. We overcome this limitation by proposing an adaptive update method for the penalty, tuning the initial hyperparameter well, and proposing good stopping criterion. However, even with all these measures, we still observe occasional instability and believe that there is room for improvement, such as developing adaptive stopping rule.
A second direction for future work is to improve the generalization of our method to objectives not seen in the training set. While our theoretical results guarantee that the constraints in (7) are sufficient to produce a function that lower bounds the GVF, this may require an exponential number of constraints. In practice,
only enforce this constraint for those objective vectors appearing in the training data, which does give us lower bounding guarantee for arbitrary right-hand sides and objective vectors from outside the training set. We observe empirically that with sufficient samples, our method performs well on out-of-sample objectives, but we do note that our Test Lower Bound column in Table I differs from the Train Lower Bound column by a significant amount.
10

---

References
[1] A.A.M. Al-Saffar, H. Tao, and M.A. Talab. Review of deep convolution neural network in image classification. In 2017 International conference radar, antenna, microwave, electronics, and telecommunications (ICRAMET), pages 26-31. IEEE, 2017.
[2] A. M. Alvarez, Q. Louveaux, and L. Wehenkel. A machine learning barning-basedd approximation of strong branching. INFORMS Journal on Computing, 29(1):185-195, 2017.
[3] B. Amos, L.. Xu, and J. Kolter. Input convex neural networks. International Conference on Machine Learning, pages 146-155. PMLR, 2017.
[4] R. Arora, A. Basu, P. Mianjy, and A. Mukherjee. Understanding deep neural networks with rectified linear units. International Conference on Learning Representations. 2018.
[5] H. Bae, J. Lee, W. C. Kim, and Y. Lee. Deep value function networks for large-scale multistage stochastic programs. In International Conference on Artificial Intelligence and Statistics, pages 11267-11287. PMLR, 2023.
[6] J. E. Beasley, OR- URL: https:/hpeolleebnmee....uuu mastijbjjbbffoo.hmm http:///.poouu..eeeeeeeee/m////a Accessed in May 2024.
[7] C. Beck, M. Hutzenthaler, A. Jentzen, and B. Kuckuck. An overview on deep learning-based approximation methods for partial differential equations. Discrete and Continuous Dynamical Systems B, 28(6):3697-3744 2023.
[8] Y. Bengio, E. Frejinger, A. Lodi, R. Patel, and S. Sankaranarayanan. A learning-basedd algorithm quickly compute good primal solutions for stochastic integer programs. In International Conference on Integration of Constraint Programmiing, Artificial Intelligence, and Operations Research (CPAIOR), pages 99-111. Springer, 2020.
[9] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: A methodological tour d' horriizo.. European Journal of Operational Research, 290(2):405 2021.
[10] Beraldi and M. E. Bruni. A clustering approach for scenario tree reduction: an application to stochastic programming portfolio optimization problem. TOP, 22:934 949,499999111 2014.
[11] C. E. Blair and R. G. Jeroslow. The value function of integer program. Mathernatical Programming, 23(1):237-273, 1982.
[12] W. D. Cook and R. J. Webster. Caratheodory's Theorem. Canadian Mathematical Bulletin, 15 (2):293-293, 1972.
[13] H. Dai, Y. Xue, Z. Syed, D. Schuurmans, and B. Dai. Neural stochastic dual dynamic program- ming. In International Conference Learning Representations, 2022.
[14] Dumouchelle, R. Patel, E. B. Khalil, and M. Bodur. Neur2SP: Neural two-stage stochastic programming. Advances in Neural Information Processing Systems, 35:23992-24005, 2022.
[15] J. Dumouchelle, E. Julien, J. Kurtz, and E. B. Khalil. Neur2RO: Neural two-stage robust optimization. In International Conference on Learning Representations, 2024.
[16] Dupačová, N. Gröwe-Kuska, and Römisch. Scenario reduction in stochastic programming. Mathematical programming, 95:493-5111 2003.
[17] R. Z. Farahani, M. SteadieSeifi, and N. Asgari. Multiple criteria facility location problems: A survey, Applied Mathematical Modelling, 3497):6689-1009, 2010.
[18] M. Fischetti, I. Ljubié, and M. Simnl. Redesigning benders decomposition for large-scale facility location. Management Science, 63(7):2146-2166 2017.
[19] I.. Foulds. multi-commodiit flow network design problem. Transportation Research Part
B: Methodological, 15(4):273-22 1981.

---

[20] G. Gamrath, D. Anderson, K. Bestuzheva, W.-K. Chen, L. Eifler, M. Gasse, P. Gemander, A. Gleixner, L. Gottwald, K. Halbig. Hendel, C. Hojny, T. Koch, Le Bodic, S. Maher, F. Matter, M. Miltenberger, F. Mühmer, B. Müller, M. E. Pfetsch, F. Schlösser, F. Serrano, Shinano, C. Tawfik, S. Vigerske, Wegscheider, D. Weninger, and J. Witzig. The SCIP Optimization Suite 7.0. Technical report, Optimization Online, March 2020. URL http: html.
//www. www.ooptiiizaion pwteiiaaiiooooonnnneeeen online.
[21] A. M. Geoffrion. Generalized Benders' decomposition. Journal of Optimization Theory and Applications, 10:237-260, 1972.
[22] A. ShaffariiHHaighhee H. Ghaffari GhaffariHadiihheh Hadigheh, and T. Terlaky. Bi-parametric optimal partition invariancy sensitivity analysis in linear optimization. Central European Journal of Operations Research, 16:215-238, 2008.
[23] B. Hanin. Universal function approximation by deep neural nets with bounded width and ReLU activations. Mathematics, 7(10):992, 2019.
[24] H. He, H. Daume III, and J. M. Eisner. Learning search in branch and bound algorithms. Advances in Neural Information Processing Systems, 27, 2014.
[25] M. Hoefer. UflLib: A collection of benchmark instances for the uncapacitated facility location problem. URL:
Accessed in May 2024.
[26] K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5):359-366) 1989.
[27] B. Jansen, C. Roos, and T. Terlaky. An interior point approach postoptimal and paramet- ric analysis in linear programming. Delft University of Technology. Faculty of Technical Mathematics and Informatics, 1992.
[28] H. Jia and S. Shen. Benders cut classification via support vector machines for solving two-stage stochastic programs. INFORMS Journal on Optimization, 3(3):278-297, 207788299,,,1111..
[29] H. Jiang, Chen, Y. Shi, B. Dai, and Zhao. Learning to defend by learning to attack. In International Conference on Artificial Intelligence and Statistics, pages 577-585. PMLR, 2021.
[30] K. Julien, O. Janosch, and R. Walter, bobblem-drieer scenario clustering in stochastic optimiza- tion. Computational Management Science, 20(1). 2023.
[31] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
[32] N. Kong, J. Schaefer, and B. Hunsaker. Two-stage integer programs with stochastic right- hand sides: a superadditive dual approach. Mathematical Programming, 108(2):255-266, 2006.
[33] E. Larsen, F. Frejinger, B. Gendron, and A. Lodi. Fast continuous and integer L-shaped heuristies through supervised learning. INFORMS Journal on Computing, 36(1):203-223, 2024.
[34] J. Lee, S. Bae, C. Kim, and Y. Lee. Value function gradient learning for large-scale multistage stochastic programming problems. European Journal of Operational Research, 308(1 (08(1):321-335 2023.
[35] M. Leshno, V. Y. Lin, A. Pinkus, and S. Schocken. Multilayer feedforward networks with nonpolynomial activation function approximate any function. Neural Networks, 6(6): 861-867, 1993.
[36] T. L. Magnanti and R. T. Wong. Accelerating benders decomposition: Algorithmic enhancement and model selection criteria. Operations Research, 29(3):464-484, 1981.
[37] T. P. Nagarhalli, V. Vaze, and N. K. Rana. Impact of machine learning in natural language processing: A review. International Conference on Intelligent Communication Technologies and Virtual Mobile Networks (ICICV), pages 1529-1534, IEEE, 2021.
12

---

[38] V. Nair, D. Dvijotham, I. Dunning, and O. Vinyals. Learning fast optimizers for contextual stochastic integer programs. In UAL, pages 591-600, 2018.
[39] V. Nair, S. Bartunov, F. Gimeno, I. Von Glehn, P. Lichocki, I. Lobov, B. O' O'Donoghue, N. Son- nerat, C. Tjandraatmadja, P. Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13344 2020.
[40] J. Nocedal and S. J. Wright. Numerical Optimization. Springer, New York, NY, USA, 2nd edition, 2006.
[41] V. Prochazka and W. Wallace. Scenario tree construction driven by heuristic solutions of the optimization problem. Computational Management Science, 17(2):77-3307, 2020.
[42] R. Rahmaniani, T. G. Crainic, M. Gendreau, and W. Rei. The Benders' decomposition algorithm: literature review. European Journal of Operational Research, 259(3):801-817 2017.
[43] K. Ralphs and A. Hassanzadeh. On the value function of mixed integer linear optimization problem and an algorithm for its construction. COR@L Technical Report 14T-004, 2014.
[44] W. Römisch. Scenario reduction techniques in stochastic programming. In International Symposium on Stochastic Algorithms, pages 1-14. Springer, 2009.
[45] C. Roos, T. Terlaky, and J.-P. Vial. Interior point methods for linear optimization. Springer Science Business Media, 2005.
[46] R. Schultz, L. Stougie, and M. H. Van Der Vlerk. Two-stage stochastic integer programming: survey. Statistica Neerlandica, 50(3):404 1996.
[47] Z. Shao, J. Yang, C. Shen, and S. Ren. Learning for robust combinatorial optimization: Algorithm and application. IEEE INFOCOM 2022-IEEE Conference on Computer Commu- nications, pages 930-939. 9000999.220 2022.
[48] J. Shen, X. Chen, H. Heaton, T. Chen, J. Liu, W. Yin, and Z. Wang. Learning a minimax optimizer: A pilot study. In International Conference on Learning Representations, 2020.
[49] J. C. Smith and Y. Song. A survey of network interdiction models and algorithms. European Journal of Operational Research, 283(3):797-811, 2020.
[50] Y. Tang, S. Agrawal, and Y. Faenza. Reinforcement learning for integer programming: Learning to cut. In International Conference on Machine Learning, pages 9367-9376. PMLR, 2020.
[51] Z. C. Taskin. Benders' decomposition. Wiley Encyclopedia of Operations Research and Management Science. John Wiley & Sons, 2010.
[52] O. Tavashoglu, O. A. Prokopyev, and A. J. Schaefer. Solving stochastic and bilevel mixed- integer programs via generalized value function. Operations Research, 67(6):1659-1677, 2019.
[53] A. C Trapp, O. A. Prokopyev, and A. J. Schaefer. On a level-set characterization of the value function of an integer program and its application stochastic programming. Operations Research, 61(2):498-5 -11, 2013.
[54] V. Verter. Uncapacitated and capacitated facility location problems. Foundations of location analysis, pages 25-37, 2011.
[55] Y. Wu, W. Song, Z. Cao, and J. Zhang. Learning scenario representation for solving two-stage stochastic integer programs. In International Conference on Learning Representations, 2022.
[56] Y. Xiong and C.-J. Hsieh. Improved adversarial training via learned optimizer. In Computer Vision-ECCV 2020: 16th European Conference, pages 85-100. Springer, 2020.
[57] S. Zaourar and J. Malick. Quadratic stabilization of benders decomposition. 2014.
13

---

A Complete Proof for GVF Representation Theorem
In this section, we provide the complete proof for the GVF Representation Theorem (Theorem 2). The following lemmas are inspired by [11, Lemma 6.1, Theorem 6.2 and Theorem 6.3]. These results from Blair and Jeroslow are originally stated for the value functions of integer programs. We borrow their techniques and extend these results for the GVFs. In the following proofs, use English letters, e.g., b or c, to indicate a fixed vector, while Greek letters, e.g., B or 7, are used to signal inputs of some functions and can vary.
A.1 Lemma
Lemma 8 states that there is a finite set D of improving directions: given suboptimal feasible point I E X (3), we can improve æ by moving along some r E D. Notably, the set D depends only on A and not y or B, thus setting basis for constructing the function hA-
Lemma 8. There exists finite set D C R" such that, for any 3 E B, Y C, and X(8). exactly one of the following is true:
7 -hha,, or
2. > and r E such that x + er E (8) and 7 rr r
Proof. Let [B1, B2... B&} C (=)x))xn be the set of all full rank submatrix of [A" ITJ", Since B, is full rank, there exists E R" and ||:]12 = I such that for every E R, tr; is solution of the system Brr = O. Let = [ e [+]]] We show that the finite set D satisfies the condition of Lemma 8.
We first show that, for any B, every extreme ray of X33) (normalized so that its - is one) belongs to D. Let be an extreme ray of ((3). Then, by definition, v must satisfy at equality exactly n inequalities from Av S and 0. Therefore, there exists a matrix B, such that B,v and thus v E D.
Consider E X(3) a feasible solution of LP(7, 8). Let P and V denote the set of extreme points and extreme rays of (3) respectively. By Carathéodory's Theorem [12], for any feasible point x X(3,, there exists {Ap PEP where Epep Ap
and (Pe Z 0]eev such that x = Eper App + Evev Pr there exists v' V such that Per > and y Par > 0, then x cannot be a optimal solution of LP(r, (3) because x - p has a smaller objective and -o' E D satisfies the second condition of Lemma 8. Without loss of generality, from on, assume that x = =Eper ApP.
Since z is a feasible solution, æ either optimal solution of LP( B) or not. If x the optimal solution, then 7 x ((7, (). Otherwise, by definition of B and C, (>,, B) has basic optimal solution p" * x such that 7 pp" <.. Since p' - x Eppp" App" (1 Ap )p", we have p" E span(D); D). By our choice of D, if E D then -r E D, thus there exists r E such that y and Be and E such that x + Er X(3).
A.2
Lemma
Using the improving directions from Lemma 8, Lemma 9 produces finite set of extreme rays that generate the objective coefficient space C. By this lemma, the value h ha(7, 3) can always be written conic combination of (ha(Cip 3) )
Lemma 9, There exists a finite set C = {ci, (2..,,.....co)) cQ] C such that for any e C. be B.
(1 hh (1) E cone
..... ..... (n... (Aa((g)1) 11)
CQ
(10)
Proof. Let D the finite set satisfying the condition in Lemma 8. For every subset R C D, we define
C(R) (ce Cl c. 20r c-220
R}.
14

---

Since C()) is polyhedral cone for every R C D, we denote E(R) to be the finite set of extreme rays of CR). We show that C URCDE(R)) and denote its elements as {cr ................................ cQ) satisfies the condition stated in Lemma 9.
For any 7 C and x². directions at x*
B, since (n, 3) has finite optimal solution, there must exists x² such that h(., 3) = 7=xx"""""... Let Rº == {r E D de > O, x² ter E ( be the set of all feasible improving
Claim 1: By our choice of Rt, we must have y E (.R)). By contradiction, suppose that y & C(R²). then there must exist r* E R such that r- 0. However, by definition of R" there exists e <> 0 such that x" + er" is a feasible solution of LP
addition, we have ry (x* + er") y' + ey r <y.x"" which contradicts the fact that x² is an optimal solution of LP 8). Hence, we derive that y E C. Moreover, since C(R*) is polyhedral cone whose extreme rays ((R)) belongs C' by our construction of C, we have there exists a 0 such that EgElQ] OgCq = 7
Claim 2: For every E C(R)), we have h(c, .3) e-x" Since x² (B), have hic, (8 < c-x' Moreover, because x" is optimal solution of LP(7, 8), we also have - 2 O for every r E lt" By contradiction, suppose there exists C(R*) such that h(c, B) not an optimal solution of LP 3). there exists e > 0 and r D such that x + er E ( and c-r < 0. However, since x + er (3), we must have r E Rº, and by definition of (R)) every C. E C(R)) must satisfy c-r 2 0. which contradicts with our conclusion that c < 0. Therefore. h(c, () = c x² for every c C(R*).
x². By Lemma and x² is
Finally, we have that
Σ Q
agh(ce, 9)
Σ TE[2]
Oggy x²
Σ TE|
xx = 77.8" -1(r,
This is because from Claim 7 E CR)), without loss of generality, we assume that 0ig = 0 for every Cq & F((R)). Therefore, either have Og2 0 or h(cg. 3) Cg x=. Thus, Eye[qi a; B)
Exe[o] 042y x².
A.3
Lemma 10
For ease of notation, denote go (3) = Ac 3) for every q [Q]. A function In is obtained from A by fixing the objective coefficients to Cg. Therefore, (3) is an LPVF (parameterized by constraint bounds), and thus convex piecewise linear function.
While Lemma 9 shows that A can be represented by a finite set of LPVFs {gy [ge)) the linear combination coefficients of such representation depend on b B and E C and unclear how to obtain. The following Lemma 10 gives more explicit characterization of the linear combination coefficients.
Lemma 10. For every 7 C and B B, we have
hA(r,3) = max
Σ (3)
&E[QI
Σ
(LPa(r,))
CgCg = y
2 0.
Proof. Let.r" be the optimal solution of LP(y,, B) and x² be the optimal solution of LP 9) for every i [[]] Since x* e ((3) is always feasible solution of LP 8), we have
x- 2 c of Vy E [Q]
Therefore, for every a such that EqERQ1 CgCo 7,, we have
h( B) Σ a,ca" >
Σ a; I
Σ agg:( iE[N]
SE[N]
where the first equality follows Claim 2 of Lemma Combined with the existence of a in Lemma derive that ( B) max.20 m [E
(8) EgE(o] agcy = 7}.
D
15

---

Since (L 5)) is linear program, for every ", S, there must exists at least one basic feasible point that an optimal solution. Hence, there exists a maximizer a (n, 3)) that has least N n elements equal to 0 (non-basic variables), and at most n non-zero elements (basic variables). The vectors of corresponding to the basic variables generates a cone. Another way to view Lemma 10 is that, to find h(>, (8), we need to find the cone containing that maximizes Cie[M] (.9((3).
A.4
Lemma 11
The next lemma shows that the optimal basis of (I.P.11) (7,8)) remains the same when y varies within the cone defined by that basis.
Lemma 11. Let E B and e E C be fixed. Without loss of generality, we assume that Eg= Cg where o > and the correspondingg C* = [c1, , Cnl is the optimal basis of (c, for any a,...., On 2 0 andd Zq=1 Cg the basis C is also the optimal basis of LP LPa(7: (7,,b)
( b). Then
Proof. By the hypothesis of the lemma and by Lemma 10, we have:
ha(c, b) = Σ Eathalee ooha(e,, b).
Since ha (7, b) a concave piecewise linear function and 7 = Ei= a;d, we have
ha(7,b)= = M Σ
Oig 1all1 Cgp b)
(b).
We will show that h(7, b) = =E (ggg(b) for every Y E cone( Since hA is linear with respect to 7 only need to prove that h(v, > (b) where y == En AgCa conv(C). By contradiction, suppose that there exists 7" E , ha b) and ha(r", b) > En= Xigr. c ||a so that c' E conv(C). By contradiction hypothesis, we have ha(?", (b) > ha(d, b). Let d 7 c, and consider the function ((t) h ttd, b). Since ((t) is concave and ((1) > ((t)
Let c' =
for E [0, 1), ((t) is a linear function on [0, 1]. However, because is an interior point of conv(C),
there exist > 0 such that d' ed CCnv(C) and ((-c) I(0) c(((1) I(0)), which contradiet
the concavity of b). Therefore, we have
h(y, b)
Σ (b). 9=1
Moreover, because the optimal solution of LPa b) is 0g = 1, aj = -A- # q. C* is also the optimal basis of LP (Cg. b). Thus, C* is the optimal basis LP (n b) for every a; 2 i [n]] O
A.5 Theorem
The previous Lemma 11 implics that for a fixed we can partition the finite set of Lemma 9 into subsets of size n, denoted pd (Ct,....
such that
1. C U cone where the interiors of cone are mutually disjoint, and
2. If y E cone(C.)) then C is the optimal basis of (Y,(y,)).
Since C'ss finite, there can only be finite number of such partitions. Thus, we can associate each 3 E B with partition of C' and group the vectors of B into groups of constraint bounds vectors with the same partition.
GVF Representation Theorem: For a fixed matrix E Rm there exists a set of P piecewise linear functions {Fp R +ROPP and piecewise linear convex function G. R. + R. such that:
ha(7,8) max pE|p
(F,(1) Vy EC, E.
16

---

Proof. We will construct the function (1, 3) as follows. Let [B...... Bp} be the partition of B such that, for every p E [P] Bp contains every constraint bounds vector b with the same partition of C from Lemma 11, i.e., pe pb if and only if b², b²2 E By for some k. Note that P is finite because C is finite. Furthermore, we denote pp ,CT,..... ..... C.p be the partition of associated with the set Bp.
Note that C is invertible since it comes from the basis of LP LP bp). Let F9 RR + R be such that
[F(1))B 1 -
[[(OB) (1(C8) Ml
if cg Cp otherwise.
In addition, let G R - R be defined as
G( (0)
which is convex piecewise linear since each gi an LP value function. By our choice of Fp. for any 7, we have (()) 2 0. Furthermore, let a Fp(r), we also have Σ Cy 7. Thus, Fp(7) is a feasible solution of LP (3) for every E C, B E B, and [P]]
By Lemma 10, have
max pE|P1
(F)())
B Complete Proofs of the GVF Unsupervised Learning Theory
B.1 Proof of Theorem 3
Theorem 3. function TA E H(A) has the following properties:
1. nA(T.)) is piecewise linear, convex, and monotonically decreasing for every fixed 7 E C.
2. na(; (3) is piecewise linear for every fixed 3 E B.
3. nA(7.3) & B) every fixed E and y E C.
Proof. The properties of function 7) follows by the choice for activation functions, weight- signed and output constraints.
1. (a(c,)) is linear since the at every layer of the constraint bounds stack, we apply linear transformation and activation that is also pieceiwse linear. Since maximum or non-negative linear combination of convex functions is convex, 7) (c..) is convex with respect to the constraints bound. addition, the function is monotonically decreasing since the first layer of the constraint bounds stack has non-positive weights.
2. Similarly, because of linear transformations every layer in the objective stack, the function nA(-,b) 6) with a fixed is piecewise linear.
3. For every fixed E C, (c, :) is convex piecewise linear function. Therefore, (c, can be written as maximum a finite number of linear function. Let [ 3) = maxtetr3 (33T (y/)). Moreover, by the weight-singed constraint of the first of layer of the constraint bounds stack, we have y < 0. In addition, since 7) E H(A), we have that maxiejuy
(a') (at) (v)) S e; for every E [n]. Therefore, each y is feasible solution of (2). By linear program weak duality, we have ma(c, (3) < ha 8). Since the argument
applies for every e E C, we derive 71(7, 8) < hA(7, 8) for every $ E B and E C.
17

---

B.2 Proof of Theorem 4
Property& 3 of Theorem relies the linear program weak duality. We will show that the inequality in
Property 3 (Theorem 3) is indeed tight.
Theorem 4. For any fixed A IR hA E H(A,, and moreover ha is pointwss larger than all other elements of (()..
Proof. By the GVF Representation Theorem (Theorem 2), there exists continuous piecewise linear functions { [Fi]-= and convex piecewise linear function G such that ha(7; (3)
max G(())) The objective stack can model exactly any continuous piecewise lin- ear function. Therefore, with sufficient layers and neurons, can model the functions {Fi)== exactly. Moreover, as shown in Theorem 2, each component of the function G is LPVF, and thus piecewise linear convex function with nonpositive slope. On the other hand, the constraint bounds stack with weight-sign constraint can model precisely any convex piecewise with nonpositive slope. Hence, with sufficient layers and neurons, it can also model the function G exactly. Thus, hA H(A). In addition, by Property 3 of Theorem 3, every function in A is upper bounded by hA.
B.3 Proof of Theorem 5
Theorem 5. There exists some M E EN,, some N E2N, a finite set C Ç. C, a finite set Ç B, and some of E MSM,,N) such that (/;, B) = h (y, for all B E B, E Moreover, this same of necessarily satisfies 1/ (7, = hal%, B) for all B B and y E C.
Proof. Let C' C {cI, fci...., cQ} } be the describe in Lemma 9. Then for every cone generated by distinct vectors in C, we pick an arbitrary interior point, and denote the set containing every such interior points as C". Then, we construct a finite set struct B in a similar way. For every cone generated by distinct vectors in {a²,... aa j",,0 et where el , e E Rd denotes the unit vector, we pick an arbitrary point, and denote the set containing every such interior points as B'. We then derive B == {a ...., aa, .e.,..,, em)) U B'. The GVF Representation Theorem (Theorem 2) proves existence of functions {Fp) and to model A.. Since these functions are piecewise linear, we denote fn as the number of pieces of Fp for p E [P] and y as number pieces of G. We then pick features such that the 7-stack of the DSM can represent every piecewise linear function with most fi..... fp pieces. Similarly, for the B-stack, we pick features M such that the stack can represent every convex piecewise linear function with at most 9 pieces."
C' as the union of and C². We con-
Let n E N, and 3) ha(2, 3) AB E B, E C, we show that 1/ (7,7)) ha(7, B3 VB E B.y E C. For a fixed e E C, the function (f B), by Property 2 of Theorem 3, is convex piecewise linear function. Moreover, 7'(c, 53 - (c, B) for every 3 E B. By our choice of B, r/(c,, () halc, 3) at more point than the number of piece that (c, 3) can have. Since 1/ (c, (e, 3) S Ma(c, 3) VB E B and i/(c, B) is convex, we have v/ (c, hA B). Hence, we have v/ (G. 3) 9n (3) for every a E [Q], 8 B.
By Lemma 9, a can be represented by conic combination of (9r (3)) By our choice C. The function of equal h at more points than the number of pieces it can have. Thus n B) h (1 for every B E B and 7 E EC
B.4 Proof of Corollary 6 and
Corollary Take the M, N, B, and C that Theorem 5 guarantees must exist. Then, hA is the unique solution of (7)
Proof. Theorem implies hA E DSM(M.N).. By Theorem 3, we have that ha 9) 2 (,,,, for every 1) satisfies (7). Finally, Theorem 5 shows that we can represent hA through set of point B and C. Therefore, hA the optimal solution of (7).
Such features exist because construct a NN's architecture with wide hidden layer.
18

---

Corollary 7. Given any nonempry subsets D, E B and De E C, there exists sufficient large p. such that A is an optimal solution of (8).
Proof. The Corollary follows from [40, Theorem 17.3] on local minimizer of nonlinear program with non-smooth penalty function and the fact that h, is the optimal solution of (7).
C Uncapacitated Facility Location
Uncapacitated facility location (UFL) [54] is a classical, widely-applicable problem with the goal of deciding which of n, "facilities" to open (warchouses, plants, equipment, etc.) while taking into account a of n. "customers" that are allocated the open facilities. This can be interpreted deterministic two-stage problem: in the first stage, we select a subset of facility locations to open, and in the second stage, we assign each customer single open facility, while minimizing the costs of opening facilities plus customer allocation. Formally, the problem is as follows:
Σ Jan + Σ
Σ
min
sE[n,]
iEInyl JE[nal
Σ Vi =1 1=1
vj E [me]
Zij S yi
vi E [nyl.j E [nc]
Zij
vi
[nyli E [nc]
y1 E {0,1}
[ny]
where n and n, are the number of facilities and customers respectively. Note that the second-stage variables implied integer variables, i.e. if y" is integer, then there exists optimal solution (x*, """""" such that x² is integer. Therefore, we can effectively treat the second-stage variables r as continuous variables.
We consider two sets of benchmark instances:
Euclidean, in which generate facilities and customers uniformly random in box (0, 1J2 using Euclidean distances as customer costs, with sizes n = ne E (100, 200, 300}; and
KG, which are the symmetric Koerkel-Ghosh instances from the UFLLIB benchmark set [25], with sizes ny n. E {250, 500, 750].
For Euclidean UFL instances, we generate one instance of Euclidean for training and five instances for testing. In the KG set from UFLLIB, we use first instance from the class A instances (a1) for training and test on the class B instances (classes and B differ in how the costs were generated).
D Stochastic Capacitated Facility Location
The Stochastic Capacitated Facility Location (SCFL) problem is a variant of the traditional facility location problem where decision- occurs under uncertainty regarding demand other param- eters, and facilities have limited capacities. SCFL problems are often modeled as two-stage stochastic programs. In the first stage, make decisions involve selecting the facilities open, committing to fixed setup costs. the second stage, given the realized demand, the model assigns customers to open facilities, ensuring capacity constraints respected while minimizing assignment costs. The problem can be formulated as follows:
Σ fin +
Σ ps Σ
Σ Casly
minz.y
1E[my]
SES
(E[Rs] sE(jn_]
Σ iE[ny]
ztjz 2 dz.
Vj E Us E
19

---

Σ 5 4.34. jEIndl "i 2 0, y/ E (0,
Wi [ngl
Wi ee Imyl E V vi Ei [my]
where, similar to the UFL case, n, and n. denotes the number of facilities and customers, respectively, In addition, SS is the set of all scenarios and ps denote the probability of the scenario 8. Moreover, we denote Si as the fixed cost of opening facility i, cg as the assignment cost per unit from facility i to customer j in scenario s, dž as the demand of customer j in scenario and as the capacity of facility i.
A major practical difference from UFL is that we can no longer decompose the problem over customers, due to capacity constraints that link all customers. However, this stochastic problem has scenarios that we decompose over, where both the demand and assignment costs can vary. Here, we have n Ny variables in each subproblem, whereas in UFL we had ny variables per subproblem.
To generate SCFL instances, we take deterministic instances from the OR-Library [6], and generate 50 scenarios by randomly modifying both the demands and unit costs be (V,,, σ) where j is the original value and a is drawn from (d. (00.1,, Ju, 0.2j)), resampling any negative costs. We consider all scenarios be equally likely, i.e., Ps- [ST We use 30 samples for Dj- We perform the experiment of learning the GVF function for SCFL in Table 3. We conduct the training on cap61 and testing on cap62, with 16 customers and 50 facilities.
Table 3: Comparison between Dual-Stack Model and DenseNet in Learning GVF.
Class GVF
Train Time
Trur Md. Erre
Trais Lever Board
Text Loner Bound
Data Labd Timee
Trais Tine
True Rdl Brver Traai Time
Trus Ret Erne
SCFL
200.99
6.75%
95.06
11.2%%
41:31
92.77
7.55%
While the description of UFL and SCFL are similar, the GVF of SCFL is more complex than UFL's. An important difference here is the feasibility of the right-hand side. For UFL, any vector in the unit-box domain is feasible. However, it is not the case for SCFL,, e.g., when demand is greater than supply. Thus, in learning the GVF, must take into account the possibility of infeasible right-hand side vectors. For the experiment in Table 3, we model the infeasible region by introducing right-hand side vector with 0 supply and positive demand the training data. The approximation of the value function is then used to solve the SCFL problem approximately.
Table 4: DSM Heuristic Solver on al SCFL Instance.
Inotanres
Sulve
Provable Gap (%)
DSM Heartstic Selver
Gap MILP (8)
Gap to Bemlers
Full Model Selver Relovation Sulve Time (s) Sulve Time (6)
Benders Heuristi Solve Time (s)
SCFL
2.29
E Details on Numerical Experiments
For comparison of the performance between DSM and DenseNet in learning GVF, we perform parameter tuning for both models in terms of model architecture, dropout and learning rate. We train both of these models on a single GPU. With DSM, for the 3-stack we perform training with 2, 3 layers, each with 32, 64 neurons. The activation of every layer is max-pooling with window of size 5. For the y-stack, we also train with 2, 3 layers each with 32, 64 neurons, except the size of last layer is 128, 256 respectively. In addition, to avoid vanishing gradients, we use a composition of GeLU and ReLU during training only. The final layer of 7-stack is then reshaped to 4 x 32 or 4 x 64 to match the shape for the output of 8-stack. The dropout is only added in the last layer of the DSM and its parameter is chosen among {0.02, 0.03, 0.04]. With DenseNet, we also train the model with 1, 2, 3 layers, each with 32, 64 neurons. Dropout is added in every layer of the DenseNet and its parameter is chosen among (0.1, 0.2, 0.3). The learning rate of Adam for both model is selected from {10-2, 10
10 10-4). Table 5 summarizes the best configuration for each models.
Another aspect in learning GVF using our unsupervised framework is the choice of penalty l update function (see Algorithm 1). We also want to answer how the quality of the upper bound at every training data point affect the learned function. As we can observe in Table and 6 that the quality of
20

---

the learned function depends more on how we update the penalty term more than how good the upper bound is.
Table NN Architectures and Learning Parameters for DSM and DenseNet
Dual-Stack Model
DenseNet Dropout
Instances
Model
Dropout
Learning Rate
Model Are.
Learning Rate
250
32).
N
32, 128
0.03
le-3
64]
0.1
lc-3
KG
500
M
64]. N
64, 256
0.03
le-3
[128. 128. 128]
0.1
le-3
750
M N
[61, 256
0.03
lo-3
[128. 128, 128]
0.1
le-3
100
M
32]. N
[3, 128
0.03
lc-2
[64, 64, 64]
0.1
le-3
Euclidean
200
64 N
664, 256
1e-2
[128, 128]
300
M 64 N [64, 256
0.03
le-2
[128. 128, 128]
0.1
le-3
Table 6: Comparison of update methods and upper bounds for GVF Learning on KG-sym 250
upper bund i 2.0
upper bound = 100.0
uppax hourd uptinall valie rel abs loss
apper bward in optimal valic tree emor
urivourd
Toons saticted
tite emor
Pcoms sutsfted tree sel ecro
Pooes satisted
Toons satisted
fcous satletted
the rel eroor
update
95%1
100,09
adngche updane
99.70% 1001 0098
3.01% 4 1756
99 614
74 221
2,49% 4 AM9
100,00%
100:008
12 1445
12 1414
98.88% 1000 M095
4,805 5 N.455
92,428 99 90.66R
3.03% 4.15%
Table 7: Comparison of update methods and upper bounds for GVF Learning on Euclidean 100
upper hound
upper
upper
upper optinall satiuled
2
lisear upditt
55 5075
$7.380 $7.30%
65. 65.43%
39.30%
99.805
59 5016
90.00%
99/06%
100/000
$9. 30%
82.81%
64.75%
99: T0PS 100.00%g
65.45%
62.95%
97. 70%
42 2116
81.79%
21.36%
adagtive updiste
F Dual-Stack Model for Non-Standard LP Formulations
Table 8 describes the necessary changes to the DSM in the case that the LP is not in standard form. Alternatively, one may simply convert the LP standard form.
Table 8: Alterations the architecture for LPs not in standard form
Linear Program Constraints
DSM Weight-Sign Constraints
Unsupervised Training Penalty Function
Ar <
Nonpositive first layer of J-Stack
None
Ar 2
Nonnegative first layer of 9-Stack
None
Aar
No sign constrannd first layer B-Stack
None
C R
None
" YED, Enejo max ( 76
R
Nonc
" LLYED Lietal -mxxf (7,)))))) "EEe, Engn (12(7.0")
Jr C IR"
None
21

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
We would like to refer to Section 4, 5, 6, and 7.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We would like refer Section 7.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
22

---

Justification:
We would like to refer to Section 4, Section 5, Appendix A and Appendix B.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Ys]
Justification:
We would like to refer Section and Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
23

---

Answer: [No]
Justification: The main contribution of the paper lies in the theory and methodology for learning GVF. All algorithms and details on experiments are presented in the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips.. ec/
Polncyy))) for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips.. cc/pcc//lcc wcc/pbllc//eeec wtwgggiiidcccsssae
asionPolicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We would like to refer to Section and Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We report standard deviations in our results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We would like to refer to Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https / /ttp/enuripp.../ wwwpeurrp..ccppppplpeeeee httpppaliic/tiitaiiiiiieaeeeeeee
Answer: [Yes]
Justification:
We have verified that we follow all items in the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper focus on theoretical properties and learning a mathematical object
(the generalized LP value function), which does not have a direct societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
25

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We study the theory of learning GVF and conduct the experiments synthetic data, which poses no risks for misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recogmize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
benchmark instances from UFLLIB, which are properly cited in the paper. These assets are not re-released with the paper.
Justification:
The only existing asset that
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswi twwode.hco....c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
26

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our study does not involve crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our study does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "QZilMcrKU2", "reviewer": "Reviewer_yPT2", "summary": "The paper presents a novel learning method for the Generalized Linear Programming Value Function (GVF), which models the optimal value of a linear programming (LP) problem as its objective and constraint bounds vary. The authors develop a neural network architecture, the Dual-Stack Model (DSM), that can efficiently approximate the GVF. This model is characterized by three properties: it provides a true under-approximation of the value function, is input-convex in the constraint bounds, and is trained using an unsupervised method that does not require computing LP optimal values. The paper also introduces SurrogateLIB, a library of MIP instances with embedded ML constraints, and demonstrates the effectiveness of the proposed method through computational experiments. Additionally, the authors develop a fast heuristic method for large-scale two-stage MILPs with continuous second-stage variables.", "questions": "How does the performance of the DSM scale with the size and complexity of the LP problems?\nCan the unsupervised learning approach be extended to other types of value functions or optimization problems?", "limitations": "The paper does not provide open access to the code or data used in the experiments, which limits the ability of other researchers to reproduce and build upon the results.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides a strong theoretical foundation for the GVF and its representation as a neural network, ensuring the model's structural properties align with the GVF. The Dual-Stack Model is a novel neural network architecture specifically designed for the GVF, which could inspire future work in similar areas. The method's ability to learn without the need for expensive LP solutions during training data generation is a significant advantage, especially for large-scale problems.", "weaknesses": "While the paper shows promising results, it is unclear how well the method generalizes to other types of optimization problems beyond the tested instances. There is limited comparison with existing methods for learning value functions or solving MILPs, making it difficult to assess the relative advantages of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. Please see the global rebuttal for our response on the limitation of the computational results raised in the “Weaknesses” section. We hope that it addresses your concerns regarding how our approach generalizes to other types of optimization problems, and regarding how it compares with other existing methods.\n\nRegarding the questions:\n\n* **Scalability**: We study the scalability of our method in Table 1, in which we vary facility location sizes from 250 to 750 for the KG instances and from 100 to 300 for the Euclidean instances. We highlight that these larger instances can be quite difficult: e.g., the LP relaxations of KG 500 and 750 take 6 min. and >15 min., respectively, to solve without decomposition. While training time of course increases with instance size, both the True Relative Error and Lower Bounds do not deteriorate in the case of KG and increase slightly in the case of Euclidean, which is evidence that DSM scales well. We will add a brief discussion on scalability in the paper.\n* **Extending the unsupervised learning approach**: Our unsupervised learning method is tightly linked with the theoretical structure of the GVF, in particular via Corollary 6. Therefore, applying this to other value functions would require investigating their structure, which is somewhat orthogonal. For example, an immediate direction could be to build an architecture for MILP value functions based on its subadditive properties. This would be more challenging, but we hope that our work could inspire further research in this direction.\n\nThe reviewer also mentions access to code as a limitation. We would happily publish the code for the model, method, and experiments upon acceptance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7wDzUbtSak", "reviewer": "Reviewer_bRXK", "summary": "### Summary\n\nTraditional LP Value Function (LPVF) represents the optimal value of a linear program as a function of its parameters, typically objective coefficients and constraint bounds. It is piecewise linear and convex, often used in sensitivity analysis and parametric programming. However, computing the LPVF can be computationally intensive and limited in capturing complex dependencies. The Generalized Value Function (GVF) introduced in this paper extends the concept of LPVF by modeling it as the maximum of bilinear functions, capturing more intricate interactions between parameters. \bAnd the approach is implemented through neural networks.", "questions": "- What are the detailed advantages and disadvantages of GVF compared to LPVF across various aspects?\n- Why were other related studies not used as baselines in the experiments? Is there a justified reason for this omission?\n- Why were the experiments conducted on only one problem? What is the rationale behind this limited scope?", "limitations": "This study does not pose any societal impact or ethical concerns. Other limitations have been addressed in the weaknesses and questions sections.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Introduce\bd a generalized value function framework that extends beyond traditional value functions.\n- Proposed a neural network architecture tailored to this generalized value function.\n- Developed a heuristic method based on the generalized value function for efficient optimization.", "weaknesses": "- Limited discussion on the potential advantages of GVF over LPVF, needing more thorough exploration and comparison.\n- Experiments conducted on only one problem, lacking comparison with baselines from related studies.\n- Experimental evaluation needs significant enhancement with more comprehensive testing and broader comparisons.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review. Our new computational experiments, described in detail in the global rebuttal, expand our computational study with another family of problem instances and two new baselines (one for the model and one for the heuristic). We hope that this can address the reviewer’s concerns about the experiments.\n\nWe answer each of the specific questions below:\n* **GVF vs LPVF**: The GVF extends the LPVF by allowing the objective coefficient to vary. In Sec. 2 of the paper, we write the following: “learning the entire GVF at once means that we can reuse the same learned model for many different objectives, potentially saving computation and allowing for a broader generalization.”, which is the main advantage of GVFs over LPVFs. While one can use multiple LPVFs to model subproblems in two-stage problems, it would require learning an NN for each LPVF. For example, in our UFL experiments, we would have to learn up to 750 NNs, whereas here we only learn a single one. Of course, learning a single GVF is generally harder than learning a single LPVF, though a core thesis of this work is that there is underlying structure tying together those many related LPVF that we should be able to exploit when learning the GVF.\n* **Other baselines**: We hope that this concern is alleviated with the addition of one more baseline for the model and another baseline for the heuristic, as described in the global rebuttal. Furthermore, the closest work on learning value functions is the Neur2SP paper (cited as [13] in our paper), which uses a feedforward ReLU network like in our DenseNet baseline. However, they take in as input a set of scenarios instead of a single one as in our case. Given all of this, we believe that DenseNet is a fair baseline, as it both closely hews towards the Neur2SP approach while adapting it in reasonable ways to our somewhat different setting. We also note in passing that the Neur2SP approach is not convex, and so its integration into the MILP heuristic we propose in Sec. 6 would require a MILP formulation (i.e., binary variables in the model), which would likely hinder its scalability.\n* **Other problems**: We hope that this issue is addressed with the addition of the SCFL problem as described in the global rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uY9agspP8b", "reviewer": "Reviewer_CMLg", "summary": "This paper proposes a novel, theoretically grounded approach to learning values function (VF) of linear programs (LP).  Specifically, a Dual-Slack Model (DSM) is proposed to approximate the value function of linear programs with varying right-hand sides and objective coefficients.  The authors prove several key results used as motivation for the architecture and an unsupervised training procedure. This paper also presents numerical results that indicate their model can achieve similar and, in most cases, superior prediction of the LP value function. The authors also demonstrate how the DSM can be a heuristic for obtaining solutions to two-stage problems.", "questions": "- Was the data for the LPs solutions collected in parallel or sequentially?  If sequentially, it may be worth highlighting that parallel implementations can significantly reduce data collection time.  \n- What activation function $\\sigma$ is used in the DSM model?\n- How is (9) solved? The authors mention in line 273 that the model can written as an LP.  However, I believe it should be integer variables as it is piecewise linear.  If so, the authors should cite relevant literature, i.e., [1].\n- How were the model sizes/parameters selected?  \n- Why did the authors choose not to provide code, especially given there is a computational study?  I see the authors mention that this is a theoretical paper in the checklist, but given they have an implementation, I see no reason to include it.  \n\n```\n[1] Matteo Fischetti and Jason Jo. Deep neural networks and mixed integer linear optimization. Constraints,\n23(3):296–309, 2018.\n```", "limitations": "The methodology has limitations, such as applying generalized linear programming value functions. However, the authors explicitly address all limitations very clearly, which is certainly appreciated.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The theoretically motivated architecture, i.e., the DSM, is an excellent contribution.  In my opinion, architecture and papers like this are a great contribution and will certainly be of significance to the field of learning-based approaches for optimization.  As such, I would rate the impact of the theory and model alone as significant.  The unsupervised learning approach is also a notable contribution.  \n- The prediction performance and solution quality of the model.  In prediction performance, i.e., learning the generalized value function, the DSM outperforms the dense network relatively consistently.  In addition, the DSM can compute high-quality first-stage solutions to two-stage MILPs.    \n- Quality and clarity of the paper.  Overall, the paper is very clearly written and well-motivated.  Additionally, the authors constantly discuss the limitations, which is undoubtedly important.", "weaknesses": "Overall, I have quite a favorable opinion of the paper.  However, a few weaknesses warrant further study, especially in the numerical experiments.  Additionally, while I briefly read over the proofs in the Appendix and did not have any concerns, I am certainly not an expert/familiar with some of the material.  \n\n- Limited computational results.  They propose a general approach yet only test six instances of the problem of uncapacitated facility location (UFL).   Moreover, the prediction performance compared to a feed-forward network model is not substantially better.  As such, comparing different benchmarks and perhaps even more models would be important to assess the computational performance holistically.  Even simple baselines, like gradient-boosted trees or random forests, would be useful, given these models generally predict with little to no parameter tuning.  Additionally, it appears no parameter tuning was done for DSM or the feed-forward, and given the relatively similar prediction and limited comparisons, it is hard to assess if DSM outperforms the feed-forward model substantially.  I agree that the paper's primary motivation and significance are more methodological/theoretical.  However, it would undoubtedly strengthen the empirical evidence for the approach proposed by the author to expand the computational section.  \n- The authors propose an unsupervised training approach that does not need to explicitly use the optimal objective values of LPs for training.  While this contribution may be helpful in some contexts, obtaining optimal objective values for LPs is generally computationally efficient.  Furthermore, solving these LPs can be trivially done in parallel, making the case for this even less clear.  From my understanding, the DSM model can also be trained with supervised learning, so comparing the trade-offs in time and solution quality between the supervised and unsupervised approach would be helpful.  A particular question that may be interesting to access is whether the supervised approach provides faster convergence in training such that it may outweigh the time required for data collection.  Additionally, perhaps the data requirements for the DSM would be significantly lower than those of a standard feed-forward network to represent the value function accurately, which may be an interesting result.\n- Benchmarks and results for the heuristic two-stage problems.  The DSM model requires continuous variables in the second stage.  As such, it applies to all two-stage problems on which Benders decomposition can be used.  Given the large number of second-stage variables in the UFL instances, I suspect this may provide a more reasonable benchmark, especially when the LP times out, to access the solution quality of the DSM approach.  Additionally, the results as is demonstrate relatively high MILP gaps, except when the MILP does not solve the instance to optimality, \n\nGiven that the paper is relatively theoretically motivated but primarily would be valuable in applied contexts, strengthening the numerical experiments would undoubtedly improve the submission.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review. We are happy to hear that the reviewer appreciates the significance and clarity of the paper. We now will address each comment in both the Weaknesses and Questions section.\n\n1. **Limited computational results**: As proposed, we will add both a new training baseline (Random Forests) and a new problem (SCFL). This is described in the global rebuttal and we hope that this strengthens the empirical evidence for our approach in your assessment. We also would like to highlight to the reviewer the following:\n   * Number of instances: We do not only test 6 instances of UFL, but rather we have 5 test instances for each of the 6 problem classes as described in Section 7. Therefore, we test 30 instances in total (45 with the addition of SCFL). We will make it clearer in the paper that each row in Tables 1 and 2 are averages over 5 instances.\n   * Hyperparameter tuning: We actually did perform parameter tuning for both DSM and DenseNet; please see Appendix D and Table 3. We will make this clearer in the final version of the text of the paper.\n\n2. **(a) Training the DSM model with supervised data**: We did perform a comparison similar to the one proposed when we did an ablation test on the upper bound to use for the DSM. In particular, we set the upper bound to be the LP optimal value. The results are in Tables 4 and 5 in Appendix D (note: the first row is training and the second row is test; we missed these labels and will fix that in the final version). We observe that passing the true optimal value actually makes the relative error worse, in a way because of how we designed our loss function. Our intuition for why this is the case is as follows. In our loss function, we balance approximating the true value function well (which pushes the function up) and lower-bounding the value function via a penalty (which pushes the function down). If we use the actual optimal LP value in the approximation term, then the latter term is stronger, pushing the function down. Tables 4 and 5 suggest that in practice it is better to use an upper bound that is slightly above the true value function to balance out the penalty (which leads to our unsupervised approach). Finally, we emphasize that unsupervised vs supervised is not the only benefit of our approach: another key feature of the DSM is that it can be embedded in an optimization problem as an LP, rather than a MILP (see response to your question 3 below), which enables us to develop the very fast heuristic from Sec. 6.\n\n   **(b) Solving LPs can be trivially done in parallel**: This is of course correct, and we will add a mention of this in the paper. However, we would like to mention a few relevant points here. First, we note that the number of LPs that would have to be solved can be very large. In particular, we solve $n_f \\cdot n_c / 10$ LPs in our computational setup. For example, for the KG case with 750 facilities and customers, this is 56,250 LPs. Second, in the case of UFL (and similarly for many large-scale problems amenable to decomposition approaches), the subproblem is very easy in that it can be actually solved with a greedy algorithm, which is what we do. Note that the average subproblem solve time is 187.02 / 56250 = 0.003s (3ms). For example, in the SCFL case (in the global rebuttal) with 50 scenarios and 30 samples for $\\mathcal{D}_b$ (1,500 LPs), data labeling took 120s (i.e. 80ms per LP on average).\n\n3. **Benchmarks and results for the heuristic two-stage problems**: We follow the reviewer’s suggestion and add a baseline where we use Benders’ decomposition within the heuristic framework from Sec. 6; see the global rebuttal for more details. We acknowledge that in certain cases we obtain relatively large gaps to the MILP solution, but 1) our approach performs very well on the KG class of instances, and 2) we believe that our approach can be of particular utility in practical applications where low latency is important, as we can achieve good solutions in the order of a few seconds or less.\n\nOn the comments in the Questions section:\n\n1. The data labeling process (i.e., solving LPs) was done sequentially. We will note in Section 7.1 that the data labeling time in Table 1 is sequential and can be embarrassingly parallelizable with sufficient computing power.\n\n2. In our experiment, the activation function $\\sigma$ for every layer of the $\\gamma$ stack is ReLU. However, to avoid vanishing gradients, we use a composition of GeLU and ReLU for training only. With the $\\beta$ stack, the activation of every layer is max-pooling with a window of size 5. The final layer of the DSM is a max-pool. We thank the reviewer for pointing this omission out; we intended for this discussion to be in Appendix D but missed its inclusion. It will be added to the updated version.\n\n3. One of the main advantages of our approach is that the model can indeed be written as an LP. This is because we are learning a model that is piecewise linear convex on $\\beta$. As described in Section 6, optimizing over input-convex neural networks does not require integer variables and can be done as an LP, and it is the reason why we see fast solve times in Table 2 (here, the first-stage variables are integer, but the DSM variables are continuous). We will make this clearer in the paper. In particular, we cited [3] earlier in the paper which studies input-convex NNs, and we will repeat the citation in Sec. 6.\n\n4. The selection of model sizes and parameters is described in Appendix D. We do standard hyperparameter tuning by evaluating combinations of a small set of possible choices (see Appendix D for details on which values we tested).\n\n5. Given our focus on the paper itself, our time at submission (and, now, for this rebuttal) was constrained and our code is not currently organized in such a way that it can be publicly released. That said, if the paper is accepted, we would be happy to publish the code for the model, method, and experiments.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "M3escOGENE", "reviewer": "Reviewer_qfDV", "summary": "This article presents some contribution on the use of neural network to learn what is called the Generalized Linear Programming Value Function (GVF), that evaluates the optimal value of a linear program given as inputs the objective vector and the matrix constraints. This function is useful in many algorithms to actually find a solution (and not only the value) of the optimization problem, in particular for Mixed Integer Linear Programs (MILPs), or two-stage optimization problems. To do so, the authors first prove some fundamental decomposition of the GLV function. Then, they use this result to design a proper architecture of a neural network that can potentially compute that function. With additional analysis, they also provide a theoretical foundation for the use of unsupervised learning to compute the GVF. The authors then devise a heuristic based on these insights and demonstrate the efficiency of their approach experimentally.\n\nThe main two theoretical contributions are: i) a decomposition of the GVF into a max-product of two piecewise-linear functions (Theorem 2), and ii) a structural description (Theorem 2 and 3) of what a GVF must verify to be representable as some NN with the architecture they deduced from Theorem 2. In particular, ii) gives the existence of a finite set of parameters such that if the given architecture is equal to the GVF, then they must be equal everywhere.\n\nThe authors then present algorithms that incorporate heuristics, that they discuss in details, showing how they are grounded in theory.", "questions": "- Is Theorem 3 completely new? Did it not exist before in the optimization literature?\n\n- Where do you believe the bottleneck of the method resides (giving results of tables 1 and 2) ? Is it the difficulty to actually compute the GVF in an unsupervised manner?\n\n- Typo: Line 90, the authors probably meant $\\xi$, not $\\chi$", "limitations": "The authors are transparent about the limitations of their work and results. Some additional explanations about the causes or bottleneck of these limitations would have been welcome. (see second question above).", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The article is well-organized, reads well, and exposes clearly the contributions. It presents a serious study, with solid structural contributions. It can be of interest for researchers at the interface of optimization and machine learning, as well as developers of optimization solvers. \n\nThe authors also articulate well between these theoretical results and the practical algorithms.", "weaknesses": "- The experimental results are somehow limited. Although the double stack method (presented in this article) seems to be more effective than DenseNets in average, it is not always the case as shown by Table 1. Also, when compared to SCIP, the gaps for most of the instances are above 20% (although the running time is indeed less than a second). \n\n- The authors do not provide an explanation of what they think to be the limitation of their experimental results, that would be of interest for readers who would be interested to follow up with their work. I would be willing to revise my evaluation score if this is adressed by the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s comments, especially for highlighting our contributions and the clarity of the paper. Please see the global rebuttal for expanded computational results. We address the specific comments (both from the Weaknesses and Questions section) below.\n\n1. **Effectiveness of the method**: From our perspective, the major benefits of the DSM are that it guarantees that certain invariants that we know must hold in the “ground truth” function, and that these invariants can be translated effectively to efficient methods for our end goals. Producing models with lower errors than standard methods is a nice side effect of using a suitable architecture, but was not our main goal. In particular, we design the DSM such that: 1) the DSM can be easily embedded into an optimization problem as an LP due to its linearity and convexity on $\\beta$, 2) it produces a function that is a guaranteed lower bound to the true GVF, and 3) it does not require supervised data. Due to these properties, we believe that our method is valuable even if our errors were the same, or even somewhat worse, than a reasonable baseline. Property 1 is what allows us the very fast solve times (<1 to ~4s) presented in Sec. 7.2, in problems where even solving the LP relaxation of the full model can take minutes. While this perspective may mean that our approach is not well-suited for every possible use case, there are settings where this approach is very well-suited: for example, soft real-time control where fast solve latencies is a hard requirement.\n\n2. **Limitations + Bottleneck of the method**: This is a very good question, and we agree that a discussion on limitations can help researchers build upon our work. We enumerate potential limitations in each part of our method.\n\n   **(a) Stability during training**: During training, we must balance two terms in our loss function: one that rewards us for fitting the data well (first term), and another one that (softly) constrains the function down to be below the true value function for $\\gamma \\in \\mathcal{D}_c$ (second term). Finding a stable balance between these two terms appears to be one of the most challenging parts of training. This was in fact a significant obstacle during the development of our method, and we overcome this limitation by proposing an adaptive update method for the penalty $\\mu$, tuning the initial $\\mu$ hyperparameter well, and proposing a good stopping criterion. However, even with all these measures, we do observe from the training logs that there is room for improvement (e.g., an adaptive stopping rule), which is a potential direction for future research.\n\n   **(b) Generalization to objective vectors not in the training set**: Our theoretical results say that guaranteeing the constraints (7b) is sufficient to produce a function that lower bounds the GVF, but we may have infinitely many constraints (as represented via $\\bar{\\mathcal{C}}$). In practice, we aim to enforce it for the objective vectors in the training data $\\mathcal{D}_c$, which does give us this guarantee for any right-hand side $\\beta$ and any objective vector from this training collection. We observe that with sufficient samples, we can generalize to other objective vectors, but we note that our Test Lower Bound column in Table 1 differs from the Train Lower Bound column by a significant amount. That said, we find that this still works well for purposes of a heuristic (see next item), but this could be a potential pitfall especially if one does not use enough training data.\n\n   **(c) Guaranteeing a lower bounding function of GVF**: As described in Sec. 5.3, we obtain a model that is close to satisfying the constraints (7b), and we then scale the function down to obtain a function that universally lower bounds the GVF. A potential pitfall here is that if the model is not close enough to satisfying the constraints, then we could be overly conservative in our scaling and end up with a function that is too far from GVF. In particular, we observed that this can happen if we do not stop the training at the right point. On the other hand, we also observe that for purposes of the heuristic in Sec. 6, obtaining an approximation with a good overall shape is often sufficient even if it is scaled down, since we care more about obtaining a solution close to optimal instead of an accurate representation of the objective values.\n\n   We will include a version of this discussion in the paper, and welcome any further feedback the reviewer might have. Specifically, we believe that the points discussed above are key when trying to identify the limitations of our method. In particular, the unsupervised training does require us to handle stability better during training. However, we can generally mitigate them with the efforts presented in our paper.\n \n3. **Novelty of Theorem 3**: Theorem 3 is indeed new (to the best of our knowledge). The Dual-Stack Model is novel, and a characterization of its properties is also novel, though it is mostly based on well-established properties (e.g., the piecewise linearity of ReLU NNs). In particular, the DSM was designed to have the desirable properties from Theorem 3 in order to mimic our GVF representation theorem (Theorem 2).\n\n4. **Typo**: Thank you for pointing out the typo. We will fix it in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their feedback. We wrote this paper with the goal of presenting a “theoretically motivated architecture” for what we view as an important and interesting setting in mathematical optimization, and we are happy to see that this vision appears to have resonated with the review team. We are grateful that the reviewers view the paper as “well-organized” and “very clearly written” (we spent a lot of time on this!). We also appreciate the constructive feedback that they offered, which we feel will lead to a stronger and more compelling paper. We will spend the remainder of the rebuttal focusing on this feedback, and how we plan to use it to improve the paper. In particular, we have expanded the computational experiments to address reviewer concerns on limited experiments:

1. **New model baseline: Random Forests**. We have performed a comparison with the GVF learned with Random Forests (suggested by reviewer CMLg) in the attached pdf Table 1, which we will add to the paper. We used the sklearn package with 100 estimators and 8 parallel threads, and all other settings are set to default. We will also add random forest experiments for KG 750 (which we did not have time to perform during the rebuttal period) and the new problem class SCFL (see below) in the final version. 

   As a reminder, these results should be interpreted in view of the three beneficial properties of our method: 1, the DSM can be easily embedded into an optimization problem as an LP due to its linearity and convexity on $\beta$, 2, it produces a function that is a guaranteed lower bound to the true GVF, and 3, it does not require supervised data. Random Forests do not benefit from any of these properties. It could be embedded into optimization as an MILP, which can make for example the heuristic in Sec. 7.2 much more expensive. Furthermore, they are piecewise constant and discontinuous, therefore not matching the natural structure of the GVF. Hence, even though Random Forests can attain a slightly lower error in some instances, this is still a positive result for the DSM especially given the long Random Forest training times.

2. **New heuristic baseline: MILP heuristic with Benders decomposition**. We compare our heuristic with a Benders Decomposition baseline (suggested by reviewer CMLg) similar to our Algorithm 3, except that in (9) we replace the DSMs by approximations obtained by solving the LP relaxation with Benders with t iterations, where t equals number of facilities. The results are in the attached pdf Table 2. After that, we solve (9) with a time limit of 1 minute (though the Euclidean instances solve to optimality faster). The solve times in the table are end-to-end. We observe that our heuristic performs much better than the Benders baseline for the KG instances, though Benders outperforms our heuristic for the Euclidean instances.

3. **New problem: Stochastic Capacitated Facility Location**. We performed experiments on the Stochastic Capacitated Facility Location Problem in the attached pdf Table 3. This is similar to the Uncapacitated Facility Location Problem in the paper, with two differences: 1, capacity constraints prevent us from decomposing over customers (facilities can serve a limited capacity over all customers), and 2, instead of a deterministic problem, we have multiple scenarios with varying demand and costs, and we would like to minimize the total expected cost over the scenarios. In this case, the decomposition is done over scenarios, and each subproblem in this decomposition is an assignment problem from customers to a set of fixed open facilities (decided in the first stage), satisfying required customer demands and facility capacity limits.

   To generate these instances, we take deterministic instances from [OR-Library](https://people.brunel.ac.uk/~mastjjb/jeb/info.html), and generate 50 scenarios by randomly modified both the demands and unit costs to be $\mathcal{N}(\mu, \sigma)$ where $\mu$ is the original value and $\sigma$ is drawn from $\mathcal{U}(0.1 \mu, 0.3 \mu)$. We use 30 samples for $\mathcal{D}_b$. Due to time constraints of the rebuttal, we only show one row of the table with one test instance (training on cap61 and testing on cap62, with 16 customers and 50 facilities). We will perform the full experiments for the final version, including the MILP heuristic.

   Unfortunately, our stopping criterion does not work as well in this case. We choose to stop at a fixed number of iterations, T = 60 (with 100 steps of the Adam algorithm in between), with the acknowledgement that training can be unstable. We decide to present these results in the rebuttal anyway because we believe they are still interesting, and we will further tune the training for the final version of the paper.

All other questions are addressed in the individual rebuttals. We are happy to discuss and incorporate further feedback.

Meta-review: Good paper. Clear accept. 

The paper studies the learning of the optimal objective function of a linear program as a function of its inputs. The neural network design utilizes the LP's optimality condition (and its implication that the optimal value function should be piecewise-linear one). The proposed method enjoys theoretical guarantees and gives promising numerical performances. And I agree with the reviewers that the paper can inspire many follow-up works on this topic.
Decision: Accept (spotlight)