Neur2BiLO: Neural Bilevel Optimization

Authors: justin  dumouchelle
esther  julien
t u delft
jannis  kurtz
elias b khalil
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 12:32:32

Abstract: Bilevel optimization deals with nested problems in which *leader* takes the first decision to minimize their objective function while accounting for a *follower*'s best-response reaction. Constrained bilevel problems with integer variables are particularly notorious for their hardness. While exact solvers have been proposed for mixed-integer *linear* bilevel optimization, they tend to scale poorly with problem size and are hard to generalize to the non-linear case. On the other hand, problem-specific algorithms (exact and heuristic) are limited in scope. Under a data-driven setting in which similar instances of a bilevel problem are solved routinely, our proposed framework, Neur2BiLO, embeds a neural network approximation of the leader's or follower's value function, trained via supervised regression, into an easy-to-solve mixed-integer program.  Neur2BiLO serves as a heuristic that produces high-quality solutions extremely fast for four applications with linear and non-linear objectives and pure and mixed-integer variables.

Main paper: 
 introduction: 
 A motivating application. Consider the following discrete network design problem (DNDP) [47, 48] . A transportation planning authority seeks to minimize the average travel time on a road network represented by a directed graph of nodes N and links A 1 by investing in constructing a set of roads (i.e., links) from a set of options A 2 , subject to a budget B. The planner knows the number of vehicles that travel between any origin-destination (O-D) pair of nodes. A good selection of links should take into account the drivers' reactions to this decision. One common assumption is that drivers will optimize their O-D paths such that a user equilibrium is reached. This is known as Wardrop's second principle in the traffic assignment literature, an equilibrium in which "no driver can unilaterally reduce their travel costs by shifting to another route" [41] . This is in contrast to the system optimum, an equilibrium in which a central planner dictates each driver's route, an unrealistic assumption that would not require bilevel modeling. A link cost function is used to model the travel time on an edge as a function of traffic. Let c ij ∈ R + be the capacity (vehicles per hour (vph)) of a link and T ij ∈ R + the free-flow travel time (i.e., travel time on the link without congestion). The US Bureau of Public Roads uses the following widely accepted formula to model the travel time t(y ij ) on a link used by y ij vehicles per hour: t(y ij ) = T ij (1 + 0.15(y ij /c ij ) 4 ). As the traffic y ij grows to exceed the capacity c ij , a large quartic increase in travel time is incurred [41] .Bilevel optimization (BiLO) [4] models the DNDP and many problems in which an agent (the leader) makes decisions that minimize their cost function subject to another agent's (the follower's) best response. In the DNDP, the leader is the transportation planner and the follower is the population of drivers, giving rise to the following optimization problem min x∈{0,1} |A 2 | ,y (i,j)∈A y ij t(y ij ) s.t.(i,j)∈A2g ij x ij ≤ B, y ∈ arg miny ′ ∈R |A| + (i,j)∈A y ′ ij 0 t ij (v)dv s.t. y ′ is a valid network flow, x ij = 0 =⇒ y ′ ij = 0,whereA 2 ∩ A 1 = ∅, A = A 1 ∪ A 2 .The leader minimizes the total travel time across all links subject to a budget constraint and the followers' equilibrium which is expressed as a network flow on the graph augmented by the leader's selected edges that satisfies O-D demands; the integral in the follower's objective models the desired equilibrium and evaluates toT ij y ′ ij + 0.15Tij 5c 4 ij y ′ ij 5 .Going beyond the DNDP, Dempe [16] lists more than 70 applications of BiLO ranging from pricing in electricity markets (leader is an electricity-supplying retailer that sets the price to maximize profit, followers are consumers who react accordingly to satisfy their demands [60] ) to interdiction problems in security settings (leader inspects a budgeted subset of nodes on a road network, follower selects a path such that they evade inspection [56] ).Scope of this work. We are interested in mixed-integer non-linear bilevel optimization problems, simply referred to hereafter as bilevel optimization or BiLO, a very general class of bilevel problems where all constraints and objectives may involve non-linear terms and integer variables. At a high level, we have identified three limitations of existing computational methods for BiLO:1. The state-of-the-art exact solvers of Fischetti et al. [24] and Tahernejad et al. [53] are limited to mixed-integer bilevel linear problems and do not scale well. When high-quality solutions to large-scale problems are sought after, such exact solvers may be prohibitively slow. 2. Specialized algorithms, heuristic or exact, do not generalize beyond the single problem they were designed for. For instance, the state-of-the-art exact Knapsack Interdiction solver [57] only works for a single knapsack constraint and fails with two or more, a significant limitation even if one is strictly interested in knapsack-type problems. 3. Existing methods, exact or heuristic, generic or specialized, are not designed for the "data-driven algorithm design" setting [3] in which similar instances are routinely solved and the goal is to construct generalizable high-efficiency algorithms that leverage historical data.NEUR2BILO (for Neural Bilevel Optimization) is a learning-based framework for bilevel optimization that deals with these issues simultaneously. The following observations make NEUR2BILO possible:1. Data collection is "easy": For a fixed decision of the leader's, the optimal value of the follower can be computed by an appropriate (single-level) solver (e.g., for mixed-integer programming (MIP) or convex programming), enabling the collection of samples of the form: (leader's decision, follower's value, leader's value). 2. Offline learning in the data-driven setting: While obtaining data online may be prohibitive, access to historical training instances affords us the ability to construct, offline, a large dataset of samples that can then serve as the basis for learning an approximate value function using supervised regression. The output of this training is a regressor mapping a pair consisting of an instance and a leader's decision to an estimated follower or leader value. 3. MIP embeddings of neural networks: If the regressor is MIP-representable, e.g., a feedforward ReLU neural network or a decision tree, it is possible to use a MIP solver to find the leader's decision that minimizes the regressor's output. This MIP, which includes any leader constraints, thus serves as an approximate single-level surrogate of the original bilevel problem instance. 4. Follower constraints via the value function reformulation: The final ingredient of the NEUR2BILO recipe is to include any of the follower's constraints, some of which may involve leader variables. This makes the surrogate problem a heuristic version of the well-known value function reformulation (VFR) in BiLO. The VFR transforms a bilevel problem into a single-level one, assuming that one can represent the follower's value (as a function of the leader's decision) compactly. This is typically impossible as the value function may require an exponential number of constraints, a bottleneck that is circumvented by our small (approximate) regression models. 5. Theoretical guarantees: For interdiction problems, a class of BiLO problems that attract much attention, NEUR2BILO solutions have a constant, additive absolute optimality gap which mainly depends on the prediction accuracy of the regression model.Through a series of experiments on (i) the bilevel knapsack interdiction problem, (ii) the "critical node problem" from network security, (iii) a donor-recipient healthcare problem, and (iv) the DNDP, we will show that NEUR2BILO is easy to train and produces, very quickly, heuristic solutions that are competitive with state-of-the-art methods. 
