bilevel optimization

Dual-density-based reweighted $\ell_{1}hBcalgorithms for a class of $\ell_{0}hBcminimization problems

  • Yun-Bin Zhao
    • Categories Convex and Nonsmooth Optimization Tags , , , , ,

    The optimization problem with sparsity arises in many areas of science and engineering such as compressed sensing, image processing, statistical learning and data sparse approximation. In this paper, we study the dual-density-based reweighted $\ell_{1}$-algorithms for a class of $\ell_{0}$-minimization models which can be used to model a wide range of practical problems. This class of … Read more

    Near-optimal Robust Bilevel Optimization

  • Miguel F. Anjos
  • Mathieu Besançon
  • Luce Brotcorne
    • Categories (Mixed) Integer Nonlinear Programming, Complementarity and Variational Inequalities, Robust Optimization Tags , , , , , ,

    Bilevel optimization studies problems where the optimal response to a second mathematical optimization problem is integrated in the constraints. Such structure arises in a variety of decision-making problems in areas such as market equilibria, policy design or product pricing. We introduce near-optimal robustness for bilevel problems, protecting the upper-level decision-maker from bounded rationality at the … Read more

    Optimal Aggregated Peak Shaving Via Residential Demand Response: A Framework for Retailers

  • Natalia Alguacil Conde
  • Michael David de Souza Dutra
    • Categories Energy Tags , , , ,

    This paper proposes an optimization framework for retailers that are involved in demand response (DR) programs. In a first phase responsive users optimize their own household consumption, characterizing not only their smart home components but also their comfort preferences. Then, the retailer exploits in a second phase this preliminary non-coordinated solution to implement a peak … Read more

    Optimal Design of Retailer-Prosumer Electricity Tariffs Using Bilevel Optimization

  • Veronika Grimm
  • Lars Schewe
  • Martin Schmidt
  • Galina Orlinskaya
  • Gregor Zöttl
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , , , ,

    We compare various flexible tariffs that have been proposed to cost-effectively govern a prosumer’s electricity management – in particular time-of-use (TOU), critical-peak-pricing (CPP), and a real-time-pricing tariff (RTP). As the outside option, we consider a fixed-price tariff (FP) that restricts the specific characteristics of TOU, CPP, and RTP, so that the flexible tariffs are at … Read more

    A mixed-integer optimization approach to an exhaustive cross-validated model selection for regression

  • Dennis Kreber
    • Categories (Mixed) Integer Nonlinear Programming, Statistics Tags , , , ,

    We consider a linear regression model for which we assume that many of the observed regressors are irrelevant for the prediction. To avoid overfitting, we conduct a variable selection and only include the true predictors for the least square fitting. The best subset selection gained much interest in recent years for addressing this objective. For … Read more

    There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization

  • Thomas Kleinert
  • Martine Labbé
  • Martin Schmidt
  • Fränk Plein
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities Tags , , , ,

    One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixed-integer linear optimization. The latter step requires to determine some big-M constant in order to bound the lower level’s dual feasible … Read more

    Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method

  • Thomas Kleinert
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , ,

    Bilevel problems are highly challenging optimization problems that appear in many applications of energy market design, critical infrastructure defense, transportation, pricing, etc. Often, these bilevel models are equipped with integer decisions, which makes the problems even harder to solve. Typically, in such a setting in mathematical optimization one develops primal heuristics in order to obtain … Read more

    The robust bilevel continuous knapsack problem with uncertain coefficients in the follower’s objective

  • Christoph Buchheim
  • Dorothee Henke
    • Categories Robust Optimization Tags , ,

    We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing according to his own profits, which may differ from those of the leader. To this bilevel problem, we add uncertainty in a natural way, assuming that the leader does not have full … Read more

    Interdiction of a Mixed-Integer Linear System

  • Ross Baldick
  • Bowen Hua
  • Kevin Wood
    • Categories Applications - OR and Management Sciences, Integer Programming Tags , ,

    A system-interdiction problem can be modeled as a bilevel program in which the upper level models interdiction decisions and the lower level models system operation. This paper studies MILSIP, a mixed-integer linear system interdiction problem, which assumes binary interdiction decisions and models system operations through a mixed-integer linear program. To solve large-scale instances of MILSIP, … Read more

    Mixed-integer bilevel representability

  • Amitabh Basu
  • Christopher Thomas Ryan
  • Sriram Sankaranarayanan
    • Categories (Mixed) Integer Nonlinear Programming, Integer Programming Tags ,

    We study the representability of sets that admit extended formulations using mixed-integer bilevel programs. We show that feasible regions modeled by continuous bilevel constraints (with no integer variables), complementarity constraints, and polyhedral reverse convex constraints are all finite unions of polyhedra. Conversely, any finite union of polyhedra can be represented using any one of these … Read more