Plenary Speakers > Ivana Ljubic

ljubic

Ivana Ljubic

Ivana Ljubic is Professor of Operations Research at the ESSEC Business School of Paris. She received her habilitation in Operations Research at the University of Vienna (2013), and she holds a PhD degree in computer science from the Vienna University of Technology (2004) and master's degree in mathematics from the University of Belgrade (2000). She worked for two years in a company dealing with portfolio optimization before continuing her university career at the University of Vienna where she was appointed until 2015. She was also Visiting Researcher/Professor at the following institutions: University of Maryland, TU Berlin, TU Dortmund, University of Paris Dauphine, etc. As of September 2015, she is appointed at the ESSEC Business School of Paris.

She is Associate Editor of Omega and member of Editorial Advisory Board of Computers and Operations Research. She also served as guest-editor of journals: European Journal of Operational Research and Annals of Operations Research and she is currently vice-president of the INFORMS Telecommunication Section

Research interests of Ivana Ljubic include network design problems, combinatorial optimization, optimization under uncertainty, bilevel optimization. She uses tools and methods of mixed integer programming, (meta-)heuristics and their successful combinations for solving optimization problems with applications in telecommunications, design of data and distribution networks and bioinformatics. 

She received PhD Fellowship of the Austrian Academy of Sciences (DOC Fellowship, 2003-2004), PhD award of the Austrian Society for Operations Research (2005), Hertha-Firnberg Post-Doc Fellowship of the Austrian Science Fund (2007-2010) and APART Fellowship of the Austrian Academy of Sciences (2011-2013). 

 

New Branch-and-Cut Algorithms for Mixed-Integer Bilevel Linear Programs

In this talk we focus on new branch-and-cut (B&C) algorithms for dealing with mixed-integer bilevel linear programs (MIBLPs). MIBLPs constitute a significant family of bilevel optimization problems, where all objective functions and constraints are linear, and some/all variables are required to take integer values. We first consider a general case in which the proposed B&C scheme relies on intersection cuts derived from feasible-free convex sets, see [1,2]. Our B&C scheme is finitely-convergent in case both the leader and the follower problems are pure integer. In addition, it is capable of dealing with continuous variables both in the leader and in follower problems—provided that the leader variables influencing follower’s decisions are integer and bounded. Our new algorithm consistently outperforms (often by a large margin) all alternative state-of-the-art methods from the literature, including methods which exploit problem specific information for special instance classes. In particular, it allows to solve to optimality more than 300 previously unsolved instances from literature. We then focus on a subfamily of MIBLPs in which the leader and follower typically share a set of items, and the leader can select some items and interdict their usage by the follower. The only constraints in the follower subproblem involving leader decision variables impose that, if an interdiction variable is selected by the leader, then certain actions of the follower are inhibited. Interdiction Problems, Blocker Problems, Critical Node/Edge Detection Problems are some examples satisfying the later condition. We show that, in case the follower subproblem satisfies monotonicity property, a family of "interdiction-cuts" can be derived resulting in a more efficient B&C scheme. Computational results are reported for the (multidimensional) knapsack interdiction and the maximum clique interdiction problems, see [3,4].

Literature:

[1] M. Fischetti, I. Ljubic, M. Monaci, M. Sinnl, On the Use of Intersection Cuts for Bilevel Optimization, Mathematical Programming, online first, 2017, DOI 10.1007/s10107-017-1189-5

[2] M. Fischetti, I. Ljubic, M. Monaci, M. Sinnl, A new general-purpose algorithm for mixed-integer bilevel linear programs, Operations Research 65(6): 1615-1637, 2017

[3] M. Fischetti, I. Ljubic, M. Monaci, M. Sinnl: Interdiction Games and Monotonicity, with Application to Knapsack Problems, INFORMS Journal on Computing, to appear, 2018

[4] F. Furini, I. Ljubic. P. San Segundo, S. Martin: The Maximum Clique Interdiction Game, submitted, 2018

Online user: 1