background: 
 Bilevel optimization (BiLO) deals with hierarchical problems where the leader (or upper-level) problem decides on x ∈ X and parameterizes the follower (or lower-level) problem that decides on y ∈ Y; the sets X and Y represent the domains of the variables (continuous, mixed-integer, or pure integer). Both problems have their own objectives and constraints, resulting in the following model:EQUATIONwhere we consider the general mixed-integer non-linear case with F, f :X × Y → R, G : X × Y → R m1, and g : X × Y → R m2 non-linear functions of the upper-level x and lower-level variables y. The applicability of exact (i.e., global) approaches critically depends on the nature of the lower-level problem. A continuous lower-level problem admits a single-level reformulation that leverages the Karush-Kuhn-Tucker (KKT) conditions as constraints on y. For linear programs in the lower level, strong duality conditions can be used in the same way. Solving a BiLO problem with integers in the lower level necessitates more sophisticated methods such as branch and cut [17, 24] along with some assumptions: DeNegre and Ralphs [17] do not allow for coupling constraints (i.e., G(x, y) = G(x)) and both methods do not allow continuous upper-level variables to appear in the linking constraints (g(x, y)). Other approaches, such as Benders decomposition, are also applicable [25] . Gümüş and Floudas [29] propose single-level reformulations of mixed-integer non-linear BiLO problems using polyhedral theory, an approach that only works for small problems. Later, "branch-and-sandwich" methods were proposed [33, 45] where bounds on both levels' value functions are used to compute an optimal solution. Algorithms for non-linear BiLO generally do not scale well. Kleinert et al. [32] survey more exact methods.In what follows, we make the following standard assumptions:1. Either (i) the follower's problem has a feasible solution for each x ∈ X , or (ii) there are no coupling constraints in the leader's problem, i.e., G(x, y) = G(x); 2. The optimal follower value is always attained by a feasible solution [see 5, Section 7.2].Value function reformulation. We consider the so-called optimistic setting: if the follower has multiple optima for a given decision of the leader's, the one that optimizes the leader's objective is implemented. We can then rewrite problem (1) using the value function reformulation (VFR):EQUATIONwith the optimal lower-level value function defined asEQUATIONLozano and Smith [39] used this formulation to construct an exact algorithm (without any public code) for solving mixed-integer non-linear BiLO problems with purely integer upper-level variables. Sinha et al. [50, 51, 52] propose a family of evolutionary heuristics for continuous non-linear BiLO problems that approximate the optimal value function by using quadratic and Kriging (i.e., a function interpolation method) approximations. Taking it one step further, Beykal et al. [9] extend the framework of the previous authors to handle mixed-integer variables in the lower level. 
methodology: 
 NEUR2BILO refers to two learning-based single-level reformulations for general BiLO problems.The reformulations rely on representing the thorny nested structure of a BiLO problem with a trained regression model that predicts either the upper-level or lower-level value functions. Appendix B includes pseudocode for data collection, training, and model deployment.Upper-level approximation. The obvious bottleneck in solving BiLO problems is their nested structure. One rather straightforward way of circumventing this difficulty is to get rid of the lower level altogether in the formulation, but predict its optimal value. Namely, we predict the optimal upper-level objective value function asEQUATIONwhere Θ are the weights of a neural network, F the objective function of the leader (2b), and y ⋆ an optimal solution to the lower level problem (3) . To train such a model, one can sample x from X , solve (3) to obtain an optimal lower-level solution y ⋆ , and subsequently compute a label F (x, y ⋆ ).We can then model the single-level problem asEQUATIONwhere we only optimize for x and thus dismiss the lower-level constraints and objective function.A trained feedforward neural network NN u (•; Θ) with ReLU activations can be represented as a mixed-integer linear program (MILP) [22] , where now the input (and output) of the network are decision variables. With this representation, Problem (5) becomes a single-level problem and can be solved using an off-the-shelf MIP solver. Note that linear and decision tree-based models also admit MILP representations [38] .This reformulation is similar to the approach by Bagloee et al. [2] , wherein the upper-level value function is predicted using linear regression. Our method differs in that it is not iterative and does not require the use of "no-good cuts" (which avoid reappearing solutions x). As such, our method is extremely efficient as will be shown experimentally.The formulation of (5) only allows for problem classes that do not have coupling constraints, i.e., G(x, y) = G(x). Moreover, the feasibility of a solution x in the original BiLO problem is not guaranteed, an issue that will be addressed later in this section (see Bilevel feasibility.).Lower-level approximation. This method makes use of the VFR (2). The VFR moves the nested complexity of a BiLO to constraint (2d), where the right-hand side is the optimal value of the lower-level problem, parameterized by x. We introduce a learning-based VFR in which Φ(x) is approximated by a regression model with parameters Θ:EQUATIONBoth NN l and NN u take in a leader's decision as input and require solving the follower (3) for data generation. By replacing Φ(x) with NN l (x; Θ) in (2d) and introducing a slack variable s ∈ R + , the surrogate VFR reads as:EQUATIONAll follower and leader constraints of the original BiLO problem are part of Problem (7) . However, without the slack variable s, the problem could become infeasible due to inaccurate predictions by the neural network. This happens when NN l (x; Θ) strictly overestimates the follower's optimal value for each x. In this case, there does not exist a follower decision for which Constraint (7d) is satisfied. A value of s > 0 can be used to make Constraint (7d) satisfiable at a cost of λs in the objective, guaranteeing feasibility.Bilevel feasibility. Given a solution x ⋆ or a solution pair (x ⋆ , ỹ) returned by our upper-or lowerlevel approximations, respectively, we would like to produce a lower-level solution y ⋆ such that (x ⋆ , y ⋆ ) is bilevel-feasible, i.e., it satisfies the original BiLO in (1) . The following procedure achieves this goal:1. Compute the follower's optimal value under x ⋆ , Φ(x ⋆ ), by solving (3).2. Compute a bilevel-feasible follower solution y ⋆ by solving problem (2) with fixed x ⋆ and the right-hand side of (2d) set to Φ(x ⋆ ), a constant. Return (x ⋆ , y ⋆ ). Upper-v.s. lower-level level approximation. Here, we note two important trade-offs between the upper-and lower-level approximations.-Generality: Example C.1 in Appendix C shows that under Assumption 1(ii), it may happen that solving the upper-level approximation problem variant (5) returns an infeasible solution while the lower-level variant (7) does not. -Scalability: The upper-level approximation has fewer variables and constraints than its lowerlevel counterpart as it does not represent the follower's problem directly. For problems in which the lower-level problem is large, e.g., necessitating constraints for each node and link to enforce a network flow in the follower solution as in the DNDP from the introduction, this property makes the upper-level approximation easier to solve, possibly at a sacrifice in final solution quality. This tradeoff will be assessed experimentally.Limitations. Since NEUR2BILO is in essence a learning-based heuristic, it does not guarantee an optimal solution to the bilevel problem. However, it guarantees a feasible solution with the lower-level approximation and can only give an infeasible solution while using the upper-level approximation when only Assumption 1(ii) is satisfied. Moreover, as will be shown in Section 3.3, the performance of NEUR2BILO depends on the regression error, which is generally the case when integrating machine learning in optimization algorithms. Empirically, we note that the prediction error achieved on every problem is very low (see Appendix K.3).For ease of notation in previous sections, all regression models take as input the upper-level decision variables. However, in our experiments, we leverage instance information as well to train a single model that can be deployed on a family of instances. This is done by leveraging information such as coefficients in the objective and constraints for each problem.For the model's architecture, the general principle deployed is to first explicitly represent or learn instance-based features. The second is to combine instance-based features with (leader) decision variable information to make predictions.The overall architecture can be summarized as the following set of operations. Fix a particular instance of a BiLO problem and let n be the number of leader variables, f i a vector of features for each leader variable x i (independently of the variable's value), and h(x i ) a feature map that describes the ith leader variable for a specific value of that variable. The functions Ψ s , Ψ d , and Ψ v are neural networks with appropriate input-output dimensions. The vector Θ includes all learnable parameters of networks Ψ s , Ψ d , and Ψ v . The functions SUM, CONCAT, and AGGREGATE sum up a set of vectors, concatenate two vectors into a single column vector, and aggregate a set of scalar values (e.g., by another neural network or simply summing them up), respectively. Our final objective value predictions are then given by the following sequence of steps:1. Embedding the set of variable features {f i } using a set-based architecture, e.g., the same network Ψ d , summing up the resulting n variable embeddings, then passing the resulting vector to network Ψ s , yielding a vector we refer to as the INSTANCEEMBEDDING:INSTANCEEMBEDDING = Ψ s (SUM({Ψ d (f i )} n i=1)). This is akin to the DeepSets approach of Zaheer et al. [58] . However, note that this step can alternatively be done via a feedforward or graph neural network depending on the problem structure. 2. Conditional on a specific assignment of values to the leader's decision vector x, a per-variable embedding is computed by network Ψ v to allow for interactions between the INSTANCEEM-BEDDING and the specific assignment of variable i as represented by h(x i ):VARIABLEEMBEDDING(i) = Ψ v (CONCAT(h(x i ), INSTANCEEMBEDDING)). 3.The final value prediction for either of our approximations aggregates the variable embeddings possibly after passing them through a function g i : NN(x; Θ) = AGGREGATE({g i (VARIABLEEMBEDDING(i))} n i=1 ). For example, if the follower's objective is a linear function and VARIABLEEMBEDDING(i) is a scalar, then it is useful to use the variable's known objective function coefficient d i here, i.e.: g i (VARIABLEEMBEDDING(i)) = d i • VARIABLEEMBEDDING(i). The final step is to aggregate the per-variable g i (•) outputs, e.g., by a summation for linear or separable objective functions.NEUR2BILO is largely agnostic to the learning model utilized as long as it is MILP-representable. In our experiments, we primarily focus on neural networks, but for some problems also explore the use of gradient-boosted trees. More details on the specific architectures for each problem can be found in Appendix K.1.Lower-level approximation. Next, we present an approximation guarantee for the lower-level approximation with NN l (x; Θ). Appendix D includes the complete proofs.Since the prediction of the neural network is only an approximation of the true optimal value of the follower's problem Φ(x), NEUR2BILO may return sub-optimal solutions for the original problem (1) . We derive approximation guarantees for a specific setup that appears in interdiction problems: the leader and the follower have the same objective function (i.e., f (x, y) = F (x, y) for all x ∈ X , y ∈ Y), and Assumption 1(i) holds. Consider a neural network that approximates the optimal value of the follower's problem up to an absolute error of α > 0, i.e., |NN l (x; Θ) -Φ(x)| ≤ α for all x ∈ X . (8) Furthermore, we define the parameter ∆ as the maximum difference f (x, y) -f (x, y ′ ) ≥ 0 over all x ∈ X , y, y ′ ∈ Y such that no ỹ ∈ Y exists which has function value f (x, y) > f (x, ỹ) > f (x, y ′ ). We can bound the approximation guarantee of the lower-level NEUR2BILO as follows: Theorem 3.1. If the leader and the follower have the same objective function and λ > 1, NEUR2BILO returns a feasible solution (x ⋆ , y ⋆ ) for Problem (1) with objective valuef (x ⋆ , y ⋆ ) ≤ opt + 3α + 2 λ ∆,where opt is the optimal value of (1) and λ the penalty term in (7a) .Upper-level approximation. As Example C.1 shows, it may happen that the upper-level surrogate problem (5) returns an infeasible solution and hence no approximation guarantee can be derived in this case. However, in the case where all leader solutions are feasible and the neural network predicts for every x ∈ X an upper-level objective value that deviates at most α > 0 from the true one, then the returned solution trivially approximates the true optimal value with an absolute error of at most 2α. This follows since the worst that can happen is that the objective value of the optimal solution is overestimated by α while a solution with objective value opt + 2α is underestimated by α and hence has the same predicted value as the optimal solution. Problem (5) then may return the latter sub-optimal solution. 
