New Branch-and-Bound Rules for Linear Bilevel Programming

By Pierre Hansen, B. Jaumard, Gilles Savard. 1989

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Understanding and Robustifying Differentiable Architecture Search (2019, background): “verge to the minimizers of the bilevel problem (1) (see Franceschi et al. (2018)). However, solving the bi-level optimization problem with non-convex inner objectives is in general a NP-hard problem (Hansen et al., 1992). Resolving to gradient-based algorithms (e.g., gradient descent) for optimizing”
Bilevel Optimization: Convergence Analysis and Enhanced Design (2020, background): “For example, Hansen et al. 1992; Shi et al. 2005; Moore 2010 reformulated the bilevel problem in eq.”
Approximation Methods for Bilevel Programming (2018, background): “The ﬁrst one is to reduce the bilevel problem to a single level problem by replacing the inner optimization problem with its optimality conditions as constraints (see e.g., [11, 17]).”
A bilevel mixed-integer program for critical infrastructure protection planning (2008, background): “Bilevel programming problems fall into the class of NP-hard problems, even in their simplest form with only continuous variables [8].”
A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications (2017, background): “Bilevel programming is known to be strongly NP-hard [79], and it has been proven that merely evaluating a solution for optimality is also an NP-hard task [165].”
BlackIoT: IoT Botnet of High Wattage Devices Can Disrupt the Power Grid (2018, methodology): “Theoretical methods for detecting cyber attacks on power grids and recovering information after such attacks have also been developed [15, 20, 37, 39, 40, 55].”
Bilevel and multilevel programming: A bibliography review (1994, background): “Savard [81], where it is established that the linear BPP is strongly NP{Hard.”
An overview of bilevel optimization (2007, methodology): “Even the “simplest” instance, the linear-linear BLPP, was shown to be NP-hard by Jeroslow (1985), while Hansen et al. (1992) proved strong NP-hardness, using a reduction from KERNEL (see Garey and Johnson 1979).”
Self-Tuning Networks: Bilevel Optimization of Hyperparameters using Structured Best-Response Functions (2019, background): “When the objectives/constraints are restricted to be linear, quadratic, or convex, a common approach replaces the lower-level problem with its KKT conditions added as constraints for the upper-level problem (Hansen et al., 1992; Vicente et al., 1994).”