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

Date :
Changed on 29/08/2023
Inria-0377-105
© Inria / Photo M. Magnin

 

 

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.

 

Martine Labbé, del equipo Inocs en videoconferencia, en el centro Inria de la Université de Lille
©
© Inria / Photo M. Magnin
Martine Labbé, from the Inocs team in videoconference, in the Inria centre at the Université of Lille

 

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

Image
Vladimir-Marianov
Verbatim

Informal collaboration started a long time ago, when researchers from both sides met at different academic events. Inria gave us the opportunity of formalizing a collaboration through the joint work on subjects that were of interest to all parties. This collaboration included joint papers and, very important, student and researchers exchange between three countries: France, Belgium and Chile.

Auteur

Vladimir Marianov

Poste

Researcher, Full Professor, Professor Emeritus at Department of Electrical Engineering, Faculty of Engineering, Pontificia Universidad Católica de Chile

- 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.

Image
Martine Labbé
Verbatim

 

In very general terms, we are interested in optimization problems arising in a multi-agent context. Stackelberg security games, product line and price optimization problems constitute examples of problems we are working on together. We develop mixed integer linear models and algorithms to solve these problems.

Auteur

Martine Labbé

Poste

Professor at Université Libre de Bruxelles and Researcher at INOCS project-team of the Inria centre at the Université of Lille

 

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.

What is an Associate Team?

An Associate Team is a joint research project between an Inria project-team and a foreign research team. For a period of three years, the partners jointly define a scientific objective, a research plan and a program of bilateral exchanges, financed by Inria.

Since Inria's arrival in Chile in 2012, 29 French-Chilean research projects in different areas of digital sciences have been funded under this program by Inria. 

Currently, there are nine Associate Teams working, in which researchers from Inria centers in France collaborate, such as Inria centre at the University of Bordeaux, Inria centre at the University Grenoble Alpes, Inria centre at the University of Lille, Inria Lyon Centre, Inria Nancy - Grand Est Centre, Inria Paris Centre, Inria Centre at Rennes University, Antenne Inria at University of Montpellier, Inria Saclay Centre, and Chilean institutions, such as the Universidad de Chile, Pontificia Universidad Católica de Chile, Universidad del Bío Bío, Pontificia Universidad Católica de Valparaíso, Universidad Adolfo Ibáñez and Universidad de O'Higgins.

Inria-0289-519

Apply to the call for Associate Teams 2024!