experimental setup: 
 Benchmark problems and their characteristics are summarized in Table 1 ; their MIP formulations are deferred to Appendix E and brief descriptions follow:-Knapsack interdiction (KIP) [10] : The leader interdicts a subset of at most k items and the follower solves a knapsack problem over the remaining (non-interdicted) items. The leader aims to minimize the follower's (maximization) objective. -Critical node problem (CNP) [18, 11] : This problem regards the protection (by the leader) of resources in a network against malicious follower attacks. It has applications in the protection of computer networks against cyberattacks as demonstrated by Dragotto et al. [18] . -Donor-recipient problem (DRP) [27] : This problem relates to the donations given by certain agencies to countries in need of, e.g., healthcare projects. The leader (the donor agency) decides on which proportion of the cost, per project, to subsidize, whereas the follower (a country) decides which projects it implements. -Discrete network design problem (DNDP) [47] : This is the problem described in Section 1.We build on the work of Rey [47] who provided benchmark instances for the transportation network of Sioux Falls, South Dakota, and an implementation of the state-of-the-art method of Fontaine and Minner [25] . This network and corresponding instances are representative of the state of the DNDP in the literature. 1 : Problem class characteristics. All problems have a single budget constraint in the leader; for the follower, the DNDP has network flow constraints whereas other problems have a knapsack constraint. The arrows refer to minimization (↓) or maximization (↑) in leader and follower, respectively. B = Binary, C = Continuous, MI = Mixed-Integer, Lin = Linear, BLin = Bilinear, NLin = Non-Linear.Baselines. As mentioned previously, the branch-and-cut (B&C) algorithm by Fischetti et al. [24] is considered to be state-of-the-art for solving mixed-integer linear BiLO. The method is applicable if the continuous variables of the leader do not appear in the follower's constraints. Both KIP and CNP meet these assumptions. This algorithm will act as the baseline for these problems. For DRP, we compare against the results produced by an algorithm in the branch-and-cut paradigm (B&C+) from Ghatkar et al. [27] . For DNDP, the follower's problem only has continuous variables, so the baseline is a method based on KKT conditions (MKKT) [25] . Of the learning-based approaches for BiLO, we compare against Zhou et al. [59] , given the generality of their approach and the availability of source code. NEUR2BILO decisively outperforms this method on KIP, finding solutions with 10-100× smaller mean relative error roughly 1000× faster; full results are deferred to Appendix F.For each problem class, data is collected by sampling feasible leader decisions x and then solving Φ(x) to compute either the upper-or lower-level objectives as labels.We then train regression models to minimize the least-squares error on the training samples. Typically, data collection and training take less than one hour, a negligible cost given that for larger instances baseline methods require more time per instance. Additionally, the same trained model can be used on multiple unseen test instances. We report times for data collection and training in Appendix K.2.Evaluation & Setup. For evaluation in KIP, CNP, and DRP, all solving was limited to 1 hour. For DNDP, we consider a more limited-time regime, wherein we compare NEUR2BILO at 5 seconds against the baseline at 5, 10, and 30 seconds. For all problems, we evaluate both the lower-and upper-level approximations with neural networks, namely NN l and NN u . For NN l we set λ = 1 for all results presented in the main paper. Details of the computing setup are provided in Appendix J.Our code and data are available at https://github.com/khalil-research/Neur2BiLO. 
