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

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

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

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

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

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

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

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

A Multicriteria Approach to Bilevel Optimization

In this paper we study the relationship between bilevel optimization and bicriteria optimization. Given a bilevel optimization problem, we introduce an order relation such that the optimal solutions of the bilevel problem are the nondominated points with respect to the order relation. In the case where the lower level problem of the bilevel optimization problem … Read more