Problème de sac à dos bi-dimensionnel bi-objectif en variables binaires : ensembles bornants et résolution exacte - Anthony Przybylski (LSNN - Université de Nantes)

Dans cette présentation, nous nous intéressons à la résolution exacte du problème de sac à dos bi-dimensionnel bi-objectif en variables binaires. Nous revenons dans un premier temps sur la relaxation surrogate afin de calculer des ensembles bornants supérieurs sur l’ensemble des points non-dominés de ce problème. Nous considérons en particulier une extension du problème dual-durrogate au cas bi-objectif proposée par Cerqueus et al. en 2015, et permettant l’obtention d’un ensemble bornant appelé « surrogate convexe optimal ». Nous proposons une nouvelle méthode afin de déterminer cet ensemble bornant, s’appuyant fortement sur un algorithme de résolution du problème dual-surrogate mono-objectif proposé par Fréville et Plateau en 1993. Nous utilisons ensuite cet ensemble bornant dans une méthode de résolution en deux phases, pour laquelle deux variantes sont considérées.