experimental results: 
 We summarize the results as measured by average solution times and mean relative errors (MREs).The relative error on a given instance is computed as 100• |obj A -obj best | |obj best |, where obj A is the value of the solution found by method A and obj best is the best-known objective value for that instance. These results are reported in Table 2 . More detailed results and box-plots of the distributions of relative errors are in Appendices G and H. Our experimental design answers the following questions: Q1: Can NEUR2BILO find high-quality solutions quickly on classical interdiction problems? Table 2 compares NEUR2BILO to the B&C algorithm of Fischetti et al. [24] . NEUR2BILO terminates in 1-2% of the time required by B&C on the smaller (n ≤ 30) well-studied KIP instances of Tang et al. [54] . However, when the instance size increases to n = 100, both NN l and NN u find much better solutions than NEUR2BILO in roughly 30 seconds, even when B&C runs for the full hour. Furthermore, Table 4 in Appendix G shows that B&C requires 10 to 1, 000× more time than NN l or NN u to find equally good solutions. In addition, the best solutions found by B&C at the termination times of NN l or NN u are generally worse, even for small instances.Q2: Do these computational results extend to non-linear and more challenging BiLO problems? Interdiction problems such as the KIP are well-studied but are only a small subset of BiLO. We will shift attention to the more practical problems, starting with the CNP (Table 2 ). CNP includes terms that are bilinear (i.e., z = xy) in the upper-and lower-level variables, resulting in a much more challenging problem for general-purpose B&C. In this case, both NN l and NN u tend to outperform B&C as the problem size increases. In addition, the results on incumbents reported in Table 5 in Appendix G are as good, if not even stronger than those of KIP.Secondly, we discuss DRP (Table 6 in Appendix G). For DRP, we evaluate on the most challenging instances from Ghahtarani et al. [26] , all of which have gaps of ∼ 50% at a 1-hour time limit with B&C+, a specialized B&C-based algorithm. Here NN u performs remarkably well: it finds the best-known solutions on every single instance in roughly ∼ 0.1 seconds at an average improvement in solution quality of 26% over B&C+.Q3: How does NEUR2BILO perform on BiLO problems with complex constraints? Given that NEUR2BILO has strong performance on benchmarks with budget constraints, the next obvious question is whether it can be applied to BiLO problems that have complex constraints. To answer this, we will refer to the results in Table 2 for the DNDP. In this setting, we focus on a limited-time regime wherein we compare NEUR2BILO with a 5-second time limit to MKKT at time limits 5, 10, and 30 seconds. NN u can achieve high-quality solutions much faster than any other method with only a minor sacrifice in solution quality, making it a great candidate for domains where interactive decision-making is needed (e.g., what-if analysis of various candidate roads, budgets, etc.).NN l , on the other hand, takes longer than NN u but computes solutions that are competitive with the baseline, the latter requiring 5× more time. We suspect that the better solution quality from NN l is due to its explicit modeling of feasible lower-level decisions that "align" with the predictions, whereas NN u may simply extrapolate poorly. In terms of computing time, one computational burden for NN l is the requirement to model the non-linear upper-and lower-level objectives, which requires a piece-wise linear approximation based on Fontaine and Minner [25] , a step that introduces additional variables and constraints. Appendix G includes results for DNDP with gradient-boosted trees (GBT), demonstrating that other learning models are directly applicable and, in some cases, may even lead to better solution quality, faster optimization, and simpler implementation. [54] ; each value is the average over 10 instances. For n = 100, our evaluation instances (100 per size) are generated using the same procedure of Tang et al. [54] . The no-learning baseline G-VFA is a VFR using the follower's greedy solution as lower-level value function approximation. For CNP, each row is averaged over 300 instances that are randomly sampled using the procedure described in Dragotto et al. [18] . For DNDP, each row is averaged over 10 instances from Rey [47] . The budget is a fraction of the total cost of all 30 possible candidate links; see Appendix K.2 for more details.Q4: Can approximations derived from heuristics be useful? We now refer back to KIP and focus on the greedy value function approximation (G-VFA), a KIP-specific approximation that relies on the fact that greedy algorithms are typically good for 1-dimensional knapsack problems. Namely, the heuristic is based on ordering the items with their value-to-weight ratio [15] and is used as the knapsack solution in the follower problem, while still being parameterized by x. This heuristic is embedded in a single-level problem as this heuristic is MILP-representable [see 1]; we note that we are not aware of uses in the literature of this approximation and it may be of independent interest. Generally, G-VFA performs quite well, and in some cases outperforms NN l and NN u , but there are clear cases where NN l and NN u outperform G-VFA demonstrating that learning is beneficial. In addition, heuristics like G-VFA can be utilized to compute features for NN l and NN u . For KIP, the inclusion of these features derived from G-VFA strongly improves the results (see Table 10 in Appendix I.3). This demonstrates that there is value in leveraging any problem-specific MILP-representable heuristics as features for learning.Q5: How does λ affect NN l ? Table 9 in Appendix I.2 shows that a slack penalty of λ = 0.1 notably improves the performance of both NN l and GBT l for DNDP, compared to the λ = 1 reported in Table 2 . As an alternative to adding slack, one can even dampen predictions of the value function to allow more flexibility using the empirical error observed during training; see Table 8 [59] propose a learning-based algorithm for binary bilevel problems which, similar to our approach, predicts the optimal value function and develops a single-level reformulation based on the trained model. They propose using a graph neural network and an input-supermodular neural network, both of which can only be trained on a single instance rather than learning across classes of instances as NEUR2BILO does. NEUR2BILO significantly outperforms this method as shown in Appendix F. For continuous unconstrained bilevel optimization, a substantially different setting, many methods have been proposed recently due to interest in solving nested problems in machine learning (e.g., hyperparameter tuning and meta-learning) [37] .Data-driven optimization. The integration of a trained machine learning model into a MIP is a vital element of NEUR2BILO. This is possible due to MILP formulations of neural networks [14, 22, 49] , and of other predictors like decision trees [38, 8] . These methods have become easily applicable due to open software implementations [7, 12, 40, 55] and the gurobi-machinelearning library. One such application is constraint learning [21] . More similar to our setting are the approaches in [19, 20, 34] for predicting value functions of other nested problems such as two-stage stochastic and robust optimization. Our method caters to the specificities of BiLO, particularly in the lower-level approximation which performs well in highly-constrained BiLO settings such as the DNDP, has approximation guarantees based on the error of the predictive model, and computational results on problems with non-linear interactions between the variables in each stage of the optimization problem; these aspects distinguish NEUR2BILO from prior work. 
