Workshop Lecture 2, 12/02/2021, 12:00 - 13:00
Department of Information Systems, Decision Sciences and Statistics
ESSEC Business School, Paris
Plenary 2
New integer and Bilevel Formulations for the k-Vertex Cut Problem
The family of Critical Node Detection Problems asks for finding a subset of vertices, deletion of which minimizes or maximizes a predefined connectivity measure on the remaining network. We study a problem of this family called the k-vertex cut problem. The problems asks for determining the minimum weight subset of nodes whose removal disconnects a graph into at least k components. We provide two new integer linear programming formulations, along with families of strengthening valid inequalities. Both models involve an exponential number of constraints for which we provide poly-time separation procedures and design the respective branch-and-cut algorithms. In the first formulation one representative vertex is chosen for each of the k mutually disconnected vertex subsets of the remaining graph. In the second formulation, the model is derived from the perspective of a two-phase Stackelberg game in which a leader deletes the vertices in the first phase, and in the second phase a follower builds connected components in the remaining graph. Our computational study demonstrates that a hybrid model in which valid inequalities of both formulations are combined significantly outperforms the state-of-the-art exact methods from the literature.
Joint work with F. Furini, E. Malaguti and P. Paronuzzi
Biosketch
Ivana Ljubic is Academic Director of the ESSEC & Mannheim EMBA program. She teaches Decision Analysis, Optimal Decision Making, Operations Research (OR) and Business Mathematics in ESSEC MSc, PhD and Advanced Master programs. Prior to joining ESSEC in 2015, she was appointed at the University of Vienna. She also worked as Visiting Scholar/Professor at the Robert H. Smith School of Business at the University of Maryland, TU Dortmund, TU Berlin, Dauphine University.
Research interests of Ivana Ljubic include combinatorial optimization, optimization under uncertainty, bilevel optimization. She uses tools and methods of mixed integer (non-) linear programming, meta-heuristics and their successful combinations for solving optimization problems with applications in network design, telecommunications, transportation, logistics, routing and bioinformatics. She has published more than 50 articles in leading OR journals, including Operations Research, Management Science, Mathematical Programming, INFORMS JOC, European Journal of Operational Research.
She is member of the Editorial Advisory Board for the journals European Journal of Operational Research, Computers & Operations Research, and she is Associate Editor for the journals Omega and Journal of Global Optimization. She also served as guest-editor of journals: European Journal of Operational Research and Annals of Operations Research.
She currently serves as chair of the INFORMS Telecommunication and Network Analytics Section. From 2010-2016 she was member of council of the INFORMS Telecommunication Section and from 2006 to 2008 she was member of the executive board of the Austrian OR Society (OEGOR).
She has received numerous research grants, including those from the French Ministry of Foreign Affairs (PHC program), Austrian Academy of Sciences (OEAW), Austrian Research Fund (FWF) and European Commission (ERA-NET).