bilevel optimization

Complexity of Bilevel Coherent Risk Programming

  • Jonathan Eckstein
    • Categories Stochastic Programming Tags , ,

    This paper considers a bilevel programming approach to applying coherent risk measures to extended two-stage stochastic programming problems. This formulation technique avoids the time-inconsistency issues plaguing naive models and the incomposability issues which cause time-consistent formulations to have complicated, hard-to-explain objective functions. Unfortunately, the analysis here shows that such bilevel formulations, when using the standard … Read more

    Packing Ellipsoids with Overlap

  • Caroline Uhler
  • Stephen Wright
    • Categories Biomedical Applications, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    The problem of packing ellipsoids of different sizes and shapes into an ellipsoidal container so as to minimize a measure of overlap between ellipsoids is considered. A bilevel optimization formulation is given, together with an algorithm for the general case and a simpler algorithm for the special case in which all ellipsoids are in fact … Read more

    Bilevel Programming and the Separation Problem

  • Andrea Lodi
  • Ted K. Ralphs
  • Gerhard J. Woeginger
    • Categories Cutting Plane Approaches, Integer Programming Tags , , ,

    In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is … Read more

    Sensitivity analysis for two-level value functions with applications to bilevel programming

  • Stephan Dempe
  • Boris S. Mordukhovich
  • Alain Zemkoho
    • Categories Nonlinear Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , , , ,

    This paper contributes to a deeper understanding of the link between a now conventional framework in hierarchical optimization spread under the name of the optimistic bilevel problem and its initial more dicult formulation that we call here the original optimistic bilevel optimization problem. It follows from this research that, although the process of deriving necessary … Read more

    Interdiction Branching

  • Andrea Lodi
  • Ted K. Ralphs
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories 0-1 Programming, Branch and Cut Algorithms Tags , , , , , ,

    This paper introduces interdiction branching, a new branching method for binary integer programs that is designed to overcome the difficulties encountered in solving problems for which branching on variables is inherently weak. Unlike traditional methods, selection of the disjunction in interdiction branching takes into account the best feasible solution found so far. In particular, the … Read more

    Bilevel Derivative-Free Optimization and its Application to Robust Optimization

  • Andrew R. Conn
  • Luis Nunes Vicente
    • Categories Nonlinear Optimization Tags , , , , ,

    We address bilevel programming problems when the derivatives of both the upper and the lower level objective functions are unavailable. The core algorithms used for both levels are trust-region interpolation-based methods, using minimum Frobenius norm quadratic models when the number of points is smaller than the number of basis components. We take advantage of the … Read more

    A Branch-and-cut Algorithm for Integer Bilevel Linear Programs

  • Scott Denegre
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Game Theory Tags , ,

    We describe a rudimentary branch-and-cut algorithm for solving integer bilevel linear programs that extends existing techniques for standard integer linear programs to this very challenging computational setting. The algorithm improves on the branch-and-bound algorithm of Moore and Bard in that it uses cutting plane techniques to produce improved bounds, does not require specialized branching strategies, … Read more

    A polyhedral study of the Network Pricing Problem with Connected Toll Arcs

  • GĂ©raldine Heilporn
  • Martine LabbĂ©
  • Patrice Marcotte
  • Gilles Savard
    • Categories (Mixed) Integer Linear Programming, Yield Management Tags , ,

    Consider the problem that consists in maximizing the revenue generated by tolls set on a subset of arcs of a transportation network, and where origin-destination flows are assigned to shortest paths with respect to the sum of tolls and initial costs. In this work, we address the instance where toll arcs must be connected, as … Read more

    On the Relationship between Bilevel Decomposition Algorithms and Direct Interior-Point Methods

  • Victor DeMiguel
  • Francisco Javier Nogales
    • Categories Constrained Nonlinear Optimization, Multidisciplinary Design Optimization Tags , , ,

    Engineers have been using \emph{bilevel decomposition algorithms} to solve certain nonconvex large-scale optimization problems arising in engineering design projects. These algorithms transform the large-scale problem into a bilevel program with one upper-level problem (the master problem) and several lower-level problems (the subproblems). Unfortunately, there is analytical and numerical evidence that some of these commonly used … Read more

    A Local Convergence Analysis of Bilevel Decomposition Algorithms

  • Victor DeMiguel
  • Walter Murray
    • Categories Multidisciplinary Design Optimization, Nonlinear Optimization Tags , , ,

    Decomposition algorithms exploit the structure of large-scale optimization problems by breaking them into a set of smaller subproblems and a coordinating master problem. Cutting-plane methods have been extensively used to decompose convex problems. In this paper, however, we focus on certain nonconvex problems arising in engineering. Engineers have been using bilevel decomposition algorithms to tackle … Read more