Registered Data

[02513] Models for the Interdiction Problem for the Minimum Spanning Tree

  • Session Time & Room : 3C (Aug.23, 13:20-15:00) @D502
  • Type : Contributed Talk
  • Abstract : The Minimum Spanning Tree Interdiction (MSTI) problem is a two-player game between a network operator aiming to determine a Minimum Spanning Tree (MST) and an interdictor which, constrained by a budget, changes the network topology to increase the weight of a MST. Mathematical formulations for a generalization of the MSTI problem are devised, and valid inequalities are proposed. Dominance relations between the models are studied, and computational experiments are presented to evaluate their efficiencies.
  • Classification : 90-10, 90C10, 90C46, Bilevel programming
  • Format : Talk at Waseda University
  • Author(s) :
    • Luis Salazar-Zendeja (INRIA)
    • Diego Cattaruzza (Centrale Lille)
    • Martine Labbé (Université Libre de Bruxelles)
    • Frédéric Semet (Centrale Lille)