← volver

Seminario / Oleg A. Prokopyev, U. Pittsburgh

13:30 horas, Sala de Consejo, Beauchef 851 (4to piso).

Invitado: Oleg A. Prokopyev, Ph.D, Professor in the Department of Industrial Engineering at the University of Pittsburgh.

 “Dealing with the Lower-level (Follower’s) Problem in Bilevel Mixed-Integer Linear Programming”.

Abstract

In bilevel optimization, two independent decision-makers (known as the leader and the follower) with their own distinct objective functions are involved in a hierarchical decision-making process.  The leader (the upper-level decision-maker) acts first, and then the follower (the lower-level  decision-maker)  determines  the response  in  terms  of  their  own  optimization  model, whose feasible  region  and  objective  function  are  parameterized  on the  leader’s  decision. Importantly, the follower’s response also affects the leader’s objective function. Bilevel programming models arise in several important application domains including network design, revenue management, energy and defense. As we first briefly overview in this talk, complexity of solving bilevel programs depends on the structure of the lower-level problem, in particular, whether the lower-level problem involves integrality restrictions. Our main focus is on bilevel mixed-integer linear optimization problems in which the decision variables of the lower-level 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 locally optimal solution with respect to a given leader’s decision. Such scenarios may occur when the follower’s computational capabilities are limited, or when the follower is not completely rational. Our framework relaxes the typical assumption of perfect rationality that underlies the standard modeling framework by defining a hierarchy of increasingly stringent assumptions about the behavior of the follower. Associated with this hierarchy is a hierarchy of upper and lower bounds that are in fact valid for the classical case in which complete rationality of the follower is assumed. Two mixed integer linear optimization problem formulations are derived for the resulting bilevel optimization problems.

Furthermore, we briefly discuss how the framework can be applied to a general class of bilevel matroid problems. Extensive computational results are provided to demonstrate the effectiveness of our formulations and the quality of the bounds produced. This is a joint work with Xueyu Shi and Ted Ralphs.

Contacto: Linda Valdés / lvaldes@dii.uchile.cl