conclusion: 
 In both its upper-and lower-level instantiations, NEUR2BILO finds high-quality solutions in a few milliseconds or seconds across four benchmarks that span applications in interdiction, network security, healthcare, and transportation planning. In fact, we are not aware of any bilevel optimization method which has been evaluated across such a diverse range of problems as existing methods make stricter assumptions that limit their applicability. NEUR2BILO models are generic, easy to train, and accommodating of problem-specific heuristics as features. One limitation of our experiments is that they lack a problem that involves coupling constraints in (1b). We could not identify benchmark problems with this property in the literature, but exploring this setting would be valuable. Of future interest are potential extensions to bilevel stochastic optimization [6] , robust optimization with decision-dependent uncertainty [28] (a special case of BiLO), and multi-level problems beyond two levels, e.g. [36] .Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: Yes. While the main paper reports averages, full distributional information for the main computational results is included in Appendix H. 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, confidence intervals, or statistical significance tests, at 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 run 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 conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: The released models do not have a high risk of misuse. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a 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] Justification: The creators either own or properly credit all code/data/models. 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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 the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. • 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. 
 
 Appendix: Bilevel optimization has been used to model attacker-defender situations, which could be used in defense or similar political contexts. We have attempted to cover more socially beneficial healthcare and transportation planning applications but duly acknowledge that our methods could be applied in rather nefarious domains. That being said, there remain many domains that could benefit from our work and that are widely beneficial, such as in the management of energy systems.Here, we outline pseudocode for NEUR2BILO. Algorithm 1 presents the pseudocode for data collection and training. Algorithm 2 presents the pseudocode for optimization. Following Algorithm 2, the objective is computed via the bilevel feasibility procedure detailed in Section 3.1. Note that data collection can be done once to collect labels for both the upper-and lower-level approximations.Additionally, a single trained model may be (and is in our experiments) evaluated across multiple test instances.Data Collection D ← {} for i = 1 to number of instances to sample do P ← sampled instance. Note that P is defined by {y : 2x + y ≤ 1} . Solution x = 1 makes the follower's problem infeasible. For solution x = 0, the optimal follower solution is y = 1 leading to the optimal value 1. Assume that the same trained neural network is used in both approaches; this is possible since leader and follower have the same objective functions. If it predicts NN(0) = 2 and NN(1) = 0, then the upper-level approximation problem (5) will return x = 1 which is infeasible whereas the lower-level approximation (7) correctly returns x = 0.F (•), G(•), f (•), g(•), Y,This section includes the full analysis of the derived approximation guarantee in Section 3.3 for the lower-level approximation with NN l (x; Θ).Recall that we look at a specific setup for which we derive approximation guarantees: the leader and the follower have the same objective function (i.e., f (x, y) = F (x, y) for all x ∈ X , y ∈ Y), we assume that Assumption 1(i) holds and that the neural network approximates the optimal value of the follower's problem up to an absolute error of α > 0, i.e.,EQUATIONWe furthermore define the parameter ∆ as the maximum difference of functions values f (x, y) -f (x, y ′ ) ≥ 0 over all x ∈ X , y, y ′ ∈ Y such that no ỹ ∈ Y exists which has function value f (x, y) > f (x, ỹ) > f (x, y ′ ).Note that ∆ can be strictly larger than zero if the follower decisions are integer.For a fixed x ∈ X , y ⋆ NN (x) denotes an optimal solution of (7). Furthermore, for any given y ∈ Y we denote by s ⋆ (x, y) an optimal slack-value in Problem (7) if the upper-and lower-level variables are fixed to x and y, respectively. Observation D.1. For any x ∈ X and y ∈ Y we haves ⋆ (x, y) = max{0, NN l (x; Θ) -f (x, y)}.Lemma D.2. Assume the leader and the follower have the same objective function and λ > 1. Then, for any given x ∈ X the following conditions hold for the optimal follower solution y ⋆ NN (x) of Problem (7) :-If NN l (x; Θ) ≥ Φ(x), then f (x, y ⋆ NN (x)) = Φ(x), i.e., (x, y ⋆ NN (x)) is feasible for the original bilevel problem. -If NN l (x; Θ) < Φ(x), then NN l (x; Θ) -1 λ ∆ ≤ f (x, y ⋆ NN (x)) ≤ Φ(x).Proof. Case 1: Let x ∈ X for which it holds NN l (x; Θ) ≥ Φ(x) and assume the opposite of the statement is true, i.e., for the optimal reaction y ⋆ NN (x) in ( 7) it holds that Φ(x) > f (x, y ⋆ NN (x)). Since λ > 0 and due to Constraint (7d) the optimal slack value for solution x in Problem ( 7) is s ⋆ (x, y) = NN l (x; Θ) -f (x, y). Assume y ⋆ (x) is the optimal follower reaction in (2) for x, then it holds that:f (x, y ⋆ NN (x)) + λs ⋆ (x, y ⋆ NN (x)) = f (x, y ⋆ NN (x)) + λ NN l (x; Θ) -f (x, y ⋆ NN (x)) > f (x, y ⋆ NN (x)) + λ NN l (x; Θ) -f (x, y ⋆ NN (x)) + (λ -1) (f (x, y ⋆ NN (x)) -f (x, y ⋆ (x))) = f (x, y ⋆ (x)) + λ NN l (x; Θ) -f (x, y ⋆ (x)) = f (x, y ⋆ (x)) + λs ⋆ (x, y ⋆ (x))where the first inequality follows since λ > 1 and f (x, y ⋆ (x)) = Φ(x) > f (x, y ⋆ NN (x)) and the latter equality follows from NN l (x; Θ) ≥ Φ(x) = f (x, y ⋆ (x)). The latter result shows that the solution (x, y ⋆ (x)) has a strictly better objective value in the surrogate problem (7) than (x, y ⋆ NN (x)) which contradicts the optimality of (x, y ⋆ NN (x)). Case 2: Let x ∈ X be a leader's decision for which NN l (x; Θ) < Φ(x) and assume the opposite of the statement, i.e., for the optimal reaction y ⋆ NN (x) in ( 7) it holds that NN l (x; Θ) -1 λ ∆ > f (x, y ⋆ NN (x)). Hence the optimal slack value in ( 7) isEQUATIONFirst, assume there exists another feasible solution ȳ(x) for Problem (7) with f (x, y ⋆ NN (x)) < f (x, ȳ(x)) < NN l (x; Θ) then solution (x, ȳ(x)) has a strictly better objective value than (x, y ⋆ NN (x)) in ( 7) since increasing the value of f by δ decreases the value of the slack variable by δ which results in a better objective value since λ > 1, which contradicts the optimality of (x, y ⋆ NN (x)). Second, assume there exists no other feasible solution ȳ(x) for Problem (7) with f (x, y ⋆ NN (x)) < f (x, ȳ(x)) < NN l (x; Θ). Then there must exists a feasible solution ȳ(x) with f (x, ȳ(x)) ≥ NN l (x; Θ) andEQUATIONby definition of ∆. In this case, we havef (x, y ⋆ NN (x)) + λs ⋆ (x, y ⋆ NN (x)) -f (x, ȳ(x)) -λs ⋆ (x, ȳ(x)) = f (x, y ⋆ NN (x)) + λs ⋆ (x, y ⋆ NN (x)) -f (x, ȳ(x)) > f (x, y ⋆ NN (x)) + ∆ -f (x, ȳ(x)) ≥ -∆ + ∆ = 0, where the first equality follows since s ⋆ (x, ȳ(x)) = 0, the first inequality follows from (10) and the last inequality follows from (11) . In summary, the latter results show that there exists a solution (x, ȳ(x)) for (7) which has strictly better objective value than (x, y ⋆ NN (x)) which is a contradiction. Note that the inequality f (x, y ⋆ NN (x)) ≤ Φ(x) follows directly from the definiton of Φ(x).The latter lemma states, that if the neural network is overestimating the follower value for a solution x ∈ X , then the surrogate problem (7) still selects an optimal follower response. However, if the neural network underestimates the value, it may happen that the surrogate problem chooses a follower response for which the objective value either is larger than the true value or differs by at most 1 λ ∆. Note that the latter term can be controlled by increasing the penalty λ.By applying Lemma D.2 we can bound the approximation guarantee of the lower-level NEUR2BILO. Theorem 3.1. If the leader and the follower have the same objective function and λ > 1, NEUR2BILO returns a feasible solution (x ⋆ , y ⋆ ) for Problem (1) with objective valuef (x ⋆ , y ⋆ ) ≤ opt + 3α + 2 λ ∆,where opt is the optimal value of (1) and λ the penalty term in (7a) .Proof. Let (x ⋆ NN , y ⋆ NN ) be an optimal solution of the surrogate problem (7) . By Lemma D.2 and by definition (8) it follows thatEQUATIONFollowing the three steps presented in Section 3.1, NEUR2BILO returns a feasible solution (x ⋆ , y ⋆ ) for Problem (2) where x ⋆ = x ⋆ NN and f (x ⋆ , y ⋆ ) = Φ(x ⋆ ). Hence the following holds:EQUATIONAssume (x ⋆⋆ , y ⋆⋆ ) is an optimal bilevel solution of Problem (1) and y ⋆⋆ NN the optimal follower response in the surrogate problem (7) . Then we havef (x ⋆ , y ⋆ NN ) + s * (x ⋆ , y ⋆ NN ) ≤ f (x ⋆⋆ , y ⋆⋆ NN ) + s * (x ⋆⋆ , y ⋆⋆ NN ) since (x ⋆ NN , y ⋆ NN )is an optimal solution of ( 7) with objective value given by (7a). From the latter inequality we obtainf (x ⋆ , y ⋆ NN ) ≤ f (x ⋆⋆ , y ⋆⋆ NN ) + s * (x ⋆⋆ , y ⋆⋆ NN ) -s * (x ⋆ , y ⋆ NN ) ≤ f (x ⋆⋆ , y ⋆⋆ ) + s * (x ⋆⋆ , y ⋆⋆ NN ) ≤ f (x ⋆⋆ , y ⋆⋆ ) + NN l (x ⋆⋆ ; Θ) -f (x ⋆⋆ , y ⋆⋆ NN ) ≤ f (x ⋆⋆ , y ⋆⋆ ) + Φ(x ⋆⋆ ) + α -(Φ(x ⋆⋆ ) -α - 1 λ ∆) = opt + 2α + 1 λ ∆where the second inequality follows from s * (x ⋆ , y ⋆ NN ) ≥ 0 and y ⋆⋆ being an optimal follower solution for x ⋆⋆ . The third inequality follows from Observation D.1 and the fourth inequality follows from (8) and from (12) applied to x ⋆⋆ . Together with (13) , this completes the proof.The bilevel knapsack problem with interdiction constraints as described in Tang et al. [54] is given bymin x∈{0,1} n ,y n i=1 p i y i s.t. n i=1 x i ≤ k, y ∈ arg max y ′ ∈{0,1} n n i=1 p i y ′ i s.t. n i=1 a i y ′ i ≤ b, y ′ i + x i ≤ 1, i ∈ [n], where x are the leader's variables and y are that of the follower. The leader decides to interdict (a maximum of k) items of the knapsack solved in the follower's problem with n the number of items, p i the profits, a i the weight of item i, respectively, and the budget of the knapsack is denoted by b.The critical node problem is described in Carvalho et al. [11] as followsmax x∈{0,1} n ,y n i=1 p d i (1 -x i )(1 -y i ) + ηx i y i + ϵx i (1 -y i ) + δ(1 -x i )y i s.t. n i=1 d i x i ≤ D, y ∈ arg max y ′ ∈{0,1} n n i=1 p a i -γ(1 -x i )(1 -y ′ i ) + (1 -x i )y ′ i + (1 -η)x i y ′ i s.t. n i=1 a i y ′ i ≤ A,where x and y are the leader's and follower's variables, respectively. Here, x denotes the decisions of the leader (defender) who selects which nodes to deploy resources to defend a set of nodes, while y are the decisions for the follower (attacker) for which nodes to attack. d i and a i are the costs for the x i and y i , respectively. D and A are the budgets for the defender and attacker, respectively. In this problem, the bilinearity arises in the objectives of both the leader and follower, which results in four outcomes for each possible combination of defending and attacking a node i. The first outcome arises when both the leader and follower do not select the node. In this case, the leader receives the full profit, p d i , and the follower pays an opportunity cost of -γp a i for not attacking an undefended node. Second is a successful attack, wherein the leader receives a reduced profit of δp d i and the follower receives the full profit p a i . Third is a mitigated attack, wherein the leader receives a profit of ηp d i for a degradation in operations, while the follower receives a profit of (1 -η)p a i for a mitigated attack. Fourth is a mitigation without an attack, wherein the leader receives a profit ϵp d i for a degradation in operations, while the follower receives a profit of 0 for a mitigated attack.The donor-recipient problem as described in Ghatkar et al. [27] , and introduced in Morton et al. [43] , is formulated asmax x∈[0,1] n ,y,y0 n i=1 w i y i s.t. n i=1 c i x i ≤ B d , (y, y 0 ) ∈ arg max y ′ ∈{0,1} n ,y ′ 0 ∈[0,1] n i=1 v i y ′ i + v 0 y ′ 0 s.t. n i=1 (c i -c i x i )y ′ i + c 0 y ′ 0 ≤ B r ,where the leader's decisions x represent those of the donor and the follower's decisions (y, y 0 ) the ones of the recipient. The profit of project i is given as w i for the leader and v i for the follower, the cost as c i , and the budget of the leader, resp. follower, as B d and B r . Next to the projects, the recipient can allocate its budget to external projects, for which the profit is given as v 0 and the cost c 0 .We use the standard formulation from Section 1 following the computational benchmarking study of Rey [47] and the code provided by the author2 .F Comparison to the Learning-Based Approach of Zhou et al. [59] This section compares our approach to a recent learning-based approach from Zhou et al. [59] based on code provided by the author 3 . We specifically compare the input-supermodular neural network (ISNN), i.e., the best-performing model from Zhou et al. [59] . Their approach requires sampling and training for each instance, which is reflected in the time, whereas the model for NN l and NN u can be trained once and evaluated across multiple instances, so the data collection and training time are excluded. We also restrict ISNN to run for one iteration given Zhou et al. [59] report very minimal improvements when increasing the number of iterations. Moreover, one iteration requires the least amount of time. [59] on the knapsack interdiction problem. n and k denote the number of items and the interdiction budget, respectively. We directly evaluate on the 180 instances (10 per size) of Tang et al. [54] ; each value is the average over 10 instances. We compare the upper-and lower-level approximations, as well as the no-learning baseline (G-VFA) and the exact algorithm (B&C).This section reports the more detailed information related to the objective values for each problem.Objective results for each problem are given in Tables 4 5 6 7 . In addition, for KIP and CNP, as the solver from Fischetti et al. [23] provides easily accessible incumbent solutions, we include two additional metrics.-The first metric "Solver Time Ratio" measures the time it takes the solver to obtain an equally good (or better) incumbent solution, divided by the solving time of the respective approximation. The number in brackets to the right indicates the number of instances for which the solver finds an equivalent solution.-The second metric "Solver Relative Error at Time" measures the relative error of the best solution found by the solver compared to the respective approximation. The value in brackets to the right indicates the number of instances for which the solver finds an incumbent before the approximation is done solving. EQUATIONIn this section, we present an ablation study comparing alternative types of value function approximation (VFA) for the lower-level approximation on the KIP. Namely, we compare the approach used the the main paper, NN l , which utilizes a slack variable to ensure feasibility. In addition, we include NN n which does not use a slack at all, and NN d , which uses the largest error in the validation set to scale the prediction down. Table 8 reports objectives, relative errors, and solving times of each method.In general, the solution quality of NN l slightly exceeds that of NN d , while NN n does significantly worse. The latter results is unsurprising given that any underestimation will cause a loss of feasibility for potentially high quality upper-level decisions. NN l is additionally generally the fastest to optimize as well.In this section, we present results with λ = 0.1 for DNDP. Table 9 presents relative error and solving times for this setting. Notably, this choice of λ tends to provide higher quality solutions than λ = 1, as reported in the main paper in Table 2 . Tuning this hyperparameter further can thus improve the already strong numerical results reported for DNDP, and possibly other problems.This section explores the impact of the use of greedy features on the KIP problem. We specifically compare a model trained purely on the coefficients to a model trained on the coefficients with additional features derived from KIP-specific greedy heuristics. From Table 10 , there is a clear advantage with the greedy features in terms of solution quality at the cost of increased solving time. The experiments for three out of four benchmarks were run on a computing cluster with an Intel Xeon CPU E5-2683 and Nvidia Tesla P100 GPU with 64GB of RAM (for training). The experiments for one benchmark were run on a virtual machine with two Intel Xeon(R) CPUs at 2.20GHz and 12GB of RAM. Pytorch 2.0.1 [44] was used for all neural network models and scikit-learn 1.4.0 was used for gradient-boosted trees in the DNDP [46] . Gurobi 11.0.1 [30] was used as the MILP solver and gurobi-machinelearning 1.4.0 was used to embed the learning models into MILPs.For all problems, we derive features that correspond to each upper-level decision variable, as well as general instance features.For KIP, CNP, DRP, we have n decisions in both the upper-and lower-level of the problems. For the learning model, we utilize a set-based architecture [58] , wherein we first represent the objective and constraint coefficients for each upper-level and lower-level decision, independent of the decision (f i ). Each of these are passed through a feed-forward network with shared parameters (Ψ d ) to compute an m-dimension embedding. The embeddings are then summed and passed through another feed-forward network (Ψ s ) to compute the instance's k-dimensional embedding. This instance embedding is then concatenated with features related to the upper-and lower-level that are dependent on the decision (h(x i )). The concatenated vector is passed through a feed-forward network with shared parameters (Ψ v ) to predict n scalar values (i.e., one for each decision). The final prediction is equal to the dot product of the n predictions with the objective function coefficients of the upper-or lower-level problem, depending on the type of value function approximation. This final step exploits the separable nature of the objective functions in question as they can all be expressed as n i=1 c i z i , where c i is a known coefficient and z i is a decision variable or a function of a set of decision variables with index i. The objectives for KIP, CNP, and DRP all satisfy this property. We leverage this knowledge of the coefficients of separable objective functions as an inductive bias in the design of the learning architecture to facilitate convergence to accurate models. The decision-dependent and decision-independent features are summarized in Table 11 .One minor remark for KIP is that since it is an interdiction problem, we multiply the concatenated vector, i.e., the input to Ψ v , by (1 -x i ) as a mask given that the follower cannot select the same items as the leader.For all instances, we do not perform systematic hyperparameter tuning. The sub-networks Ψ d , Ψ s , Ψ v are feed-forward networks with one hidden layer of dimension 128. The decision-independent feature embedding dimension (m) is 64, and the instance embedding dimension (k) is 32. We use a batch size of 32, a learning rate of 0.01, and Adam [31] as an optimizer.We train neural network models (one hidden layer, 16 neurons, a learning rate of 0.01 with the Adam optimizer) and gradient-boosted trees (default scikit-learn hyperparameters, except for n_estimators = 50). The inputs to these models are 30-dimensional binary vectors representing the subset of links selected by the leader. FeaturesKIP f i pi/ai maxi{pi/ai} , p i , a i , k/n, x dg i , y dg i , obj dg /n h(x i ) f i , x i , y g i CNP f i p d i /di maxi{p d i /di} , p a i /ai maxi{p a i /ai} , d i , a i , p a i , p d i , γ, η, ϵ, δ, A, D h(x i ) f i , x i , -γ(1 -x i ), (1 -x i ), (1 -η)x i DRP f i wi/ci maxi{wi/ci} , vi/ci maxi{ci/vi} , w i , v i , c i , B d , B r h(x i ) f i , x iTable 11 : Features for KIP, CNP, and DRP. Most features are derived directly from the objective and constraint coefficients, so refer to Appendix E for the definitions. For KIP, additional features are computed using simple greedy heuristics. For the KIP DIF, we compute x dg i , y dg i , obj dg , which correspond to a purely greedy strategy, i.e., the upper-level interdicts the k items with the largest profit to cost ratio (p i /a i ) and the lower-level decisions are the largest remaining highest profit to cost ratio items. For h(x i ) in KIP, we also include lower-level decisions based on G-VFA (y g i ).For KIP, CNP, DRP, we sample 1,000 instances according to the procedures specified in Tang et al.[54], Dragotto et al. [18] , and Ghatkar et al. [27] , respectively. For each instance, we sample 100 upper-level decisions, i.e., 100,000 samples in total. Additionally, for KIP, CNP, DRP, the lower-level problems are solved with 30 CPUs in parallel. For training, we train for 1,000 epochs. However, if the validation mean absolute error does not improve in 200 iterations, we terminate early. Data collection and training times are reported in Table 12 .For DNDP, we use the Sioux Falls transportation network provided by [47] • The experimental setting should be presented in the core of the paper to a 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, or as supplemental material.https://github.com/davidrey123/DNDP/https://github.com/bozlamberth/LearnBilevel/ 


