Skip to main navigationSkip to main content
The University of Southampton
Mathematical Sciences

CORMSIS Seminar - The Maximum Clique Interdiction Game, Dr Fabio Furini (Paris-Dauphine) Seminar

Operation Research Group
Time:
14:00 - 15:00
Date:
16 August 2018
Venue:
Room 8031, Building 54, Mathematical Sciences, University of Southampton, Highfield Campus, SO17 1BJ

For more information regarding this seminar, please email Konstantinos Katsikopoulos at K.Katsikopoulos@southampton.ac.uk .

Event details

We study the two player zero-sum Stackelberg game in which the leader interdicts (removes) a limited number of vertices from the graph, and the follower searches for the maximum clique in the interdicted graph. The goal of the leader is to derive an interdiction policy which will result in the worst possible outcome for the follower. This problem has applications in many areas, such as crime detection, prevention of outbreaks of infectious diseases and surveillance of communication networks. We design an exact solution framework based on a Bilevel Integer Linear Programming model. Thanks to the study of the polytope of the corresponding single-level reformulation, we derive a branch-and-cut algorithm and enhance it by tight combinatorial lower and upper bounds, which also allow for a drastic reduction of the size of the input graph. Our model is based on an exponential family of Clique-Interdiction Cuts whose separation requires solving the maximum clique problem. We derive an effective separation procedure based on a newly developed combinatorial algorithm that is tailored for finding maximum cliques in interdicted graphs. We assess the applicability and the limits of our exact framework on publicly available instances, including large-scale social networks with up to one hundred thousand vertices and three million edges. Most of these instances are solved to provable optimality within short computing times. Our code (which will be also publicly available) allows to analyze the resilience of (social) networks with respect to vertex-interdiction attacks, i.e., the decrease of the size of the maximum clique in function of incremental interdiction budget level.

Speaker information

Dr Fabio Furini, Paris-Dauphine. Fabio Furini received his Bachelors and Masters degrees in Engineering and Industrial Management, and his Ph.D in Automation and Operations Research at the University of Bologna in 2004, 2007 and 2011 respectively. He has since conducted periods of research at prestigious universities in Europe and the United States, including the University of Colorado and Imperial College London. He currently holds a position as assistant professor at Paris-Dauphine University. His work is a combination of the disciplines of Mathematics, Economics, Information Technology, and Operations Research. He has used advanced analytical techniques to arrive at optimal or near-optimal solutions to intricate decision-making problems. The focus of his research has been on achieving operational efficiencies, aiming to develop general software, generalizable insights and applications. In particular, his work has dealt with techniques and algorithms for Mixed Integer Linear and Non-Linear Programming problems, and the study of challenging applications such as Aircraft Routing and Sequencing and Train Timetabling. He has published articles on these subjects in many leading international journals in the field of optimization.

Privacy Settings