bilevel optimization

An Exact Projection-Based Algorithm for Bilevel Mixed-Integer Problems with Nonlinearities

  • Maximilian Merkert
  • Galina Orlinskaya
  • Dieter Weninger
    • Categories (Mixed) Integer Nonlinear Programming, Game Theory, Global Optimization Tags , , , ,

    We propose an exact global solution method for bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, \eg, products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems … Read more

    Optimization under rare chance constraints

  • Vishwas Rao
  • Anirudh Subramanyam
  • Shanyin Tong
    • Categories Stochastic Programming Tags , , ,

    Chance constraints provide a principled framework to mitigate the risk of high-impact extreme events by modifying the controllable properties of a system. The low probability and rare occurrence of such events, however, impose severe sampling and computational requirements on classical solution methods that render them impractical. This work proposes a novel sampling-free method for solving … Read more

    Valid Inequalities for Mixed Integer Bilevel Linear Optimization Problems

  • Ted K. Ralphs
  • Sahar Tahernejad
    • Categories Cutting Plane Approaches, Game Theory, Polyhedra Tags , ,

    Despite the success of branch-and-cut methods for solving mixed integer bilevel linear optimization problems (MIBLPs) in practice, there have remained some gaps in the theory surrounding these methods. In this paper, we take a first step towards laying out a theory of valid inequalities and cutting-plane methods for MIBLPs that parallels the existing theory for … Read more

    On Linear Bilevel Optimization Problems with Complementarity-Constrained Lower Levels

  • Steven A. Gabriel
  • Martin Schmidt
  • Marina Leal
    • Categories Applications - OR and Management Sciences, Complementarity and Variational Inequalities Tags , , , , ,

    We consider a novel class of linear bilevel optimization models with a lower level that is a linear program with complementarity constraints (LPCC). We present different single-level reformulations depending on whether the linear complementarity problem (LCP) as part of the lower-level constraint set depends on the upper-level decisions or not as well as on whether … Read more

    Why there is no need to use a big-M in linear bilevel optimization: A computational study of two ready-to-use approaches

  • Thomas Kleinert
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Cutting Plane Approaches Tags , , , , ,

    Linear bilevel optimization problems have gained increasing attention both in theory as well as in practical applications of Operations Research (OR) during the last years and decades. The latter is mainly due to the ability of this class of problems to model hierarchical decision processes. However, this ability makes bilevel problems also very hard to … Read more

    Optimal Residential Users Coordination Via Demand Response: An Exact Distributed Framework

  • Natalia Alguacil Conde
  • Michael David de Souza Dutra
    • Categories (Mixed) Integer Linear Programming, Energy Tags , , ,

    This paper proposes a two-phase optimization framework for users that are involved in demand response programs. In a first phase, responsive users optimize their own household consumption, characterizing not only their appliances and equipment but also their comfort preferences. Subsequently, the aggregator exploits in a second phase this preliminary noncoordinated solution by implementing a coordination … Read more

    Characterization of an Anomalous Behavior of a Practical Smoothing Technique

  • Pedro Borges de Melo
    • Categories Game Theory, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    A practical smoothing method was analyzed and tested against state-of-the-art solvers for some non-smooth optimization problems in [BSS20a; BSS20b]. This method can be used to smooth the value functions and solution mappings of fully parameterized convex problems under mild conditions. In general, the smoothing of the value function lies from above the true value function … Read more

    Mixed Integer Bilevel Optimization with k-optimal Follower: A Hierarchy of Bounds

  • Xueyu Shi
  • Oleg A. Prokopyev
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Game Theory Tags ,

    We consider mixed integer bilevel linear optimization problems in which the decision variables of the lower-level (follower’s) problem are all binary. We propose a general modeling and solution framework motivated by the practical reality that in a Stackelberg game, the follower does not always solve their optimization problem to optimality. They may instead implement a … Read more

    Inexact Derivative-Free Optimization for Bilevel Learning

  • Matthias J. Ehrhardt
  • Lindon Roberts
    • Categories Nonlinear Optimization Tags , , ,

    Variational regularization techniques are dominant in the field of mathematical imaging. A drawback of these techniques is that they are dependent on a number of parameters which have to be set by the user. A by now common strategy to resolve this issue is to learn these parameters from data. While mathematically appealing this strategy … Read more

    Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality

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

    Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker (KKT) conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch- and-cut has proven to be a powerful extension … Read more