Decision: The reviews of this paper are mixed, but I propose accepting it. The approach is novel according to the reviewer consensus. The main criticism of this work comes from the angle of solving bilevel problems in the area of neural architecture search, but I believe the application area of this paper to be sufficiently different to warrant its acceptance. The experiments are reasonable and show good performance of the approaches presented.

The authors ought to consider the following changes for the camera ready version as pointed out by one of the reviewers: 
- Expand the comparison with related methodologies, e.g.:
	[1]D. Rey, H. Bar-Gera, V. V. Dixit, and S. T. Waller, "A branch-and-price algorithm for the bilevel network maintenance scheduling problem," in Transportation Science, 2019. 
  [2] T. Tay and C. Osorio, "A sampling strategy for high-dimensional, simulation-based transportation optimization problems," in Transportation Science, 2024.
  [3] Liu, H., Simonyan, K., & Yang, Y. (2018). DARTS: Differentiable Architecture Search. In International Conference on Learning Representations.

Reviews: review: paper_summary: paper_summary: The paper studied bilevel optimization problems with discrete decision variables. The proposed framework, Neur2BiLO, adopts a learning-based approach to solve such problems, which is based on a trained neural network to approximate the leader's or follower's value functions.
strength_weakness: strength_weakness: The proposed algorithm is very straightforward in its development and lacks established performance guarantees. This limitation typically necessitates robust numerical validation. Despite multiple experiments, the evidence provided does not convincingly demonstrate superiority over existing methods.

