Home Events OPTIMA Seminar 21 September 2022 16:30


Sep 21 2022


4:30 pm - 5:30 pm



OPTIMA Seminar 21 September 2022 16:30

Speaker: Ivana Ljubic is a Professor of Operations Research at the ESSEC Business School of Paris

Abstract:  Given an undirected graph, we study the capacitated vertex separator problem, which asks to find a subset of vertices of minimum cardinality, the removal of which induces a graph having a bounded number of pairwise disconnected shores (subsets of vertices) of limited cardinality. The problem is of great importance in the analysis and protection of communication/social networks against possible viral attacks, and for matrix decomposition algorithms.We provide a new bilevel interpretation of the problem and model it as a two-player Stackelberg game, in which the leader interdicts the vertices (i.e., decides on the subset of vertices to remove), and the follower solves a combinatorial optimization problem on the resulting graph. This approach allows us to develop a computational framework based on an integer programming formulation in the natural space of the variables. Thanks to this bilevel interpretation, we derive three different families of strengthening inequalities and show that they can be separated in polynomial time. We also show how to extend these results to a min-max version of the problem.Our extensive computational study conducted on available benchmark instances from the literature reveals that our new exact method is competitive against the state-of-the-art algorithms, and is able to improve the best-known results for several difficult classes of instances.

This talk is based on the paper:

Fabio Furini, Ivana Ljubic, Enrico Malaguti, Paolo Paronuzzi: Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem. Oper. Res. 70(4): 2399-2420 (2022)

Biography: Ivana Ljubic is a Professor of Operations Research at the ESSEC Business School of Paris. She holds a PhD in computer science from the Vienna University of Technology (2004). Prior to joining ESSEC in 2015, she was appointed at the University of Vienna, where she also received her habilitation in Operations Research in 2013. Research interests of Ivana Ljubic include combinatorial optimization, optimization under uncertainty and bilevel optimization, with applications in network design, telecommunications and logistics.  She is a member of the Editorial Board of the European Journal of Operational Research, Computers & Operations Research, and she is Associate Editor for Transportation Science and Networks.


ZOOM MEETING ID: 873 1557 5255; PASSWORD: 778635

More Info


The event is finished.


Sep 21 2022

Advancing an industry-ready optimisation toolkit, while training a new generation of industry practitioners and over 120 young researchers, who will vanguard a highly skilled workforce of change agents for industrial transformation.

Monash University
Clayton, Victoria, 3080

University of Melbourne
Parkville, Victoria, 3010

© 2021 ARC Industrial Transformation Training Centre in Optimisation Technologies, Integrated Methodologies and Applications (OPTIMA)