Neur2BiLO: Neural Bilevel Optimization
Authors: Justin Dumouchelle
Esther Julien
Jannis Kurtz
Elias Boutros Khalil
Venue: NeurIPS 2024 poster (2024)
Keywords: bilevel optimization
machine learning
discrete optimization
integer programming
Primary area: optimization
TL;DR: This work proposes a learning-based approach for quickly computing high-quality solutions for several challenging classes bilevel optimization problems (linear/non-linear, integer/mixed-integer) via learning-based value function approximation.

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.

NEUR2BILO: Neural Bilevel Optimization
Justin Dumouchelle"
Esther Julien TU Delft
Jannis Kurtz University of Amsterdam
Elias B. Khalil University of Toronto
University of Toronto
Abstract
Bilevel optimization deals with nested problems in which a leader takes the first decision minimize their objective function while accounting for a follower's best-response reaction. Constrained bilevel problems with integer variables are par- ticularly 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 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 bilevel problem are solved routinely, our proposed framework, NEUR2BILO, embeds a neural network approximation of the leader's follower's value function, trained via supervised regression, into an rasy-to-solve mixed-integer program. NEUR2BILO serves as heuristic that produces high-quality solutions extremely fast for four applications with linear and non-linear objectives and pure and mixed-integer variables.
Introduction
A motivating application. Consider the following discrete network design problem (DNDP) 47 48]. transportation planning authority seeks to minimize the average travel time on road network represented by a directed graph of nodes N and links A₁ by investing in constructing a set of roads (i.e., links) from of options A2, subject a budget The planner knows the number of vehicles that travel between any origin-destinatee take into account the drivers' reactions to this decision. One common assumption that drivers will optimize their O-D paths such that user equilibrium is reached. This is known Wardrop's 's second principle the traffic assignment literature, an equilibrium in which "no driver can unilaterally reduce their travel costs by shifting another route" [1]. 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 model the travel time on an edge as a function of traffic. Let Cij E R4, be the capacity (vehicles per hour (yph)) of a link and Ti E R. the free-flow travel time (i.e., travel time the link without congestion). The US Bureau of Public Roads uses the following widely accepted formula to model the travel time t(Hi)) ) on a link used by Yij vehicles per hour: ty,,) = Tip + O. 0.15(y63/ (55(5//c))))))) (cr As the traffic Vij grows to exceed the capacity Cıj. a large quartic increase in travel time is incurred [41].
(O-D) pair of nodes. A good selection of links should
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 's (the follower's ') best response. In the DNDP, the leader the transportation planner and the follower the population of
"Correspondigg author; justin. htw.:a/ddummmcchelemmmmalll.... uto.ommooom...uuoooooooooooo
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

