BIO-SEL: Bilevel optimization that solves problems in safety problems in safety, energy and logistics

In a world increasingly involved in technology, where security problems arise, the BIO-SEL Associate Team - which comes from the previous BIPLOS Associate Team - was created, led by Martine Labbé, from the INOCS project-team of the Inria centre at the Université of Lille, and Vladimir Marianov, from the Pontificia Universidad Católica de Chile (PUC).

 The initiative is also composed of researchers from the Faculty of Physical and Mathematical Sciences (FCFM) of the Universidad de Chile, the Universidad de Santiago de Chile, and the Universidad de O'Higgins, and focuses on bilevel scheduling, a sub-area of optimization applied to logistics and security problems. This offers great opportunities in terms of solving optimization problems, as it provides a framework for understanding various applications in energy projects.

This time, we spoke with Martine Labbé, researcher, coordinator of the BIO-SEL project, professor at the Université Libre de Bruxelles and researcher of Inria's INOCS project-team; and Vladimir Marianov, researcher, coordinator of the BIO-SEL project and professor at PUC, specialist in telecommunications and mathematical models of resource localization, to learn more about their collaborative work.

Could you introduce us to BIO-SEL?

- Vladimir Marianov (VM): On the Chilean side, the team includes several senior researchers from different universities and a research institute: Fernando Ordóñez, from Universidad de Chile; Víctor Bucarey, from Universidad de O'Higgins; Sebastián Dávila, from Universidad de Santiago, and myself. Víctor and Sebastián were students when the collaboration began. Currently, Pamela Bustamante, from the Pontificia Universidad Católica de Chile, also participates. 

- Martine Labbé (ML): On the Inria centre at the Université of Lille side, the team is composed of high-level researchers: Luce Brotcorne, Hélène Le Cadre, Frédéric Semet and myself.

© Inria / Photo M. Magnin

How did BIO-SEL originate? How did you start to collaborate for the first time? 

- ML: I have a longstanding collaboration with Fernando Ordóñez, on bilevel optimization problems.  We have co-supervised a Ph.D. student who has worked on Stackelberg security games. The Associate team program of Inria gave us the possibility to officialize this fruitful collaboration and obtain some funds to support it. Given that there was also a common interest from both sides to study problems in logistics, we have naturally extended the scope of our project in this direction. 

Which are the specific areas of research of each of you? and what scientific questions are you seeking to answer or have already answered with the project?

- VM: The team covers a broad spectrum of interests and subjects. It is not easy to just separate the individual interests, as all the subjects are actually overlapped. I could say that the interaction of different agents and the study of the response of each one of them to actions to the remaining ones could be a way of describing what keeps us together. This could mean Security games, in which an agent has to defend different types of targets from attackers, knowing that there is a likelihood of attack; the actions of a store owner to gain as much market as possible and its actions when competitors could come later to capture market from it, are two of the examples of problems we solve.

We have recently developed efficient formulations for some variants of the Stackelberg security game. We also considered a product line optimization problem  faced by a retail chain owning multiple stores. The method we developed to solve this problem improves the state of the art.

What are BIO-SEL's objectives?

- VM: One of the objectives is to help understand how defenders have to act when there is the possibility of attacks, in very different contexts, and develop strong efficient mathematical tools to solve these problems.  A second objective of this stage of the work is to study the assortment problem when a group of stores is owned by a firm that wants to maximize its sales. The assortment problem consists of deciding what products should be displayed at which store.

- ML: Our general objective is to develop efficient and scalable methods for bilevel optimization problems, in particular for some Stackelberg security games and some applications in logistics and energy. We investigate several questions. Namely, how to formulate and solve efficiently a Stackelberg in which there is an exponential number of pure strategies. This applies to the case where there is a limited budget allocated to securing targets. In logistics, we pursue our collaboration on assortment problems and also initiate some research on the optimal coalition formation for buyers.

Various websites, such as Groupon, propose products whose prices depend on the demand and buyers can coordinate to obtain better prices. Generally, there exists a central entity, the coordinator, that realizes the formation of coalitions and distributes the payments to the players. We consider the Coalition Structure Generation (CSG) problem that focuses on partitioning the set of agents into mutually disjoint coalitions in such a way that the total reward is maximized.  Given that problem CSG is known to be NP-hard, we plan to develop mixed integer linear models.

What are the specific applications that BIO-SEL could have or has had?

- VM: Since the objective is to apply to logistical and security problems, we can highlight police patrolling, assortment and the formation of buyer coalitions.

- ML: It is applicable in security games, specifically in prevention of terrorist attacks, airport control, smuggling prevention, etc. Product variety and pricing are important marketing strategies.

How is the work between the French and Chilean teams complementary?

- VM: Naturally, each scientist has his or her own areas of expertise. We have focused on collaborating by contributing each one from his or her own expertise, be it mathematical, or on applications. I would say that what has been most important is the opportunity of exposing students to different groups, and different working cultures.

- ML: We all have different profiles, be it more applied, more theoretical, algorithm oriented, etc. I would say that our expertise is intertwined. This project has been essential for several young researchers by allowing them to do long term visits abroad. They could benefit from the advice of the other team part members and be immersed in the other team part culture for a while.