Session Detail Information
Add this session to your itinerary

Cluster :  Combinatorial Optimization

Session Information  : Monday Jul 13, 14:45 - 16:15

Title:  Bilevel Programming Problems in Combinatorial Optimization and Game Theory
Chair: Stefano Coniglio,Phd, RWTH Aachen University, Lehrstuhl 2 für Mathematik, Pontdriesch 14-16, Aachen 52062, Germany, coniglio@math2.rwth-aachen.de

Abstract Details

Title: Bilevel Optimization in Game Theory
 Presenting Author: Margarida Carvalho,INESC TEC and Faculty of Sciences, University of Porto, Rua Campo Alegre 1021/1055, Porto 4169-007, Portugal, margarida.carvalho@dcc.fc.up.pt
 Co-Author: Alberto Caprara,DEI, University of Bologna, Viale Risorgimento 2, Bologna 40136, Italy, alberto.caprara@unibo.it
 Andrea Lodi,University of Bologna, Viale Risorgimento 2, Bologna, Italy, andrea.lodi@unibo.it
 Gerhard Woeginger,Department of Mathematics and Computer Science Eindhoven University of Technology, P.O. Box 513, Eindhoven 5600, Netherlands, gwoegi@win.tue.nl
 
Abstract: Real economic markets can be described as games, this is, a participant decision has influence in the other participants' revenues. In this presentation, an algorithmic method for a sequential game, the bilevel knapsack with interdiction constraints, is proposed and it's generalization to other competitive games is discussed. We conclude by showing that a broad class of simultaneous mixed integer games is at least as hard as this bilevel knapsack problem.
  
Title: A Backward Sampling Framework for Interdiction Problems with Fortification
 Presenting Author: Leonardo Lozano,PhD Student, Clemson University, llozano@clemson.edu
 Co-Author: Cole Smith,Clemson University, jcsmith@clemson.edu
 
Abstract: We examine a class of three-stage sequential defender-attacker-defender problems that are notoriously difficult to optimize, and almost always require the third-stage (recourse) problem to be a convex optimization problem. We propose a new approach in which we allow the recourse problem to take any form. The proposed framework restricts the defender to select a recourse decision from a sample of feasible vectors and iteratively refines the sample to force finite convergence to an optimal solution. We provide computational experiments on the traveling salesman interdiction problem with fortification to demonstrate that our algorithm solves interdiction problems involving NP-hard recourse problems within reasonable computational limits.
  
Title: Novel Formulations for General Stackelberg and Stackelberg Security Games
 Presenting Author: Carlos Casorrán-Amilburu,Ph.D. Candidate, Université Libre de Bruxelles, Boulevard du Triomphe B-1050 Bruxelles, Brussels 1050, Belgium, casorranamilburu@gmail.com
 Co-Author: Bernard Fortz,Université Libre de Bruxelles - Graphes et Optimisation Mathématique, Boulevard du Triomphe CP 210/01, Bruxelles 1050, Belgium, bernard.fortz@ulb.ac.be
 Martine Labbé,Professor, Université Libre de Bruxelles, Bd. du Triomphe, CP 212, Brussels 1050, Belgium, mlabbe@ulb.ac.be
 Fernando Ordóñez,Associate Professor, Universidad de Chile, Republica 701, Santiago, Chile, fordon@dii.uchile.cl
 
Abstract: We categorize Stackelberg Game formulations present in the literature, according to their use of big M constants and explore how they can be ordered in terms of tightness of their continuous relaxation. We present a novel formulation whose constraints do not require large positive constants. We provide tight values for these big M constants in each of the formulations and perform exhaustive computational experiments between formulations to see where we stand. We establish a relationship between the novel formulations provided for the General Stackelberg Games and for Security Games by means of a projection result and obtain convex hull-defining formulations when we restrict the problem to a single type of follower.