Thesis of Luis Alberto Salazar Zendeja

Modèles et algorithmes pour le problème d'interdiction de l'arbre couvrant de poids minimal

La prévention est un aspect important pour tout système pour en assurer le bon fonctionnement. Les transports, les livraisons ou la production sont des processus où la prévention joue un rôle essentiel. Les catastrophes naturelles et les perturbations causées par l'homme sont des exemples de ce qui peut provoquer un dysfonctionnement de ces systèmes, ce qui, dans la plupart des cas, conduit à un fonctionnement indésirable, voire à l'absence totale de fonctionnement. La modélisation de ces situations dans le cadre d'un Jeu d'Interdiction (JI) est l'un des moyens les plus pratiques de garantir les meilleurs résultats. Un JI implique deux entités non coopératives qui interagissent l'une avec l'autre. La première entité, appelée l'interdicteur, cherche à perturber les processus d'optimisation ou les paramètres de la seconde entité, appelée le défenseur. L'interdicteur agit en premier, puis le défenseur réagit en toute connaissance des actions de l'interdicteur. L'interdicteur peut modifier les ressources du défenseur voire les détruire afin d'aggraver l'objectif du défenseur. Le problème de l'Interdiction de l'Arbre Couvrant Minimal (IACM) est le JI traité dans cette thèse. Dans cette problème, l'interdicteur cherche à allouer ses ressources dans le but de modifier la topologie du réseau dans lequel le défenseur calcule l'Arbre Couvrant Minimal (ACM) de façon à ce que le poids de ce dernier subisse le plus grand incrément. L'interdicteur est limité par une contrainte budgétaire. La contrainte budgétaire peut être définie comme une contrainte de cardinalité, le coût d'interdiction de chaque arête étant alors égal, ou comme contrainte de sac à dos, les coûts d'interdiction étant différents. Le travail présenté dans cette thèse est structuré comme suit. Une revue de la littérature du IACM et de deux autres problèmes d'interdiction est présentée au chapitre 2. Le chapitre 3 présente sept modèles mathématiques pour le problème IACM. Une première formulation venant de la littérature est rappelée. Un deuxième modèle original basé sur une formulation linéaire du problème ACM est présenté. De plus, des inégalités valides sont développées pour renforcer le modèle. Deux formulations supplémentaires sont proposées. Elles sont obtenues grâce à la théorie de dualité. Toutes les formulations traitent les deux types d'interdiction. Un dernier modèle qui ne considère que le cas d'interdiction totale est présenté. Des instances sont générées comparer les efficacités de nos formulations. Le problème IACM est ensuite résolu par un algorithme de Branch-and-Price dans le chapitre 4. La formulation la plus compacte définie au chapitre 3 est utilisée pour définir le problème maître restreint et le problème de pricing. Une famille de contraintes qui excluent les stratégies d'interdiction non pertinentes est développée et ajoutée au problème de pricing. Ensuite, un algorithme de génération de colonnes intégré dans un schéma Branch-and-Bound est présenté. Les expériences numériques sont réalisées sur l'ensemble d'instances générées au chapitre 3. Un algorithme de décomposition de Benders est développé pour traiter le problème IACM. Le problème IACM est décomposé en un Problème Maître (PM) et un sous-problème. Une famille de contraintes pour le PM, appelée contraintes d'optimalité, est introduite et liftée. Une famille d'inégalités valides est également proposée pour renforcer la relaxation linéaire du PM. Le sous-problème, paramétré par la solution du PM, consiste uniquement en la détermination d'un ACM. L'algorithme de décomposition de Benders est implémenté à l'aide d'un solveur commercial. Quatre types d'instances sont générés. L'algorithme est évalué pour chacune des quatre configurations possibles en fonction du type d'interdiction et des contraintes budgétaires. Le manuscrit se termine au chapitre 6 par les conclusions générales de la thèse. Les limites et les travaux futurs sont également discutés.

Jury

M. Frédéric SEMET Centrale Lille Institut Directeur de thèse Mme Martine LABBé Université Libre de Bruxelles Co-directrice de thèse Mme Carmen GALé POLA Universidad de Zaragoza Examinatrice Mme Yasmín Águeda RíOS SOLíS Tecnológico de Monterrey Rapporteure M. François CLAUTIAUX Université de Bordeaux Rapporteur M. Diego CATTARUZZA École Centrale de Lille Examinateur Mme Safia KEDAD-SIDHOUM Conservatoire National des Arts et des Métiers Examinatrice

Thesis of the team INOCS defended on 28/11/2022