15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 July 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 July 2017

Schedule Authors My Schedule

Bilevel optimization I

Jul 12, 2017 09:45 AM – 11:00 AM

Location: PWC

Chaired by Patrice Marcotte

3 Presentations

  • 09:45 AM - 10:10 AM

    Value-function based non-cooperative games

    • Jong-Shi Pang, presenter, University of Southern California
    • Tianyu Hao, University of Southern California

    Generalizing the family of network interdiction games communicated to us by Andrew Liu and his collaborators,
    this paper studies a two-stage non-cooperative game wherein the objective function of each player's optimization problem contains a value function of a second-stage linear program parameterized by the first-stage variables,
    through a (possibly piecewise) linear function that upper bounds the second-stage decision variable. We investigate the solution existence of this game and methods for computing such solutions. The latter methods include Lemke's algorithm for problems with affine structures and best-response schemes in general.

  • 10:10 AM - 10:35 AM

    Theoretical and computational comparisons of formulations for Stackelberg bimatrix games

    • Martine Labbé, presenter, GOM, Université Libre de Bruxelles and INRIA
    • Carlos Casorran-Amilburu, Université libre de Bruxelles
    • Bernard Fortz, Université Libre de Bruxelles
    • Fernando Ordonez, Universidad de Chile

    Stackelberg Games confront contenders, a leader and a follower, with opposed objectives, each wanting to optimize their rewards. The objective of the game is for the leader to commit to a reward-maximizing strategy anticipating that the follower will best respond.
    A Stackelberg game can be modeled as a bilevel bilinear optimization problem. We present different single level reformulations and compare their LP relaxations from both theoretical and computational points of view.

  • 10:35 AM - 11:00 AM

    A branch-and -bound algorithm for a bilevel location-allocation model.

    • Patrice Marcotte, Université de Montréal
    • Andrea Lodi, University of Bologna
    • Teodora Dan, presenter, Université de Montréal

    We propose an exact branch-and-bound framework for determining the optimal locations and service levels associated with facilities, taking into account user behaviour and competition. In this bilevel maximization setting, we obtain a valid upper bound on the objective through the linearization of the lower level nonlinear terms. At each node of the enumeration tree where an integer solution (number of servers) is achieved, a feasible solution is computed by solving the follower's mathematical program. Preliminary numerical results will be presented and discussed.