drivers, giving rise to the following optimization problem
min XE (0.1)II
Σ
yisl(yis)
(JEE
s.t.
Σ
DifTij S B,
(6.)
Σ fod
y arg min y'ER4""
1e toy(v)do
(GJEA
y' is valid network flow, J/5
Fay
where Ag n = 0,
The leader minimizes the total travel time across all links subject a budget constraint and the followers' equilibrium which is expressed 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 to Tiybiy +
0.15T:J
(3/))
5
5el
Going beyond the DNDP, Dempe [6 lists more than 70 applications of BiLO ranging from pricing in electricity markets (leader is an clectricity-supplinng retailer that sets the price 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- non-linen -ineir bilevel optimization problems. simply referred to hereafter as bilevel optimization or BiLO, 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 BiL.O:
1. The state-of-the-ee the-trtt exact solvers of Fischetti et al. [4 and Tahernejad 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-at exact Knapsack Interdiction solver (57) only works for a single knapsack constraint and fails with two or more, a significant limitation even 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 "casy": : For 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 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, 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 regressor mapping 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., feedforward ReLU neural network 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.
decision tree, is possible to use a MIP solver find the leader's
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 heuristic version of the well-known value function reformulation (VFR) BiLO. The VFR transforms bilevel problem into single-level one, assuming that one can represent the follower's value (as function of the leader's decision) compactly. This is typically impossible as the value function may require an exponential number of constraints, 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 constant, additive absolute optimality gap which mainly depends on the prediction accuracy of the regression model.
Through series of experiments (i) the bilevel knapsack interdiction problem, (ii) the "critical node problem" from network security, (ii) a donor-recipient healtheare 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-un methods.
Background
Bilevel optimization (BiLO) deals with hicrarchical problems where the leader (or upper-level) problem decides on x E X and parameterizes the follower (or lower-level) problem that decides on y ); the sets X' and y represent the domains of the variables (continuous, mixed-integer, pure integer). Both problems have their own objectives and constraints, resulting in the following model:
min xEX.y
F(x,y)
(1a)
s.t.
G(x,y) 2 0,
(lb)
y E arg [f [(x y') 2 0), y'Ey
(1c)
where consider the general mixed-integer non-linear case with f RR G: Rmm, and : X' x y > m2 non-linear functions of the upper-level x and lower-level variables y.
The applicability of exact (i.e., global) approaches critically depends the nature of the lower-level problem. A continuous lower-level problem admits a single-level reformulation that leverages the Marush-Kuhn-Tuckee (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 [ do not allow for coupling constraints (i.e., G y) = G(x)) and both methods do not allow continuous upper-level variables to appear in the linking constraints (g(x,))). Other approaches, such as Benders decomposition, are also applicable (25). Gümüiş 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-sanee sandwchn methods were proposed [33 45 where bounds 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.
Assumptions.
what follows, we make the following standard assumptions:
1. Either (i) the follower's problem has a feasible solution for each x X, (ii) there are coupling constraints in the leader's problem, i.c., G(xx y) = G(x);
2. The optimal follower value always attained by a feasible solution [see 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, ss the one that optimizes the leader's 's objective is implemented. We can then rewrite problem ( using the value function reformulation (VFR):
min x xEX
F(x,y)
(2a)
s.t.
G(x,y) 2 0.
(2b)
g(x,y) 0,
(2c)
f(x,y) 2 $(x),
(2d)
3

---

with the optimal lower-level value function defined as
((x)
max (xx,))(()))))))))))))))))))))))) g(x,)) 0}.
ycy'
Lozano 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. propose a family of evolutionary heuristics continuous non-linear BiLO problems that approximate the optimal value function by using quadratic and Kriging (i.c., function interpolation method) approximations. Taking it one step further, Beykal et al. [9] extend the framework of the previous authors to handle
Sinha et al. [50 51 52
variables in the lower level.
3 Methodology
NEUR2BILO refers to two learning- based single-level r reformulations for general BiLO problems. The reformulations rely on representing the thomy nested structure 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.
3.1 NEUR2BIL.O
Upper-level approximation. The obvious bottleneck solving BiLO problems is their nested structure. One rather straightforward way of circumventing this diffieulty is 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 as
NNW xx θ) N F(x,y*),
where @ are the weights of a neural network, F the objective function of the leader (bb). and y* an optimal solution to the lower level problem (3). To train such model, one can sample x from X' solve (3) to obtain optimal lower-level solution y", and subsequently compute label F(x, y*).
We can then model the single-level problem as
min XEX
NN θ) s.t. G(x) 2 0,
(5)
where we only optimize for x and thus dismiss the lower-level constraints and objective function. trained feedforward neural network NN (::O): with ReLUU activations can represented 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 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 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 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 (d)). where the right-hand side the optimal value of the lower-level problem, parameterized by x. We introduce learning-based VFR in which ((x) is approximated by a regression model with parameters O:
NN' θ) ((x).
(6)
Both NN! and N take in leader's decision as input and require solving the follower (3) for data generation. By replacing (xx with NN' (x: θ) in 2d and introducing slack variable R., the

---

surrogate VFR reads as:
min xEA.yE> $20
F(x,y) + As
(7a)
s.t.
G(x,y) 2 0,
(7b)
g(x,y) 2
(7c)
f(x,y) NN (x: 0)
(7d)
All follower and leader constraints the original BiLO problem are part of Problem
7 However,
without the slack variable the problem could become infeasible due to inaccurate predictions by the neural network. This happens when NN' (x; θ) strictly overestimates the follower's optimal value for each x. In this case, there does not exist follower decision for which Constraint (7d) is satisfied. A value of s > 0 can be used to make Constraint (7d) satisfiable at cost of As in the objective, guaranteeing feasibility.
Bilevel feasibility.. Given solution x" solution pair (x", y) returned by our upper- lower- level approximations, respectively, we would like to produce a lower-level solution y* such that (x",y" y") ( is bilevel-feasible, i.e., it satisfies the original BiLO in ① The following procedure achieves this goal:
1. Compute the follower's optimal value under x*, p(x*), ), by solving (3)
2. Compute ailevel-feasible follower solution y* by solving problem with fixed xt and the right-hand side of (2d) set to (xx*), ), a constant. Return (x", y
only Assumption Ti) is satisfied, then only the lower-level approximation is applicable and this procedure guarantees optimistic hilevel-feasibe solution for it. If only Assumption [T is satisfied, then this procedure can detect in Step I that an upper-level approximation' 's solution x" does not admit follower solution, i.e., that it is infeasible, calculates feasible y* if exists in Step 2. If both Assumptions ii) and are satisfied simultaneously, then this procedure guarantees an optimistic bilevel-feasible solution for either approximation.
Upper- v.s. lower-level level approximation. Here, we note two important trade-offs between the upper- and lower-level approximations.
Appendix Coppendix[shhvve shows that under Assumption I [i), it may happen that solving the upper-level heteeelppppxiiiii approximation problem variant (5) returns an infeasible solution while the lower-level variant does not.
Generality:
Example C.I
Scalability: The upper-level approximation has fewer variables and constraints than its lower- level counterpart as it does not represent the follower's 's problem directly. For problems in which the lower-level problem is large, e.g., necessitating constraints for each node and link to enforce 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 final solution quality. This tradeoff will be assessed experimentally.
Limitations. Since NEUR2BILO is in essence a learning-bart based heuristic, it does not guarantee an optimal solution to the bilevel problem. However, it guarantees feasible solution with the lower-level approximation and can only give an infeasible solution while using the upper-level approximation when only Assumption i(ii) is satisfied. Moreover, will be shown Section 3.3 the performance of NEUR2BIL depends on the regression error, which is generally the case when integrating machine learning optimization algorithms. Empirically, we note that the prediction error achieved on every problem is very low (see Appendix K.
3.2 Model architecture
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 single model that can deployed on a family of instances. This is done by leveraging information such as coefficients in the objective and constraints for each problem.
5

---

For the model's architecture, the general principle deployed is to first explicitly represent or learn instance-based features. The second is combine anstance-based features with (leader) decision variable information to make predictions.
The overall architecture
be summarized the following set of operations. Fix a particular instance of a BiLO problem and let n be the number of leader variables, f; a vector of features for each leader variable x; (independently of the variable's value), and h(x;) a feature map that describes the ith leader variable for specific value of that variable. The functions T V and D are neural networks with pepropriat input-output dimensions. The vector θ includes all learnable parameters of networks V Via, and Tr. The functions SUM, CONCAT, and AGGREGATE, 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 simply summing them up), respectively. Our final objective value predictions are then given by the following sequence of steps:
up
1. Embedding the set of variable features {fi} using a set-based architecture, e.g. the same network vd, summing up the resulting n variable embeddings, then passing the resulting vector to network T yielding vector we refer to as the INSTANCEEMBEDDING:
INSTANCHEMBEDDING = (' (()))))
This is akin the DeepSets approach of Zaheer 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 specific assignment of values to the leader's decision vector per-variable embedding is computed by network T to allow for interactions between the INSTANCHEM- BEDDING and the specific assignment of variable as represented by hxx)): v (CC)N))TT(b(x... INSTANCEEMBEDDING))
VARIALLEMBBEDDNNG()
3. The final value prediction for either of our approximations aggregates the variable embeddings possibly after passing them through function g::
NN(x; θ) = AGGREGATE( {9. [VARIABBLEEMBEEDDNN((()))
For example, the follower's 's objective is linear function and VARIABLEEMBEDDDNN()) is scalar, then it is useful to use the variable's known objective function coefficient d, here, i.e.: gi gi (VARIABLEEBEEDDNNGG
= d, d,-VARIABE VARIABLEEMBEDDINGG) The final step is to aggregate the per-variable 9-(+) outputs, e.g., by summation for linear separable objective functions.
NEUR2BILO is largely agnostic the learning model utilized long as it is MILP relpeeeerese........ 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.
3.3 Approximation guarantees
Lower-level approximation. Next, we present an approximation guarantee for the lower-level approximation with NN' G). Appendix IoppendxxDlineee includess the complete proofs.
Since the prediction of the neural network is only an approximation of the true optimal value of the follower's problem (xx). NEUR2BILO may return sub-optimal solutions for the original problem (I. We derive approximation guarantees for 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 E X E ))), and Assumption ii) holds. Consider neural network that approximates the optimal value of the follower's problem up to an absolute error of a > 0, i.e..
for all X. Furthermore, we define the parameter A as the maximum difference f(x, y) f(x, > over all
INN (x; +) (xx) S
(8)
E X, y, y' E y such that no ý E y exists which has function value f(x, ) > f(x, y)
> f(x, y').
We can bound the approximation guarantee the lower-level NEUR2BILO as follows:
Theorem 3.1. If the leader and the follower have the same objective function and X > 1. NEUR2BILO returns a feasible solution (x*, ,²,,") for Problem ( with objective value
2
f(x", S opt + +
-
X
where opt is the optimal value of ① and X 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 E X' an upper-level objective value that deviates at most a > 0 from the true one, then the returned solution trivially approximates the true optimal value with an absolute error of at most 2a. This follows since the worst that can happen is that the objective value of the optimal solution is overestimated by a while a solution with objective value opt + 2a is underestimated by and hence has the same predicted value as the optimal solution. Problem ( then may return the latter sub-optimal solution.
4 Experimental Setup
Benchmark problems and their characteristics are summarized in Table [ their MIP formulations are deferred to Appendix L and brief descriptions follow:
The leader interdicts a subset of at most items and the follower solves knapsack problem over the remaining (non-interdicted) items. The leader aims to minimize the follower's (maximization) objective.
Knapsack interdiction (KIP) 10
Critical node problem (CNP) [18, [1]: 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. [8).
Donor-recipient problem (DRP) [27]: This problem relates to the donations given by certain agencies 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.
This is the problem described in Section 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-ar method of Fontaine and Minner [25]. This network and corresponding instances are representative of the state of the DNDP in the literature.
Discrete network design problem (DNDP) 47
Leader
Follower
Problem
Obj. Cons.
Obj. Cons.
KIP (L7)
B
Lin Lin
B
Lin
Lin
CNP (11)
B BLin Lin
B
BLin
Lin
DRP (1T)
C Lin
Lin
MI
Lin
BLin
DNDP
(U7)
B NLin
Lin
C
NLin
Lin
Table I: 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 con- straint. The arrows refer to minimization
(L) or maximization (f) in leader and follower, respectively. B = Binary, C Continuous, MI = Mixed-Integer Lin = Linear, BLin = Bilinear, NLin Non- Linea.
Baselines. As mentioned previously, the branch-and-cut (B&C) algorithm by Fischetti et al. 24 considered to be satte-of-theant for solving mixed-integer linear BiLO. The method is applicable 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-cur paradigm (B&C+) from Ghatkar et al. (27]. For DNDP, the follower's 's problem only has continuous variables, so the baseline is method based on KKT conditions (MKKT) (25). Of the learning-basse 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-100x smaller mean relative error roughly 1000 faster; full results are deferred to Appendix F
Data collection & Training. For each problem class, data is collected by sampling feasible leader decisions and then solving (xx) to compute either the upper- lower-level objectives as labels. We then train regression models minimize the least-squares error on the training samples. Typically, data collection and training take less than one hour, negligible cost given that for larger instances
7

---

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 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 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' and NN", respectively. For NN' we set À = 1 for all results presented in the main paper. Details of the computing setup are provided in Appendix Our code and data are available at https:
cow/khalil reeaeeerrereaaeeeerBi....
Experimental Results
We summarize the results as measured by average solution times and mean relative errors (MREs). The relative error on given instance is computed as 100 vdjjA-objvaal where obj,A is the value of [objnese]
the solution found by method A and objoest the best-known objective value for that instance. These
results are reported in Table 2 More detailed results and box box-plots of the distributions of relative
errors are in Appendices G and Our experimental design answers the following questions:
Q1: Can NEUR2BILO find high-quality solutions quickly on classical interdiction problems?
Table|Ccomant NEUR2BILO to the B&C algorithm of Fischetti al. [24]. NEUR2BILO terminates in 1-2% of the time required by B&C on the smaller (n S 30) well-studied KIP instances of Tang et al. (54). However, when the instance size increases to n = 100, both NN and NN find much better solutions than NEUR2BILO in roughly 30 seconds, even when B&C runs for the full hour. Furthermore, Table in Appendix BenddixxGssooo shows that B&C requires 10 to 1, 000x more time than NN' or NN to find equally good solutions. In addition, the best solutions found by B&C at the termination times of NN or NN 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., = = ry in the upper- and lower-level variables, resulting challenging problem for ceneral-purposs B&C. In this case, both NN' and NN tend to outperform B&C as the problem size increases. In addition, the results on incumbents reported in Table in Appendix G are as good, if not even stronger than those of KIP.
a much more
Secondly, we discuss DRP (Table 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" 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 Table for the DNDP. In this setting, we focus on a limited-time regime wherein we compare NEUR2BILG with 5-second time limit to MKKT at time limits 5, 10, and 30 seconds. NN 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 (c.g., what-if analysis of various candidate roads, budgets, etc.).
NN', on the other hand, takes longer than N but computes solutions that are more competitive with the baseline, the latter requiring 5x more time. We suspect that the better solution quality from NN' is due to its explicit modeling of feasible lower-level decisions that "align" with the predictions, whereas NN may simply extrapolate poorly. In terms of computing time, one computational burden for NN' 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 incluude 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.
8

---

Knapsack Interdiction Problem
# Items
Interdiction Budget
NN
NN
G-VFA
B&C
(1)
18
5
1.48
0.59
1.48
0.34
1.82
0.14
0.00
9.55
18
1.51
0.59
1.51
3.97
5.81
18
14
0.00
0.22
0.00
0.17
64,22
0.03
0.00
0.39
20
5
0.41
0.62
0.41
2.19
23.18
20
10
0.99
0.66
0.99
0.58
0.99
0.36
0.00
10.27
23.39
22
6
0.71
0.19
0.71
0.18
U.42
0.18
0.00
42.30
22
1.01
0.28
0.28
1.08
16.26
22
17
14.43
0.24
14.43
0.15
14.43
0.13
0.00
0.68
25
0.44
2.66
0.44
0.44
0.64
137.96
25
13
1.42
2.75
1.42
2.79
3.85
1.24
0.00
48.43
25
2.49
0.48
2.49
0.38
2.49
0.13
0.00
1.77
28
7
0.39
0.67
0.39
0.74
0.26
0.62
0.00
309.18
28
14
0.75
2.10
0.75
1.45
1.37
1.29
0,00
120.74
28
21
1.14
0.45
1.14
0.49
3.16
0.31
0.00
4.92
30
0.00
1.54
0.00
1.54
0.43
0.97
0,00
792.4
30
0.49
3.64
0.49
187.23
30
23
2.29
1.08
2.29
0.73
4.48
0.25
0.00
5.65
3,600.40
100
50
0.96
51.68
0.96
49,28
0.04
53.74
8.96
3,600.44
23.78
35.27
3,600.52
Avg. 30
1.86
1.06
1.86
0.91
7.21
0.47
0.00
95.43
Aug.
0.66
27.15
31.07
3,600.45
Critical Node Problem
Nodes (VV1)
NN!
NN
B&C
MRE
Time
MRE
Time
MRE
Time
10
3.20
0.04
2.75
0.02
1.01
4,24
2,60
0.23
0.05
0.73
50
1.42
0.38
0.98
0.10
0.67
3,600.30
100
1.12
0.48
0,56
0.42
1.79
3,600.65
300
2.01
1.12
0.33
0.83
2.32
3,600.54
500
1.33
1.09
0.45
1.19
2.47
3,600,80
Average
1.95
0.66
1.14
0.43
1.50
2.941.99
Discrete Network Design Problem
NN:
NN
MKKT
Edges
Budget
MRE
Time
MRE
Time
MRE-5
MRE-10
MRE-30
2.95
5.78
10
0.5
0.73
3.35
1.22
0.01
6.47
2.17
0.00
10
0.75
0.47
2,80
1.32
0.00
5.80
0.02
0.06
5.02
2.64
7.78
20
0.5
1.01
4.91
4.36
0.03
6.00
2.52
0.64
20
0.75
0.85
4.47
0.91
0.01
7.87
0.22
0,11
Average
1.72
3.92
1,80
0.01
6.62
1.76
0.29
Table 2: Mean relative error (MRE) and solving times for KIP, CNP, and DNDP. For KIP with S 30, we directly evaluate on the 180 instances (10 per size) of Tang et al. (54]; each value is the average over 10 instances. For = 100, our evaluation instances (100 per size) are generated using the same procedure of Tang et al. [54). The no-learning baseline GFVFA 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 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), KIP-specific approximation that relies on the fact that greedy algorithms are typically good for I-dimensional knapsack problems. Namely, the heuristic based on ordering the items with their value-to- ratio [15] and is used as the knapsack solution in the follower problem, while still being parameterized by x. This heuristic embedded in a single-level problem this heuristic 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 some cases outperforms NN' and N but there are clear cases where NN' and N outperform G-VFA demonstrating that learning is beneficial. In addition, heuristics like G-VFA can be utilized to compute features for NN' and N For KIP, the inclusion of these features derived from G-VFA strongly improves the results (see
represeeeeett [see MI; we note

---

Table 10 in Appendix 1.3). reeP--epreeettable heuristics as features for learning.
This demonstrates that there is value in leveraging any problem-specine
Q5: How does À affect NN'? Table 9 in Appendix 1.2 shows that slack penalty of À = 0.1 improves the performance of NN' on some instances for DNDP, compared to the reported in 2 indicating that tuning over À might be beneficial. 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 in Appendix L.1
6 Related Work
and Beykal et al. [9] discussed in Section 2 other learning- based methods have been introduced to solve BiLO problems. Bagloee et al. (2 present heuristic for DNDP which uses a linear prediction of the leader's objective function. An iterative algorithm refines the prediction with new solutions, terminating after a pre-determined number of iterations. Chan et al. 13 propose to simultaneously optimize the parameters of learning model for subset of followers in large-scale cycling network design problem. Here, only non-parametric or linear models are utilized as optimizing more sophisticated learning models is generally challenging with MILP-based optimization. Molan and Schmidt [42] make use of a neural network to predict the follower variables. The authors assume a setting with black-box follower's s problem, no coupling constraints, and continuous leader variables. Another learning-bar based heuristic is proposed by Kwon et al. [35) for bilevel knapsack problem. This approach knapsack-speciffe and requires a sophisticated, GPU-based, problem-spectee graph neural network for which no code is publicly available. Zhou et al. [59 propose 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-supermodule 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, 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) 33).
Learning for bilevel optimization. Besides the approaches of Sinha et al. [50 52
Data-driven optimization. The integration of a trained machine learning model into MIP is vital element of NEUR2BILO. This is possible due to MILP formulations of neural networks [4] 22
and of other predictors like decision trees 38 g
These methods have become easily applicable and the cooobi-machineeeetaee
library. More similar to our setting the approaches in [99 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 BiL.O, particularly in the lower-level approximation which performs well in highly-constrained BiI.O 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.
due to open software implementations 12 40 55
One such application is constraint learning 21
7 Conclusion
In both its upper- and lower-level instantiations, 2EUR2BILO finds high-quality solutions in 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. 2BILO models are generic, easy to train, and accommodating of problem-specificc heuristics as features. One limitation of our experiments is that they lack a problem that involves coupling constraints in (Ib). 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-dependen uncertainty (8 (a special case of Bil.O,, and multi-level problems beyond two levels, e.g. [36..
10

---

Acknowledgments
Dumouchelle, Julien, and Khalil acknowledge funding support from the Natural Sciences and Engi- neering Research Council Discovery Grant Program and the SCALE AI Research Chair Program. Julien received funding from the Dutch Research Council (Nederlandse Organisatie voor Wetenschap- pelijk Onderzoek, NWO) under project OCENW.GROOT.201.0055.
References
[1] David Avis, David Bremner, Hans Raj Tiwary, and Osamu Watanabe, Polynomial size linear programs for problems in p. Discrete Applied Mathematics, 265:22-39, 2019.
[2] Saeed Asadi Bagloce, Mohsen Asadi, Majid Sarvi, and Michael Patriksson. A hybrid machine- learning and optimization method to solve bi-level problems. Expert Systems with Applications, 95:142-152, 2018.
[3] Maria-Florina Balcan. Data-driven algorithm design. arXiv preprint arXiv:201 2020.
[4] Jonathan F Bard. Practical bilevel optimization: algorithms and applications, volume 30. Springer Science Business Media, 2013.
[5] Yasmine Beck and Martin Schmidt. A gentle and incomplete introduction to bilevel optimization. Lecture notes, 2021.
[6] Yasmine Beck, Ivana Ljubić, and Martin Schmidt. A survey bilevel optimization under uncertainty. European Journal of Operational Research, 2023.
[7] David Bergman, Teng Huang, Philip Brooks, Andrea Lodi, and Arvind U RRghunathann. JANOS: an integrated predictive and prescriptive modeling framework. INFORMS Journal on Computing. (4(2):877-816, 2022.
[8] Dimitris Bertsimas, Jack Dunn, and Yuchen Wang. Near-optimal nonlinear regression trees. Operations Research Letters, 49(2):201-206, 2021.
[9] Burcu Beykal, Styliani Avraamidou, loannis PE Pistikopoulos, Melis Onel, and Efstratios N Pistikopoulos. Domino: Data-driven optimization of bi-level mixed-integer nonlinear problems. Journal of Global Optimization, 7-:1-3, 2020.
[10] Alberto Caprara, Margarida Carvalho, Andrea Lodi, and Gerhard Woeginger. Bilevel knapsack with interdiction constraints. INFORMS Journal on Computing, 28(2):319-333, 2016.
[11] Margarida Carvalho, Gabriele Dragotto, Andrea Lodi, and Sriram Sankaranarayanan. Integer programming games: gentle computational overview. In Tutorials in Operations Research: Ad- vancing the Frontiers of OR/MS: From Methodooogies to Applications, pages 31-51. INFORMS, 2023.
[12] Francesco Ceccon, Jordan Jalving, Joshua Haddad, Alexander Thebelt, Calvin Tsay, Carl D Laird, and Ruth Misener. OMLT: Optimization & machine learning toolkit, arXiv preprint arXiv:2202.0244 2022.
[13] Timothy CY Chan, Bo Lin, and Shoshanna Saxe. A machine learning approach solving large bilevel and stochastic programs: Application to cycling network design. arXiv preprint arXiv:2209.0 09404, 2022.
[14] Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. Maximum resilience of artificial neural networks. In International Symposium Automated Technology for Verification and Analysis, pages 251-268. Springer, 2017.
[15] George B Dantzig. Discrete-variable extremum problems. Operations research, 5(2):266-288, 1957.
[16] Stephan Dempe. Bilevel optimization: theory, algorithms, applications and a bibliography. Bilevel Optimization: Advances and Next Challenges, pages 581-672, 2020.

---

[17] Scott T DeNegre and Ted K Ralphs. A branch-and-cut algorithm for integer bilevel linear programs. In Operations research and cyber-infrassruuctuee, pages 65-78. Springer, 2009.
[18] Gabriele Dragotto, Amine Boukhtouta, Andrea Lodi, and Mehdi Taobane. The critical node game, 2023.
[19] Justin Dumouchelle, Rahul Patel, Elias B Khalil, and Merve Bodur. Neur2SP: Neural two-stage stochastic programming. Advances in Neural Information Processing Systems, 35, 2022.
[20] Justin Dumouchelle, Esther Julien, Jannis Kurtz, and Elias Boutros Khalil. Neur2RO: Neural two-stage robust optimization. In The Twelfth International Conference on Learning Represen- tations, 2024.
[21] Adejuyigbe O Fajemisin, Donato Maragno, and Dick den Hertog. Optimization with constraint learning: framework and survey. European Journal of Operational Research, 2023.
[22] Matteo Fischetti and Jason Jo. Deep neural networks and mixed integer linear optimization. Constraints, 23(3):296-33) 0099,63----00000 2018.
[23] Matteo Fischetti, Ivana Ljubić, Michele Monaci, and Markus Sinnl. Intersection cuts for bilevel optimization. In Integer Programming and Combinatorial Optimization: 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings 18, pages 77-88. Springer, 2016.
[24] Matteo Fischetti, Ivana Ljubić. Michele Monaci, and Markus Sinnl. A new general-purposs algorithm for mixed-integer bilevel linear programs. Operations Research, 65(6)1615-11677, 2017.
[25] Pirmin Fontaine and Stefan Minner. Benders decomposition for snserete-conninnoee linear bilevel problems with application to traffic network design. Transportation Research Part B: Methodologiccl, 70:163-1111 163-12,,, 2014.
[26] Alireza Ghahtarani, Ahmed Saif, Alireza Ghasemi, and Erick Delage. A double-oracle, logic- based benders decomposition approach to solve the k-adaptability problem. Computers & Operations Research, 155:106243, 2023.
[27] Shraddha Ghatkar, Ashwin Arulselvan, and Alec Morton. Solution techniques for bi-level knapsack problems. Computers & Operations Research, 159:10 2023.
[28] Marc Goerigk, Jannis Kurtz, Martin Schmidt, and Johannes Thürauf. Connections and reformu- lations between robust and bilevel optimization. optimization-onling pre-print, 2023.
[29] Zeynep H Gümüş and Christodoulos A Floudas. Global optimization of mixed-integer bilevel programming problems. Computational Management Science, 2:181-212, 2005.
[30] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023. htRl:sttss:///
gurobi com.
[31] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 141.6690, 2014.
[32] Thomas Kleinert, Martine Labbé, Ivana Ljubić, and Martin Schmidt. survey on mixed- integer programming techniques in bilevel optimization. EURO Journal on Computational Optimization, 9: 10000, 2021.
[33] Polyxeni-M Kleniati and Claire Adjiman. A generalization the branch- wath--and------wieee algo- rithm: from continuous to mixed-integer nonlinear bilevel problems. Computers & Chemical Engineering, 72:373-386, 2015.
[34] Jan Kronqvist, Boda Li, Jan Rolfes, and Shudian Zhao. Alternating mixed-integer programming and neural network training for approximating stochastic two-stage problems. arXiv preprint arXiv:2305.06788 2023.
[35] Sunhyeon Kwon, Hwayong Choi, and Sungsoo Park. Solving bilevel knapsack problem using graph neural networks. arXiv preprint arX1v:2211.13436, 2022.
12

---

[36] Markus Leitner, Ivana Ljubić, Michele Monaci, Markus Sinnl, and Kübra Tammmmy. An exact method for binary fortification games. European Journal of Operational Research, 307(3): 1036-1039, 2023.
[37] Risheng Liu, Jiaxin Gao, Jin Zhang, Deyu Meng, and Zhouchen Lin. Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond. IEEE Trunsuctions on Puttern Analysis and Machine Intelligence, 44(12):0045-10067, 2021.
[38] Michele Lombardi, Michela Milano, and Andrea Bartolini. Empirical decision model learning. Artificial Intelligence, 244:343-23 36733,67222220 2017.
[39] Leonardo Lozano and J Cole Smith. A nalue-function--ased exact approach for the bilevel mixed-integer programming problem. Operations Research, 65(3):768-786 2017.
[40] Donato Maragno, Holly Wiberg, Dimitris Bertsimas, $ ilker Birbil, Dick den Hertog, and Adejuyigbe O Fajemisin. Mixed-integer optimization with constraint learning. Operations Research, 2023.
[41] Tom V Mathew and KV Krishna Rao. Introduction to transportation engineering, traffic assignment. Lecture notes, 2006.
[42] Ioana Molan and Martin Schmidt. Using neural networks to solve linear bilevel problems with unknown lower level. Optimization Letters, pages 1-21, 2023.
[43] Alec Morton, Ashwin Arulselvan, and Ranjeeta Thomas. Allocation rules for global donors. Journal of health economics, 58:67-75, 2018.
[44] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alchéé Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019. http://papers. hatpaapers..eurip..... www.ueeuuucccccee wctpaaper/915---yrrrrr an-imperative-style--e teriigg-prrooomnnc-eee----ee
pdf.
[45] Remigijus Paulavičius and Claire S Adjiman. New bounding schemes and algorithmic options for the saunhhannd-snddiing algorithm. Journal of Global Optimization, 77(2):197-225, 2020.
[46] Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning in Python, Journal of Machine Learning Research, 12:2825-288 28300, 2011.
[47] David Rey. Computational benchmarking of exact methods for the bilevel discrete network design problem. Transportation Research Procedia, 47:11-18, 2020.
[48] David Rey. Optimization and game- game-theoretical methods for transportation systems. PhD thesis, Toulouse 3 Paul Sabatier, 2023.
[49] Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning, pages 4558-4566. PMLR, 2018
[50] Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. Solving optimistic bilevel programs by iteratively approximating lower level optimal value function. In 2016 IEEE Congress on Evolutionary Computation (CEC), pages 1877-1884. IEEE, 2016.
[51] Ankur Sinha, Zhichao Lu, Kalyanmoy Deb, and Pekka Malo. Bilevel optimization based on iterative approximation of multiple mappings, 2017.
[52] Ankur Sinha, Samish Bedi, and Kalyanmoy Deb. Bilevel optimization based on kriging approximations of lower level optimal value function. In 2018 IEEE congress on evolutionary computation (CEC), pages 1-8. IEEE, 2018
13

---

[53] Sahar Tahernejad, Ted K Ralphs, and Scott T DeNegge. A mixed integer bilevel linear optimization problems and its implementation. Mathematical Programming Computation, 12:529-568, 2020.
algorithm for
[54] Yen Tang, Jean-Philippe P Richard, and J Cole Smith. A class of algorithms for mixed-integer bilevel min max optimization. Journal of Global Optimization, 66:225 2222,,26,2222 2016.
min-max
[55] Mark Turner Antonia Chmiela, Thorsten Koch, and Michael Winkler. Pyscipopt-ml: Embedding trained machine learning models into mixed mixed-integer programs. arXiv preprint arXiv:2312.08007, 2023.
[56] Alan Washburn and Kevin Wood. Two-person zero-sum games for network interdiction. Operations research, 43(2):243-251, 1995.
[57] Noah Weninger and Ricardo Fukasawa. fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints. In International Conference Integer Programming and Combinatorial Optimization, pages 438 452. Springer, 2023.
[58] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
[59] Bo Zhou, Ruiwei Jiang, and Siqian Shen. Learning to solve bilevel programs with binary tender. In The Twelfth International Conference Learning Representations, 2024.
[60] Marco Zugno, Juan Miguel Morales, Pierre Pinson, and Henrik Madsen. A bilevel model for electricity retailers' participation in a demand response market environment. Energy Economics, 36:182-199 2013.
14

---

A Impact Statement
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 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 in the management of energy systems.
B NEUR2BILO Pseudocode
Here, we outline pseudocode for NEUR2BILO. Algorithm [ presents the pseudocode for data collection and training. 2 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 collect labels for both the upper- and lower-level approximations. Additionally, single trained model may be (and is in our experiments) evaluated across multiple test instances.
Algorithm NEUR2BILO Data Collection and Training
Data Collection
D < 0
for 1 to number of instances to sample do
P <- sampled instance. Note that p is defined by F(-), f(), and X. For most
BiLO problems, these functions are defined by the constraint and objective coefficients
for
to number of decisions per-instance do
X <- sampled upper-level decision
f- arg maxyey yx) g(x,y) 2 0}
Add (P.x, F(x, yxx D
end for end for return D
Training
if approximating upper-level then Train regressor (NN") with features (P, and label (F(.) from dataset 'D else if approximating lower-level then
Train regressor (NN') with features (P, x) and label (f(+)) from dataset D
end if
return N or NN
Algorithm 2 NEUR2BILO Optimization
Input: Evaluation instance P', trained model NN /NN". Note that the trained model (NN" /NN")
is used on multiple evaluation instances. if approximating upper-level then x" <- ueper-level solution from the upper-level approximation (Equation (5))
else if approximating lower-level then
x f- upper-level solution from the lower-level approximation (Equation (7))
end if
return x*
15

---

C Example Comparing the Upper- and Lower-level Approximations
Example C.I. Consider the problem
min y/ zE (0,01)
s.t. y arg max {y 2x S
vc(0,1)
Solution makes the follower's problem infeasible. For solution 0, the optimal follower
solution 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( = 2 and NN(1) = O, then the upper-level approximation problem (5) will return which is infeasible whereas the lower-level approximation correctly returns 0.
D Proofs for Approximation Guarantees
This section includes the full analysis of the derived approximation guarantee in Section 3.3 for the lower-level approximation with NN' (x; ().
Recall that we look at 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 E X, E Y), we assume that Assumption Ti) holds and that the neural network approximates the optimal value of the follower's problem to an absolute error of a > 0, i.e.,
NN (x: Q) +xx)
for all X.
We furthermore define the parameter A the maximum difference of functions values f(x, y) f(x, y') 2 over all x E y, E y such that no ý e y exists which has function value y( f( f(x,y'). Note that A can be strictly larger than zero if the follower decisions are integer.
For fixed x E X. (x) denotes optimal solution of 77.. Furthermore, for any given y ) we denote by s" (x, y) an optimal slack-value Problem 7 the upper- and lower-level variables are fixed to x and y, respectively.
Observation D.1. For any x E X and y E y we have
s' s'xx,y) max Nx: y))
Lemma D.2. Assume the leader and the follower have the same objective function and X Then, for any given x E X' the following conditions hold for the optimal follower solution Vis(x) of Problem 7
NN' (x: Q) > 4(x), then f(x, 4(x). i.e. (NN is feasible for the original bilevel problem.
IfNN < 4(x), then (x; - 1 (Nx S ((x).
Proof. Case 1: Let x E X' for which it holds NN' [x; +) > ((x) and assume the opposite of the statement is true, i.e., for the optimal reaction yÑN (x) (7 holds that oxx) > y (x)). VăN
Since À > and due to Constraint (7d) the optimal slack value for solution x in Problem 7 is
s" y) NN' O) f(x,y) Assume y (x) is the optimal follower reaction in 2 for x, then
holds that:
(x)) As As (x)(
=((x,Ni(()) + X (NN' (x; 9) [(x,
>((x)(((x)) + (NN' (x; 9) fxx, vix())) + - (A-1))((xxxxxm())))) - f(x,y(xx))
=s(x)x"(x)) + + (NN' -x((xx
=f(x,y" + x
16

---

where the first inequality follows since À > and f(x,y" = 4(x) > yix(x)) and the yx),""(x)), The latter result shows that the solution (x, y" (x)) has a strietly better objective value in the surrogate problem
latter equality follows from NN' (x; )) 2 xxx)
77 than (x, (x)(
which contradicts the optimality of (x, (r))
Case 2: Let x E X' be a leader's decision for which NN' @) < +(x) and assume the opposite of the statement, i.e., for the optimal reaction (xx(x) in ( it holds that NN (x; 1 > f(x: ViNN()) Hence the optimal slack value in
7 is
s* (x, ViN (x)) NN' (x: (x; 0) - f(x, YNN (x))
(10)
First, assume there exists another feasible solution f(x) for Problem with
f(x, (&x())) < {()) (x)
then solution (x, (())) has a strictly better objective value than (x. yNN (x)) in 7 since increasing
the value of by 5 decreases the value of the slack variable by 5 which results in a better objective value since À > 1, which contradicts the optimality of (x, (x)).
Second, assume there exists no other feasible solution (x) for Problem 7 with
f(x, vix(x)) < fxx (())) < NN (x;
Then there must exists feasible solution (xx) with (()) NN' (x: +) and f(x, (x)) A,
(11)
by definition of A. In this case, have
f(x, As (x,,
((x) As (x, Fx( = y(x + As (x, (x, (x)) - F(x))
yix, A fxx) 2 --
where the first equality follows since s" (x. f(x)) = 0, the first inequality follows from (0)) and the last inequality follows from (II). In summary, the latter results show that there exists a solution (x)) for which has strictly better objective value than (x) which is contradiction.
Note that the incquality f(x, (xN())) s 2(x) follows directly from the definiton of (xx).
The latter lemma states, that if the neural network is overestimating the follower value for solution X X, then the surrogate problem 7 still selects an optimal follower response. However, the neural network underestimates the value, it may happen that the surrogate problem chooses follower response for which the objective value either is larger than the true value or differs by at most A Note that the latter term can be controlled by increasing the penalty X.
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 feasible solution xx"y") for Problem [ with objective value
2
1xx,,"
< opt + 3a
X
where opt is the optimal value of ① and the penalty term in
7a
Proof. Let (x v&) be an optimal solution of the surrogate problem 77. By Lemma D.2 and by definition { it follows that
(xxxn) 2 f(XiiN vTN) NN' (xNNi +) A
(12)
((xxx) - A.
Following the three steps presented in Section 3.1
NEUR2BILO returns feasible solution (x*,y*)
for Problem where x* -XšN and f(x", , (x*). Hence the following holds:
f(x" = ((x*) < f(xx V + +a 1 1
(13)
17

---

Assume (x*) is an optimal bilevel solution of Problem and YNN the optimal follower response in the surrogate problem (7). Then we have
f(x", + s" (x", vis)) I f(x** Yik) + s y
since (N yuN) is an optimal solution of with objective value given by 7a From the latter inequality we obtain
f(x" vAN)
_ f(x" UNK) + s "x""","""""""""""""""""" s" (x'. yiN)
f 1xx""y"" + (x"" ,yšN)
$ f f(x", ,"*) + NN' ; - f(xx', ,
S "(x"","'" yy") + x(x*") + ($(x**) x A
1 -
opt + 2a
where the second inequality follows from s* (x", VKN) 2 and y** being an optimal follower
solution for x** The third inequality follows from Observation D.I and the fourth inequality follows
from (8) and from [12 applied to x**
Together with 13 this completes the proof.
E
Problem Formulations
E.1
Knapsack interdiction
The bilevel knapsack problem with interdiction constraints as described in Tang et al. [54] is given by
min
Pey
xe <E(0,1)".
s.t.
24 S k.
Σ pitk
y E arg max
(0,11
Σ anah S b,
s.t.
1=1
J/( + x4 < 1, E [m]]
where x are the leader's variables and are that of the follower. The leader decides to interdict (a maximum of k) items of the knapsack solved the follower's problem with n the number of items, pa the profits, a the weight of item i, respectively, and the budget of the knapsack is denoted by b.
E.2 Critical node problem
The critical node problem described in Carvalho al. ||| as follows
n
P x1)(1 vi) + nr, ex, (1 v:) + 6(1 - -x.)1i)
max xE (0,1)
Σ d,z; - D. i=1
s.t.
p - 77(1 -1-1)) w/) + (1 24)z4 + (1 --)zz8)))
y E arg max y' ('E(0,1
Σ asy < A,
s.t.
18

---

where x and y are the leader's s and follower's variables, respectively. Here, 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, and a, are the costs for the Jy and Yt. respectively. D and are the budgets for the defender and attacker, respectively. 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, pf. and the follower pays an opportunity cost - for not attacking an undefended node. Second is a successful attack, wherein the leader receives a reduced profit of ōy and the follower receives the full profit p. Third is mitigated attack, wherein the leader receives profit of npt for degradation in operations, while the follower receives profit of (1 - n)p for mitigated attack. Fourth is a mitigation without an attack, wherein the leader receives a profit ep, for degradation in operations, while the follower receives profit of 0 for mitigated attack.
this
E,3
Donor-recipient problem
The donor-recipient problem as described in Ghatkar al. 27 and introduced in Morton et al. 43 is formulated as
max X x -020
WiYii
s.t.
Σ 1=1
c S Bd:
(y, vo)
arg max
ualk + v0y/
y'((0.))..pE((0.1
Σ (c. c,at)y/ + co2l Br.
s.t.
where the leader's decisions x represent those of the donor and the follower's decisions (y, you the ones of the recipient. The profit of project is given as for the leader and is for the follower, the cost as cs and the budget of the leader, resp. follower, as Ba and B,. Next the projects, the recipient can allocate its budget to external projects, for which the profit is given as Un and the cost co.
E,4 Discrete network design problem
We use the standard formulation from Section 1 following the computational benchmarking study of Rey 47 and the code provided by the author
F Comparison to the Learning-Basee Approach of Zhou et al. [59]
This section compares our approach recent learning-basse based approach from Zhou et al. [59 based on code provided by the author | We specifically compare the huput-supermodular neural network (ISNN), i.., the 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' and NN can be trained once and evaluated across multiple instances, so the data collection and training time 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, amount of time. Table 3 the MRE and time for each method for the knapsack instances from Tang al. [54]. Generally, we can see a significant improvement over ISNN in both computing time and MRE.
iteration requires the least
http:://gttabbb.ccwwaarrrrrr111p
19

---

ISNN
NN
NN
G-VFA
B&C
Time
Time
MRE
Time
MRE
MRE
5
10.50
254.35
1.48
0.59
1.48
0.34
1.82
0.14
0.00
9.55
18
9
46.50
227.49
1.51
0.59
1.51
0.43
3.97
0.22
0.00
5.81
302.10
217.62
64.22
0.39
20
5
8.56
262.01
0.41
0.62
0.41
0.45
2.19
0.25
0.00
23.18
20
10
54.07
236.74 74
0.99
0.66
0.99
0.58
0.99
0.36
0.00
10.27
15
447.29
229.41
3.57
0.32
3.57
0.19
23.39
0.02
0.00
0.94
22
6
17.32
266.55
0.71
0.19
0.71
0.18
0.42
0.18
0.00
42.30
11
66.24
247.97
1.01
1.08
0.00
16.26
22
17
485,75
241.61
14,43
0.24
14,43
0.15
14.43
0.13
0.00
0.68
25
7
14.75
280.71
0.44
2.66
0.44
2.42
0.44
0.64
0.00
137.96
264.09
1.42
2.75
1.42
3.85
48,43
25
19
424,92
262.04
2.49
0.48
2.49
0.38
2.49
0.13
0.00
1.77
7
19.17
297.44 44
0.39
0.67
0.39
0.74
0.26
0.62
0.00
309.18
14
73.61
286.02
0.75
2.10
0.75
1.45
1.37
1.29
0.00
120.74
28
21
423.15
279.51
1.14
0.45
1.14
0.49
3.16
0.31
0.00
4.92
21.01
305.67
0.43
792.44
30
15
68.19
295
0.49
3.64
0.49
3.06
0.75
1.35
0.00
187.23
23
416.03
290.94
2.29
1.08
2.29
0.73
4.48
0.25
0.00
5.65
Average [54]
164.49
263.67
1.86
1,06
1,86
7.21
0.47
0,00
95.43
Table 3: Comparison to ISNN from Zhou et al. [59] on the knapsack interdiction problem. 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- (F-)FA) and the exact algorithm (B&C).
G Objective & Incumbent Results
This section reports the more detailed information related to the objective values for each problem. Objective results for each problem are given in T In addition, for KIP and CNP, as the solver from Fischetti et al. 23 provides easily accessible incumbent solutions, include two additional metrics.
The first metric "Solver Time Ratio" measures the time 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 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 done solving.
WN"
G
BAC
NN
NNN
100
NEV
G3
18
14540
1:5:0
148.0
143.43
1.51
1.51
3.7
0.50
0.43
0.33
1.11
12.3 (12)
11.52 (10)
17-40(10)
-10
-11)
-12)
20
39670
79030
347.00
181.53
D41
0/11
2.3
062
0.45
0.25
33 10
58 (1))
65.66 (1))
(109
-00
-15
175
23400
33.40
41.30
31.40
23.33
14
182 1321
4.3 (00)
54.2/111
18320
163.81
153.3)
161.99
1.55
0353
225.5 100)
5499 (00)
12006-10
-131
23.31
1442
14.0
3443
111
436.0
438.00
436.30
137.50
55 130
51.34000
110.38 (10)
2589121
22,0/22
25.912)
19246
191-91
191.53
133
108
575
1.33
18.11
11100)
25 1513
171
155
18
319.5
313-01
317.91
116.39
0.56
11.9
0.3
106
0.14
1442
309 15
131
535 110
29.05:0
18 11
48.5
46.10
20.31
15.33
114
116
3.3
106
0.8
1.11
1259 1301
11 (10)
-001
-00
19
20130
25120
201.00
338.9
040
1629
035
100
53
105
135
18725 25
39 3434100
24420 (1)
96.11 19
26.1/0
13.99
100
35
116111
3.66 09
2.15.47
060
040
8.8
516
1037
842
419
3500 10
10
90
48
34 1636.105 (180)
31:0 (006
37.01
100
15
245.8
385m
34582
15445
846
088
455
31.34
1030
1508 50
135 15:
118 (7)
177 (10))
144 85 2140
19 (100
Table 4: KIP objective and incumbent results. Each row averaged over 10 instances, except for n = 100, which is average over 100 instances. NN' and NN specify the lower- and upper-level approximations respectively. All times in seconds.
20

---

[V]
Obaecsie Ne0*
Moxs Relatiee Elmor (55)
Selver Tire Raaes
Sclver Actatte Eireral Tize
BAC
Y000
RAV
NN
23447
238.3
1:31
1,00
1,88
1.29
3,000:001
126 (288)
191 (282)))
2906/
592 72
506.23 23
572.51
1,00
1.77
0.78
1.59
1.89
3 50
735 94 (375)
5434 (2112
2:22 (248)
2:57 (124)
101
3:385
2.29547
2313.30
312
1.29
1,89
1,39
3,003 301
648 37 13315
244
2. (278)
303
6.71 91
4.802 43
6.55007
391
0,33
2.80
1.59
1.89
3 50
4165 (166)
107 01.38.33 -47
1.45 (245)
2468 (243)
11,343.00
11,43922
11,206.43
2.47
1.59
106.9
90.48:15)
1.51
(255)
Table 5: CNP objective and incumbent results. Each row averaged over 300 instances. All times in seconds.
Instence
Objectice NN.
Reistive Ernur (16
Times
N00
BAC+
NN
NN
BBCC
NNs
NNV
B&CC+
34.356.00
59,524,00
47.206.00
42.28
0.80
1.44
3,000
33.713.00
54,764.00
39.526.00
3,409.05
36.717.00
66,367.00
46,792,00
45.17
0.00
3,600.07
54,908.00
14,086.00
1.68
59627.00
43,35500
35,710.00
54,414.00
39,539.00
34.37
0.00
3,600.00
61
45,238.00
37.50
0.00
26.80
3.600.16
610,888.00
43.194.00
0
28.59
3,600.10
Averaged
35,997.
58,473.30
43,213.50
90.
0.80
26.00
0.11
2.30
3,60% 87
Table DRP objective results. Each row corresponds to single instance from dataset 15, i.e., the most challenging instances from Ghatkar et al. [27]. All times in seconds.
Oijictio C3RT
Bakako Rive (S) MKKETS
Traes GIT
NN4"
GRC!
MKKT
1I
MIKTT1D 1D
XW
NV
caV
CITT"
MICTT-1
NN
NN
GITT
K.8522
0.
5350292
5.52228
$391.21
3.40.7
3A4541
5,81135
075
122
3.12
3.14
6.47
1.12
109)
1.35
0.81
3.66
0077
0.35
5,478 02
5,372.90 98
5,212
$221900
3,35 14
5,62322
5.199.7
685
1/6
1.8
14]
5.12
088
570
0.8
5.00
0.25
1.2
401
0.21
1080119
0,885.0
<.661:6
4.3550
4.61.00
1161.22
4851.8
333
3.44
4.6
Table 7: DNDP objective results. Each averaged across 10 instances. All times in seconds.
H Distributional Results for Relative Error
I Ablation
L1 Lower-level value function constraints
In this section, we present an ablation study comparing alternative types of value funetion approxima- tion (VFA) for the lower-level approximation on the KIP. Namely, we compare the approach used the the main paper, NN', which utilizes a slack variable to ensure feasibility. addition, we include N which does not use slack at all, and NNd, which uses the largest error in the validation set to scale the prediction down. Table & reports objectives, relative errors, and solving times of each method. In general, the solution quality of NN slightly exceeds that of NNd. while NN does significantly worse. The latter results is unsurprising given that any underestimation will cause a loss of fcasibility for potentially high quality upper-level decisions. NN' is additionally generally the fastest to optimize as well.
1.2 The effect of A
In this section, we present results with X = 0.1 for DNDP. Table presents relative error and solving times for this setting. Notably, this choice of tends to provide higher quality solutions than À = as reported in the main paper in Table Tuning this hyperparameter further can thus improve the already strong numerical results reported for DNDP, and possibly other problems.
I.3 Greedy features for Knapsack
This section explores the impact of the use of greedy features on the KIP problem. We specifically compare model trained purely on the coefficients to a model trained on the coefficients with additional features derived from KIP-specific greedy heuristics. From Table TO there a clear advantage with the greedy features in terms of solution quality at the cost of increased solving time.
21

---

21
Objective
Mean Relative Eree (86)
Times NN.
NNN
NN
NN'
NN
NN
NN
NNV
NN"
15
30X.30
505 405.40
318.40
0.00
0.03
5.28
0.59
0183
1.06
18
145.60
145.60
152.90
0.00
0.00
5.70
0.59
1.21
0.51
18
14
31,00
$7.50
40.00
0.00
16.91
46.23
0.22
0.30
0.35
20
390,30
390.30
413.90
0.00
0.62
1.38
165.40
165.40
0,.00
1.76
32,50
3.33
14.29
0.33
0.96
22
0.50
1,23
25
446.50
2.66
23
I3 194.90
195,
206.55
0.00
0.26
2.75
4.83
23
19
43.30
43.30
64.40
1,69
1.69
92.49
0.48
0.74
1.34
25
518.30
518.30
$32.20
0.00
0.00
2.30
0.67
0.83
2:37
25
14
224.90
224.90
234.70
11.00
0.00
4.60
2.30
2.69
3.72
28
21
46.70
49 90
60.70
0.00
7.48
37.45
0.45
0.83
167
30
$36.30
537. 10
537.70
0.00
0.15
0.25
1.54
1,36
3.07
50
15
231.20
231,20
232.88
0.16
0.16
0.52
3.64
4.18
5.00
30
23
49,00
50.20
$1.50
0.00
2.79
4.48
1
1.50
1.76
100
2,164.71
1,164.13
2.168.5 52
0.04
0.23
10,02
12.38
19.31
0303
Table 8: KIP results comparing NN NN4, and NN Each row is average over 10 instances, except for n 100, which an average over 100 instances. All times seconds.
of edges
Indget
NN
NN
GBT
GBT
MKKT
MRE
MRE
Time
MRF-5
MRE-30
3.26
10
0.5
0.39
2.90
1.22
0.01
1.33
3.54
2.74
0.07
6.47
2.17
0.00
10
0.75
0.48
2.23
1.32
0.00
0.47
2.19
0.91
0.06
5,80
0.02
0.06
20
0.25
3,62
5.02
2.46
0.02
1.36
5.02
1.23
0.23
7.59
4.96
0.67
20
1.56
0.63
5.02
2,06
0.43
4.75
2.27
8.00
Average
1.44
3.52
1,50
0.01
1.00
3.96
1.60
0.13
6.61
1.76
Table 9: DNDP results for À 0.1. Each is averaged across instances. NN' and GBT are the learning-based formulations with slack for the lower-level approximation. N and GBT" are the learning-based formulations for the upper-level approximation.
Objostiv
Mean Retative Eie (%)
Tince
grunly
grenlyy
goady
grosdy
XNI guxly
groodl
145.60
150.50
4.28
18
14
31
11.00
0.80
$3.04
0.22
0.65
30
5
390 30
326 80
0,80
331
9.52
0.86
20
J0
165.40
172.00
0.55
4.06
0.56
0,85
20
15
33.40
36.50
0
7.31
0.32
0.86
6
30000
087
1.67
25
13
19490
107
0.50
3.58
3.75
0,07
25
19
43.30
49.10
0.80
13.55
0.58
0.87
28
7
S1R.30
537.70
0.15
3,63
0.57
0,87
28
14
23AV0
0.21
0.61
2.10
0.88
46.70
15
1.20
23
48.0
$1.30
4.7
0.08
100
25
2,16471
2,473.05
0.60
14.22
10.00
0.54
100
50
965.37
1J862 92
0.84
10.35
$1.68
0.52
100
75
245.01
313
44
0.80
27.62
24.50
0.53
Table 10: KIP results comparing NN' with and without greedy-based features N Each row averaged over 10 instances, except for 100, which is an average over 100 instances. All times in seconds.
22

---

14:
NN
NN
Ralative Error
10:
G-VFA
B&C
8-
6:
4.
2:
0
18
20
22
25
28
30
100
Items
Figure Box plot of relative errors for KIP with interdiction budget of n1/4.
25
NN
NN
20
Relative Error
G-VFA
B&C
10
5.
8 8
8
0:
8.8
18
20
22
25 Items
28
30
100
Figure Box plot of relative errors for KIP with interdiction budget of n12.
J Computing Setup
The experiments for the 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). 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 (3) was used the MILP solver and purobi-machinelamminn 1.4.0 was
used to embed the learning models into MILPs.
K
Machine Learning Details
K.1 Models, features, & byperparameters
For all problems, derive features that correspond to each upper-level decision variable, well as general instance features.
K.1.1 KIP, CNP, DRP
For KIP, CNP. DRP, we have decisions in both the upper- and lower-level of the problems. For the learning model, we utilize 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,). Each of these are passed through feed-forward network with shared parameters (V.,) to compute an m-dimension embedding. The embeddings are then summed and passed through another feed-forward network (V.) to compute the instance's 's k-dimensional embedding. This instance embedding is then concatenated with features related
upper- and lower-level that are dependent on the decision (l (xx))). The concatenated vector is passed through feed-forward network with shared parameters (V,) predict n scalar values (i.e., one for each decision). The final prediction equal to the dot product of the predictions with the objective function coefficients of the upper- or
23

---

175
NN'
NN
150
Ralative Error
G-VFA
125
B&C
100
75
28
100
Items
Figure 3: Box plot of relative errors for KIP with interdiction budget of k: 3n/4.
60
NN
50
Relative Error
B&C
40
30
20
00:00
900
10
25
50
100
300
500
Number of Nodes
Figure 4: Box plot of relative errors for CNP. B&C does not find any upper-level solutions for 2 of the 300 instances of size [V| 500, these are excluded from the plot.
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 Σx= 4224, where a is known coefficient and is decision variable or a function of a set of decision variables with index 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- deeeeddee and decision-independeer features are summarized in Table
One minor remark for KIP is that since it is interdiction problem, we multiply the concatenated vector, i.e., the input to vr, by (1 xF:) as mask given that the follower cannot select the same items the leader.
For all instances, we do not perform systematic hyperparameter tuning. The sub-networks a V.. V are feed-forward networks with one hidden layer of dimension 128. The decision-indepena feature embedding dimension (m) is 64, and the instance embedding dimension (k) is 32. We use batch size of 32, learning rate of 0.01, and Adam 31 optimizer.
K.1.2 DNDP
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.
K.2 Data collection & training times
For KIP, CNP, DRP, we sample 1,000 instances according to the procedures specified in Tang et al. (4)) Dragotto et al. [18), and Ghatkar et al. [27]. respectively. For each instance, sample 100

---

16
14
NN
Relative Error
GBT!
MKKT-
MKKT-30
2
0.25
0.5
0.75
Budget
Figure 5: Box plot of relative errors for DNDP with 10 edges. MKKT-(5510..0 corresponds
MKKT run with each respective time limit.
17.5
NN
NN
15.0
Relative Error
12.5
GeT
10.0
MKOKT-10
MIKKT-30
7.5
5.0
2.5
0.0
0.25
0.5 Budget
0.75
Figure 6: Box plot of relative errors for DNDP with 20 edges. MKKT-(5,10,30) corresponds to MKKT run with each respective time limit.
Problem
Type
Features
KIP
f,
p:/0: max,; pp Pse 04, k/n, 2i yi objdo /n
I((x:)
fú, Vis 1f
CNP
f;
18/a, maxi (p//d.)'
/d/d;
tp/ J. di Ois pl. P.. 7o 17, 5, A. D
1((x;)
Pú, Di. 7(1 Izi. (1 2z). (1 17)
DRP
f; l((x,)
w//cc max, [ max,
/v, Wi. Uss Cs. Ba, B,
f, Iz;
Table 11: Features for KIP, CNP, and DRP. Most features are derived directly from the objective and constraint coefficients, so refer Appendix E for the definitions. For KIP. additional features are computed using simple greedy heuristics. For the KIP DIF, we compute x dg obj which correspond to purely greedy strategy, i.e., the upper-level interdicts the & items with the largest profit to cost ratio (p./a,) and the lower-level decisions are the largest remaining highest profit to cost ratio items. For h(xx) in KIP, we also include lower-level decisions based on G-VFA (y.).
upper-level decisions, i.e., 100,000 samples in total. Additionally, for KIP, CNP, DRP, the lower-level problems solved with 30 CPUs in parallel. For training, train for 1,000 epochs. However, the validation mean absolute error does not improve in 200 iterations, we terminate early. Data collection and training times are reported in Table
For DNDP, we use the Sioux Falls transportation network provided by 47 along with the author's 60 test instances. All instances use the same base network with different sets of candidate links to
25

---

add and different budgets. There are 30 candidate links in total, and each test instance involves subset of 10 or 20 of these links. To construct a training set, we sample 1000 leader decisions by first uniformly sampling an integer between 1 and 20, then uniformly sampling that many candidate links out of the are rejected as they are likely to exceed realistic budgets.
30 options; samples with total cost exceeding 50% of the total cost of edges
Problem
Data Collection
Training Time
Upper
KIP (n
183
142.08
2576.43
KIP (n 20)
172.65
4714,88
KIP 22)
141 61
2346. 20
KIP 25]
170.30
40077 75
KIP ( 28)
142.
2684.80
KIP (n 30)
168.91 91
1835.27
164.16
3467 266
CNP CNP 10)
1,397 58
1839.60
4670
CNP (V 25)
1.522.32 32
2072.60
1841.31
CNP ( 50)
1,823.16 16
2103.50
2963 64
100)
19444188
CNP (V) 300)
3.662.5 89
3800.02
3598.04
CNP ( 500)
4,742.06
2263 86
6214.35
DRP
1939 24
1768.82
1784.15
1033.15
Table 12: Data collection and training times for all problems. Note that as KIP is an interdiction problem, the same trained model can be used for the upper- and lower-level approximation, so simply leave the upper-level as for this problem. All times in seconds.
K.3 Prediction error
For KIP, CNP, and DRP, we provide the Mean Absolute Error (MAE), as well as the Mean Absolute Label (MAL) as a reference access the prediction quality for the validation data Table [3] The table shows that models achieve MAE of at most ~ le-6 with MAL ranging from 0.006 to 200 for all KIP, CNP, and DRP instances. For DNDP, both neural network and gradient-boosted tree models achieve Mean Absolute Percentage Error (MAPE) ~ 5%.
Problem
Upper Level Approximation
Lower Approximation MAE
MAE
MAL
MAL
KIP (n 18)
5.05e-00
2.0992
KTP (n
5.98e-0
2.5369
KIP (n 22)
1.00e
2.6933
3.45e 10
KIP (u 28)
1.48e-90
3.7327
(a 30)
2.8
KIP 100)
1.21e
13.104
CNP [|V| = 10)
1.35e
5.4606
6.74g
1.5272
([V] 255)
1.09g 08
CNP [[V] 50))
1.23e
23.9687
4.77e
7.7536
CNP ([V] 100)
4.33k
46.5468
3.97e
14.7491
CNP ([V
1.836-08
135.8972
2.54e-07
44.577
CNP ([V) = 500)
8.54e
222.3805
9.51e
76.212
DRP
2.51e 07
0.0062
7.82e
0.0703
DNDP
0.0292
0.4297
0.02504
0.4990
Table 13: Prediction errors for all problems. Note that as KIP is an interdiction problem, the same trained model can be used for the upper- and lower-level approximation, we simply leave the lower-level as for this problem.
26

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The methodology and numerical results accurately validate the key methodolog- ical contributions and computational performance discussed in the abstract and introduction.
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 to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Key limitations of NEUR2BILO are briefly discussed in Section Any assumptions are explicitly stated throughout the paper and appendices.
Guidelines:
The answer NA means that the paper has 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 a 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 few datasets or with 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 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged 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 of assumptions and a complete (and correct) proof?
Answer: [Yes]
27

---

Full theorems, assumptions, and complete proof' are provided in the appendix. Important assumptions are mentioned in the main paper.
Justification:
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 or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if 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 supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Yes, the paper provides sufficient detail for the methodology and the learning models in the appendix. The code provided also include can be run to reproduce the results in the paper, the trained models and test instances are also included.
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 a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it 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 good way accomplish this, but reproducibility 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 appropriate to the research performed.
also be provided via detailed
While NeurIPS 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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (c.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 deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
28

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Yes, all of the code and data are available here ltttps://github.ccom
challllrresercchhNeuer 2BiL
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we 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 new 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 for more details.
/ //nips.col wwwppbbic/guidee..eeeeeceeeeeeee /pb.:i/cgguudeee/oeeebbbbiaiiss
The authors should provide instructions on 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. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
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: Yes, these details are included in detail in Appendix K
Guidelines:
The answer NA means that the paper does not include experiments.
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.
7. Experiment Statistical Significance
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 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, confi- dence 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.)
29

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation 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 enror 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 Question:
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?
Answer: [Yes]
Justification: All computing information is discussed in Appendix Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 as well as 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 or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research does not involve human subjects. Given the nature of the paper, there data-related concerns.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances 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 socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Yes, an impact statement is provided in the appendix. For the camera-ready version of the paper, will include this in the main paper, given the additional space provided.
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.
30

---

The conference expects that many papers will be foundational research and not tied to 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 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 (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
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)?
Answer: [NA]
Justification: The released models do not have high risk of misuse.
Guidelines:
The answer NA means that the paper poses no 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 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 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/modell.
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 of the asset used and, if possible, include 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 pataasts.ppapersvii paperswi thcode. com datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
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 not available online, the authors are encouraged to reach out to the asset's 's creators.
31

---

13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: All assets (dataset/ccode/modee) are available and anonymized.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent 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. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
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 much detail as possible should be included the main paper.
According to the NeurlPS 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: The paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may 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.
32


Reviews:
[{"review_id": "Sgv0DKYM3M", "reviewer": "Reviewer_Rwxw", "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.", "questions": "1. Can the proposed algorithm be extended to continuous network design problems? If not, please explain the reasons. \n\n2. Can the proposed algorithm be applied to neural architecture search? If not, please explain the reasons.", "limitations": "Please find my comments about the limitations in other parts of the review.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper studied an important problem, and its overall structure is easy to follow. In recent years, research in bilevel optimization has become increasingly popular.  However, most algorithms are dedicated to bilevel programs with continuous decision variables, like the continuous network design problem in transportation and the hyperparameter optimization problem in machine learning. Yet, bilevel optimization problems with discrete decision variables are equally important and have also found applications in various domains. Hence, the relevance and applicability of tackling such problems are well-justified.", "weaknesses": "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.\n\nFirst, 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. \n\n[1] https://github.com/bstabler/TransportationNetworks\n\nSecond, 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. \n\n[2] Liu, H., Simonyan, K., & Yang, Y. (2018, September). DARTS: Differentiable Architecture Search. In International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.  Below, we respond to each of the weaknesses and questions.  \n\n**Weaknesses**:\n- Next to the performance guarantees we provide in the paper, we believe that we have conducted a thorough numerical validation. In total, we test on 2250 instances with ranging instance sizes on a wide variety of benchmark problems (continuous/integer upper/lower-level problems and non-linearity in both levels). For almost every set of larger instances (i.e., more difficult instances), we achieve better solutions on average over exact/heuristic methods, within multiple orders of magnitude less time.  \n- For DNDP, our primary motivation for comparing the Sioux Falls instances is their use, as a publicly available benchmark set, in other bilevel DNDP papers (see [1] and corresponding GitHub repo).  While there may be larger networks at the suggested GitHub repository,  these do not have the bilevel instance parameters required. Namely, the travel speeds and capacities of candidate road segments that are to be considered for addition to the network. The author of [1] did this generation exercise using their domain knowledge for the Sioux Falls network, making it suitable for benchmarking.\n- Regarding neural architecture search (NAS), Neur2BiLO can easily be adapted to this problem (see response to the below question for details).  While this is certainly an important bilevel optimization problem within the machine learning community, this could also be argued for any bilevel optimization problem, such as the over 70 applications listed in [2].  Given our extensive numerical study already evaluates Neur2BiLO on four integer bilevel optimization problems of interest to the bilevel optimization community more broadly, we believe this alone to be a notable contribution and sufficient evaluation.  In addition, we note that the generality and evaluation on four benchmarks with such variable structure is already more than the vast majority of bilevel algorithms evaluate on.  Furthermore, most bilevel algorithms are not even as general as Neur2BiLO given they are not suitable for non-linear problems.  \n\n**Questions**: \n\n- Neur2BiLO can be applied to purely continuous bilevel problems. However, these are generally well-solved by formulating the problem as a single-level problem using KKT-conditions or duality theory where applicable, or using first-order gradient methods as in the highly effective approach of BOME [3]. Generally, we focus on more challenging integer bilevel problems, wherein existing methods are intractable or have prohibitively long runtime.  \n- Yes, given a bilevel formulation of NAS, it can be applied to this problem.  In this context, one can learn to approximate the value function of any training metric that needs to be optimized.  Data collection can be done via sampling over architectures and training those specific architectures.  As you mentioned, Neur2BiLO may be useful given the discrete nature of NAS.  We would like to thank the reviewer for pointing this out as we believe studying Neur2BiLO and extensions for NAS would certainly be an interesting, and potentially high-impact, direction for future work and contribution.  We believe a contribution such as this would likely warrant an independent paper given the large body of existing methods, and literature, much of which can be leveraged within the Neur2BiLO framework.  \n\n**References**\n- [1] Rey, D. (2020). Computational benchmarking of exact methods for the bilevel discrete network design problem. Transportation Research Procedia, 47, 11-18.\n- [2] Dempe, S. (2020). Bilevel optimization: theory, algorithms, applications and a bibliography. Bilevel optimization: advances and next challenges, 581-672.\n- [3] Liu, B., Ye, M., Wright, S., Stone, P., & Liu, Q. (2022). Bome! bilevel optimization made easy: A simple first-order approach. Advances in neural information processing systems, 35, 17248-17262.", "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": "hX8sHIairV", "reviewer": "Reviewer_qVCc", "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.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "I found the work conducted to be substantial, supported by several proofs of components. \n\nAdditionally, the experiments evaluate performance across four scenarios: KIP, CNP, DRP, and DNDP, which adds further substance to the study.", "weaknesses": "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.\n\n2. 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.\n\n3. 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.\n\n4. The major body of the paper is not self-contained, requiring frequent switching between the main text and the appendix to obtain necessary information.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.  Below, we provide responses to each of the weaknesses.  \n1. For the first weakness, we will discuss two separate points.  \n   - We acknowledge that this paper focuses on relatively specialized bilevel optimization problems/literature.  We will add some basic references of the area in the introduction of the paper.  However, it is a technical conference and bilevel optimization is indeed a technical topic, so the paper certainly does require some background in the area.  Given the area of submission is Optimization (convex and non-convex, discrete, stochastic, robust) and all other reviewers commented that the clarity of the paper is high, we believe the presentation to be appropriate. However, if you have specific suggestions to improve the readability, please let us know and we can attempt to include them in the final revision.  \n   - In terms of the non-linear and mixed-integer bilevel problems, our approach handles all of them similarly as the upper- and lower-level approximations proposed rely only on computing optimal objective values to the decomposed single-level problems for data collection, which can reliably be done with any mixed-integer solver.  The trained models are then utilized directly as discussed in Section 3.1.  For this reason, we view this as a strength of the paper, as standard algorithms for bilevel optimization typically require much stronger assumptions or are limited to specific classes of problems, whereas Neur2BiLO can be deployed quite generally.  \n2. $\\text{NN}^u$ and $\\text{NN}^l$ are separate approaches, based on the same principle of transforming the bilevel problem into a single-level problem. One does so by learning to approximate the upper-level objective and the other does so by learning to approximate the lower-level objective. Each of the two approaches stand on their own; they cannot be combined.\n3. The major contribution of this paper is on the development of an efficient general learning-based algorithm for bilevel optimization, through the upper- and lower-level learning based approximations presented. In the final version of the paper, we will make the contributions more explicit.  However, we provide a brief list of major contributions below.  \n   - Generality: We propose a learning-based approach for bilevel problems particularly in the presence of integer variables or non-linear constraints/objectives. These are extremely challenging problems for classical optimization methods which require specialization to problem structure or significant computational effort.  \n   - Efficiency & Efficacy: Neur2BiLO computes high-quality solutions on a variety of bilevel optimization problems, often within orders of magnitude less time than traditional methods for bilevel optimization.  For larger, and more challenging problems, Neur2BiLO computes best-known solutions, in some cases by large margins, such as the 26% improvement over the state-of-the-art solutions for the donor-recipient problem.  \n   - Theoretical Guarantees: We provide theoretical guarantees for solution quality in terms of an additive absolute optimality gap which mainly depends on the prediction accuracy of the regression model.  \n4. Given the pagelimit, we aimed to present the central aspects of our approach in the main body of the paper.  We will aim to improve the readability and inclusion of material within the final version of the paper.  If you have any suggestions on what material you believe would be most beneficial to move from the main paper to the appendix, we would be happy to take that more strongly into consideration.", "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": "xDC7car7CN", "reviewer": "Reviewer_saS9", "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.", "questions": "I don't have any questions.", "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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents two novel ML-based approaches to reduce the challenging problem of BiLO. The approaches are not complicated but new and interesting. Empirical results show that both methods are promising - they can find similar quality or better quality solutions than the baselines but with shorter runtime.\n\nThe paper is also easy to read.", "weaknesses": "Note that I have reviewed this paper in the past and I am frankly surprised that it was rejected.\nThe authors have addressed most of my concerns last time.\n\nThese are not major weaknesses but still should be pointed out: \nThe 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.\nFurthermore, the theoretical approximation guarantees are not that surprising given that the prediction error is assumed to be bounded.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.  \n\nWe do acknowledge that the effectiveness certainly does depend on how well the value functions can be approximated.  Through our experiments, we do indeed demonstrate that this is relatively easy for the problems studied and note that these are already challenging problems within bilevel optimization.  While it may be possible that optimization problems with a more complex structure may be harder to approximate, we note that these would pose similar challenges for any method for bilevel optimization.  Specifically, most methods require frequent evaluation of the upper- and/or lower-level problems, the addition of cutting planes, and branch-and-bound.  All of which will likely suffer from similar issues with increasing problem complexity.  Furthermore, more challenging problems are even less likely to have well-defined problem-specific heuristics/algorithms.", "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": "PZuFCONSVy", "reviewer": "Reviewer_otky", "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.\n\nThe 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.\n\nNeur2BiLO is thoroughly evaluated on several challenging benchmark problems to highlight the generality and effectiveness compared to exact baselines and other learning-based methods.", "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.\n\n- 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 have been discussed.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "This is a very strong submission overall and was enjoyable to review. In particular, the writing is of extremely high quality given the technical nature of the paper. The methodology is clearly written, but importantly, the discussion of related works, experimental setup, limitations and analysis of results are presented very cleanly.\n\nNeur2BiLO is comprehensively evaluated against exact methods and other learning based methods, both experimentally and in the discussion. The approach is relatively straightforward but seems to integrate machine learning into existing algorithms and results for bilevel optimization a very elegant and principled way. In particular, the practicality of training the method and the effectiveness in practice as shown in the experiments is very appealing.", "weaknesses": "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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review.  Below, we provide responses to each of the weaknesses and questions.  \n\n**Weaknesses**:\n- Indeed, none of the problems we study in our experiments contain coupling constraints. We have not found bilevel optimization benchmarks with coupling constraints in the literature. For example, the bilevel mixed-integer linear solver of Fischetti et al. [1] is evaluated on many problems, none of which have coupling as far as we could tell. We will discuss this in the limitations of the paper. Please also note that in the presence of coupling constraints the upper-level approximation algorithm we developed is not applicable since the coupling constraints cannot be modeled.  However, the lower-level approximation can certainly be used.  \n- Regarding the smoothness of the optimal value function (OVF): unfortunately even in the simplest possible case, namely when the follower problem is a linear optimization problem with continuous decision variables $y$, the OVF can be non-smooth. Indeed, the OVF of a linear problem is piecewise linear and convex in the right-hand-side parameters of the constraints and piecewise linear and concave in the objective parameters; see [2]. Hence, if the leader variable $x$ appears either on the right-hand-side of the constraints or in the objective function the optimal value function can be piecewise linear and hence non-smooth. Even worse, if the leader variables appear in the constraint matrix of the follower the optimal value function can be discontinuous. Clearly, certain problem structures exist, where the optimal value function of the follower problem is smooth, but we do not see why this would be important for our method. Especially the approximation error in (8) you are mentioning is not affected by the smoothness of the function. Actually, the neural network with ReLU activations is a piecewise linear function itself and thus non-smooth. Hence, at least theoretically, it could achieve an approximation error of $\\alpha=0$ in (8). Could you clarify your point about why the smoothness of the OVF would be important for our work?\n\n**Questions**:\n- Yes, you are completely right. There is no guarantee that the solutions returned by our methods are optimal, but in Lines 161-173 we discuss under which assumptions our methods can guarantee a feasible solution. Note that the only case which can lead to an infeasible solution $x^\\star$ is if only Assumption 1(ii) is satisfied and if we use the upper-level approximation method. In all other cases the procedure guarantees feasibility. Note also that for the lower level approximation feasibility is always ensured. We will make sure to clarify this point in the paper. \n- Regarding smoothness, please see our answer above.\n\n**References**:\n- [1] Fischetti, M., Ljubić, I., Monaci, M., & Sinnl, M. (2017). A new general-purpose algorithm for mixed-integer bilevel linear programs. Operations Research, 65(6), 1615-1637.\n- [2] Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to linear optimization (Vol. 6, pp. 479-530). Belmont, MA: Athena Scientific.", "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:

Meta-review: 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.
Decision: Accept (poster)