15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, July 12 — 14, 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, July 12 — 14, 2017

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

Bilevel optimization I

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

Location: PWC

Chaired by Patrice Marcotte

3 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

Back