First, the experiments on the discrete network design problem (DNDP) are conducted on the relatively small Sioux-Falls network. I recommend testing on larger networks, such as the Chicago-Sketch [1], to better assess scalability. 

[1] https://github.com/bstabler/TransportationNetworks

Second, a significant application, neural architecture search (NAS), is missing from the study. NAS and DNDP share conceptual similarities: one designs neural networks, and the other transportation networks. Traditionally, NAS often employs continuous relaxation for efficient architecture search using gradient descent. However, given that the proposed algorithm directly manages discrete bilevel optimization, it opens the possibility of exploring NAS without needing such relaxations. 

[2] Liu, H., Simonyan, K., & Yang, Y. (2018, September). DARTS: Differentiable Architecture Search. In International Conference on Learning Representations.
questions: questions: 1. Can the proposed algorithm be extended to continuous network design problems? If not, please explain the reasons. 

2. Can the proposed algorithm be applied to neural architecture search? If not, please explain the reasons.
limitations: limitations: Please find my comments about the limitations in other parts of the review.
paper_summary: paper_summary: The paper develops a neural method to solve bi-level optimization problems. It begins with a motivating application and then proposes NEUR2BILO, which utilizes two layers of neural networks to approximate solutions for the upper and lower levels.
strength_weakness: strength_weakness: 1. The paper is not very friendly to readers who are not engaged in this specialized area. The problem addressed has many challenging issues, such as bi-level, non-linear, and mixed-variable components. I wonder how the authors address each of these challenges, as it is not very clear in the current presentation.

