Neur2BiLO: Neural Bilevel Optimization

Thank you for the review. Below, we provide responses to each of the weaknesses and questions.

Weaknesses:

• 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.
• 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?

Questions:

• 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.
• Regarding smoothness, please see our answer above.

References:

• [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.
• [2] Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to linear optimization (Vol. 6, pp. 479-530). Belmont, MA: Athena Scientific.

Thank you for the review.

We 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.

Thank you for the review. Below, we provide responses to each of the weaknesses.

1. For the first weakness, we will discuss two separate points.
   • 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.
   • 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.
2. $\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.
3. 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.
   • 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.
   • 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.
   • 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.
4. 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.

Thank you for the review. Below, we respond to each of the weaknesses and questions.

Weaknesses:

• 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.
• 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.
• 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.

Questions:

• 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.
• 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.

References

• [1] Rey, D. (2020). Computational benchmarking of exact methods for the bilevel discrete network design problem. Transportation Research Procedia, 47, 11-18.
• [2] Dempe, S. (2020). Bilevel optimization: theory, algorithms, applications and a bibliography. Bilevel optimization: advances and next challenges, 581-672.
• [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.