Institut Fayol – Mines St Etienne

Séminaire des Doctorants du LIMOS : problème BSTP (Bi-objective Spanning Tree Problem)

Une nouvelle session du séminaire des doctorants du LIMOS a eu lieu la semaine dernière. L’occasion d’écouter, Thanh Loan NGUYEN, actuellement en troisième année de thèse, qui a présenté ses travaux de recherche sur une méthode innovante pour résoudre le problème BSTP (Bi-objective Spanning Tree Problem) en utilisant une approche basée sur les solutions de Kalai-Smorodinsky.

Sujet : Les Solutions de Kalai-Smorodinsky pour le Problème d’Arbre de Recouvrement Bi-objectif

Résumé : Ce travail s’est penché sur le Problème d’Arbre de Recouvrement Bi-objectif (BSTP), une extension du problème classique de l’Arbre de Recouvrement Minimum, ayant de nombreuses applications diverses. Dans ce problème, chaque arête d’un graphe donné est associée à deux poids distincts, et l’objectif était de trouver un arbre de recouvrement qui minimise simultanément les deux poids totaux.

Topic: On the Kalai-Smorodinsky solutions for Bi-objective Spanning Tree Problem

Abstract: This work investigates the Bi-objective Spanning Tree Problem (BSTP), an extension of the classical Minimum Spanning Tree problem with diverse applications. In this problem, each edge of a given graph is associated with two distinct weights, and the objective is to find a spanning tree that simultaneously minimizes the two total weights. As a specific case of bi-objective optimization, we may be interested in enumerating all the Pareto-optimal solutions of BSTP. However, as the number of Pareto-optimal solutions may be exponential, all the existing approaches to enumerate efficient solutions cannot achieve a polynomial CPU time. In this talk, we propose a novel approach for finding preferred efficient solutions where the worst of the ratios of the two objective values to their maximum possible values, respectively, is the minimum. This approach is based on the Kalai-Smorodinsky (KS) solution, a well-known concept in cooperative game theory. More precisely, we consider an extension of the KS solution concept to the discrete case that can be found by optimizing convex combinations of two objectives. We first characterize the properties of such KS solution(s) for the BSTP. Next, we present a weakly polynomial time algorithm for finding the KS solution(s) for the BSTP. Finally, we showcase the computational results in some instances and discuss the results. Beyond the particular case of the BSTP, this paper offers an efficient and explainable approach for solving bi-objective combinatorial optimization problems.  

Les Séminaires des Doctorants LIMOS

Sur le plan pratique, les « Séminaires des Doctorants » sont organisés par et pour les doctorants du LIMOS. Le but est d’apprendre, d’échanger et de débattre autour de courtes présentations sur les différents aspects des sciences informatiques. Le second objectif est de fédérer les doctorants du LIMOS autour d’une rencontre régulière afin de savoir un peu mieux ‘qui fait quoi’ entre les murs du labo.

Les présentations proposées sont destinées à un public académique et doivent avoir un lien fort avec l’informatique. Le séminaire peut également permettre aux doctorants de présenter leurs résultats à d’autres membres du labo, de s’entrainer avant une présentation à une conférence, ou de répéter leur soutenance de thèse.

Sur le plan de la valorisation, la présence des doctorants à cinq séminaires labo et une présentation au Séminaire des Doctorants validera un module de la formation doctorale ED SIS.

#LIMOS

Commentaires Clos.