BIO-SEL: la optimización Binivel que resuelve problemas en seguridad, energía y logística

En un mundo cada vez más involucrado en la tecnología, donde surgen problemas de seguridad, surgió el Equipo Asociado BIO-SEL -que proviene del Equipo Asociado anterior BIPLOS-, el cual es liderado por Martine Labbé, del equipo-proyecto INOCS del centro Inria de la Université de Lille, y Vladimir Marianov, de la Pontificia Universidad Católica de Chile (PUC).

 La iniciativa la componen, además, investigadores de la Facultad de Ciencias Físicas y Matemáticas (FCFM) de la Universidad de Chile, de la Universidad de Santiago de Chile y de la Universidad de O'Higgins, y se enfoca en la programación Binivel, una subárea de optimización que se aplica a problemas de logística y seguridad. Esta ofrece grandes oportunidades en términos de resolución de problemas de optimización, ya que proporciona un marco para comprender variadas aplicaciones en proyectos energéticos. 

Esta vez, hablamos con Martine Labbé, investigadora, coordinadora del proyecto BIO-SEL, profesora de la Université Libre de Bruxelles e investigadora del equipo-proyecto INOCS de Inria; y con Vladimir Marianov, investigador, coordinador del proyecto BIO-SEL y docente de la PUC, especialista en telecomunicaciones y modelos matemáticos de localización de recursos, para conocer más acerca de su trabajo colaborativo. 

¿Podrían presentarnos a BIO-SEL?

- Vladimir Marianov (VM): Por la parte chilena, el equipo cuenta con varios investigadores sénior de distintas universidades y de un instituto de investigación: Fernando Ordóñez, de la Universidad de Chile; Víctor Bucarey, de la Universidad de O'Higgins; Sebastián Dávila, de la Universidad de Santiago, y por mí. Víctor y Sebastián eran estudiantes cuando comenzó la colaboración. Actualmente, también contamos con la participación de una estudiante, Pamela Bustamante, de la Pontificia Universidad Católica de Chile.

- Martine Labbé (ML): Del lado del centro Inria de la la Université de Lille, el equipo está compuesto por investigadores de alto nivel: Luce Brotcorne, Hélène Le Cadre, Frédéric Semet y por mí. 

Crédito

© Inria / Photo M. Magnin

¿Cómo se originó BIO-SEL? ¿Cómo empezaron a colaborar por primera vez?

- ML: Mantengo una larga colaboración con Fernando Ordóñez sobre problemas de optimización bi-nivel. Hemos codirigido a un estudiante de doctorado que ha trabajado en juegos de seguridad de Stackelberg. El programa de Equipos Asociados de Inria nos dio la posibilidad de oficializar esta fructífera colaboración y obtener fondos para apoyarla. Dado que había un interés común por ambas partes en estudiar problemas de logística, naturalmente hemos ampliado el alcance de nuestro proyecto en esta dirección.

¿Cuáles son las áreas específicas de investigación de cada uno de ustedes? ¿Qué preguntas científicas buscan responder o ya han respondido con el proyecto?

- VM: El equipo abarca un amplio espectro de intereses y temas. No es fácil separar los intereses individuales, ya que en realidad todos los temas se solapan. Podría decir que la interacción de distintos agentes y el estudio de la respuesta de cada uno de ellos a las acciones de los restantes podría ser una forma de describir lo que nos mantiene unidos. Esto podría significar que los juegos de seguridad, en los que un agente tiene que defender diferentes tipos de objetivos de los atacantes, sabiendo que existe la probabilidad de un ataque; y las acciones del propietario de una tienda para ganar el mayor mercado posible y sus acciones cuando los competidores podrían llegar más tarde para arrebatarle el mercado, son dos de los ejemplos de problemas que resolvemos.

Recientemente, hemos desarrollado formulaciones eficientes para algunas variantes del juego de seguridad de Stackelberg. También, consideramos un problema de optimización de la línea de productos al que se enfrenta una cadena minorista que posee múltiples tiendas. El método que desarrollamos para resolver este problema mejora el estado del arte.

¿Cuáles son los objetivos de BIO-SEL?

- VM: Uno de los objetivos es ayudar a comprender cómo tienen que actuar los defensores cuando existe la posibilidad de ataques, en contextos muy diferentes, y desarrollar herramientas matemáticas sólidas y eficientes para resolver estos problemas.  El segundo objetivo de esta fase del trabajo es estudiar el problema del surtido cuando un grupo de tiendas es propiedad de una empresa que quiere maximizar sus ventas, ya que el problema de surtido consiste en decidir qué productos deben exponerse en cada tienda.

- ML: Nuestro objetivo general es desarrollar métodos eficientes y escalables para problemas de optimización de dos niveles, en particular para algunos juegos de seguridad de Stackelberg y algunas aplicaciones en logística y energía.  A saber, cómo formular y resolver eficientemente un Stackelberg en el que existe un número exponencial de estrategias puras, lo que se aplica al caso en que hay un presupuesto limitado asignado a la seguridad de los objetivos. En logística, proseguimos nuestra colaboración en problemas de surtido y también iniciamos algunas investigaciones sobre la formación óptima de coaliciones para compradores.

Varios sitios web proponen productos cuyos precios dependen de la demanda, y los compradores pueden coordinarse para obtener mejores precios. Generalmente, existe una entidad central, el coordinador, que realiza la formación de coaliciones y distribuye los pagos a los jugadores. Consideramos el problema de Generación de Estructuras de Coalición (CSG) que se centra en la partición del conjunto de agentes en coaliciones mutuamente disjuntas, de tal manera que se maximice la recompensa total. Dado que se sabe que el problema CSG es NP-difícil, planeamos desarrollar modelos lineales enteros mixtos.

¿Cuáles son las aplicaciones específicas que podría tener o ha tenido BIO-SEL?

- VM: Ya que el objetivo es aplicar en problemas de logística y seguridad, se puede  destacar el patrullaje policial, surtido y formación de coaliciones de compradores.

- ML: Es aplicable en juego de seguridad, específicamente en prevención de ataques terroristas, control de aeropuertos, prevención de contrabando, etc. La variedad de productos y los precios son importantes estrategias de marketing.

¿Cómo se complementa el trabajo entre los equipos de Francia y Chile?

- VM: Naturalmente, cada científico tiene sus propias áreas de especialización, sin embargo nos hemos centrado en colaborar aportando cada una desde su especialidad, ya sea matemática o sobre aplicaciones. Yo diría que lo más importante ha sido la oportunidad de exponer a los estudiantes a diferentes grupos y culturas de trabajo.

- ML: Todos tenemos perfiles diferentes, ya sean más aplicados, más teóricos, orientados a algoritmos, etc. No obstante, opino que nuestros conocimientos están entrelazados. Este proyecto ha sido esencial para varios jóvenes investigadores, ya que les ha permitido realizar estancias de larga duración en el extranjero y han podido beneficiarse de los consejos de los otros miembros del equipo, así como sumergirse en la cultura de los demás durante un tiempo.