2. The paper introduces two models, NN^u and NN^l, designed to generate solutions for the upper and lower levels, respectively. Then, I would expect that  the combination of the two models will solve the entire bi-level problem. However, in the experiments, NN^u and NN^l are compared in parallel, which is confusing.

3. I am struggling to identify the major contribution of this study to the learning to optimize area. The paper's organization makes it difficult to grasp the main points clearly.

4. The major body of the paper is not self-contained, requiring frequent switching between the main text and the appendix to obtain necessary information.
questions: questions: See weaknesses.
limitations: limitations: See weaknesses.
paper_summary: paper_summary: The paper tackles the bi-level optimization problem (BiLo) in general. BiLO can be seen as the problem of a leader computing a strategy (x) to commit to, such that the leader’s objective is optimized subject to the follower’s best response (y) to the committed strategy. The paper provides two ML-based approaches, one is the upper-level approximation that learns to predict a mapping from x to the leader’s objective, and the other is the lower-level approximation that learns to predict the utility of the follower given x. Both approaches reformulate the BiLO into a single-level mathematical program. The paper also provides approximation analyses for the lower-level approximation. The error term is an additive function of ML regression errors and a gap of f values due to discontinuity. In experiments, both approaches are evalutated on 4 different BiLO problems and compared against B&C, heuristics and exact solvers.
strength_weakness: strength_weakness: Note that I have reviewed this paper in the past and I am frankly surprised that it was rejected.
The authors have addressed most of my concerns last time.

These are not major weaknesses but still should be pointed out: 
The effectiveness of this approach mainly depends on how closely ML can learn to approximate \Phi(x) or F(x,y*). In general, this looks like a very challenging task and it is the bottleneck of these approaches. In this case, it just happens that the regression task is easy for the four benchmarks.
Furthermore, the theoretical approximation guarantees are not that surprising given that the prediction error is assumed to be bounded.
questions: questions: I don't have any questions.
limitations: limitations: The applicability of this approach seems to be largely dependent on the ML regression errors. The authors have discussed limitations of their work in the paper.
paper_summary: paper_summary: This paper proposes two approximate methods for solving constrained, mixed-integer, non-linear bilevel optimization problems. The core idea is to convert the bilevel problem into a single level problem by clever use of neural networks trained offline by solving single level optimization problems. The upper-level approach trains a NN to predict for a fixed leader decision, the leader objective function assuming the follower acts optimally. A single level optimization problem can then be solved by replacing the lower level problem with the NN. The other approach uses the value function reformulation for bilevel problems and aims to train a neural network to learn the optimal value of the lower level problem, given a leader decision.

The performance/capability tradeoffs for each method across different classes of bilevel problems is thoroughly discussed, and some theoretical analysis is provided which depends on the approximation error of the true objective/value function. Importantly, the algorithm has a "post-processing" step where the approximate solutions from Neur2BiLO are refined to ensure feasibility of the original bilevel problem.

Neur2BiLO is thoroughly evaluated on several challenging benchmark problems to highlight the generality and effectiveness compared to exact baselines and other learning-based methods.
strength_weakness: strength_weakness: This is a minor weakness but none of the problems evaluated have coupled constraints. It would be great if Assumption 1 i) were satisfied but the constraints were coupled.

The theory around the approximation error to the true underlying functions is discussed in Sec. 3.1, which is nice, but it is unclear whether or not for these class of problems that the optimal value function of the follower's problem is actually smooth. I think this is important to at least have some discussion of this to caveat the bounds, since the approximation error in (8) may not be attainable.
questions: questions: - Lines 161-173: My understanding is that this is a sensible heuristic approach which refines the approximation to satisfy constraints 2b, 2c imposed in (1). Specifically, there is no guarantee that the solution is optimal, but it is probably a good solution which is feasible. Can you please confirm or correct my intuition please? It was not completely clear from reading the paper whether or not this is the case.

- This relates to one of the weaknesses. Is it reasonable to assume in general that the value function of the lower level problem or the optimal objective function of the outer level function is smooth?
limitations: limitations: Limitations have been discussed.

Comments: title: Response to reviewer
Response to Authors' rebuttal
comment: Thank you for the clarification.  We agree that including a discussion on this would be a great addition, and we will do so in the final version of the paper.
Thanks for the response. I will keep my score.
Thank you for your detailed response and for agreeing to address my concerns and limitations. I still think this is a very strong paper and would advocate for acceptance.

Re my concern about smoothness: My question was motivated by the universal approximation theorem and the general ability for a neural network to approximate a function which may not be continuous (the value function in this case). It would be nice to have a little bit of discussion around the approximation error (empirical insights or general discussion like in your response will suffice) for the other more general problems where discontinuous value functions may arise.

I appreciate that Theorem 3.1 is for a particular class of problems and does not require any assumption on the value function specifically.