Décomposition de Benders avec sous-problèmes entiers : coupes indicatrices basées sur la monotonie

La décomposition classique de Benders échoue lorsque le sous-problème est un programme mixte en nombres entiers, en raison de l’absence de dualité forte. Nous proposons une nouvelle classe de coupes indicatrices sans dualité, applicables à tous les problèmes décomposables par Benders dont le problème maître est en nombres entiers purs et les sous-problèmes sont des programmes linéaires mixtes en nombres entiers (MILP). Ces coupes sont dérivées de la propriété de monotonie de la fonction valeur du sous-problème, ce qui permet de construire des coupes valides sans recourir à la dualité.

Nous introduisons également un cadre théorique permettant de comparer l’efficacité de différentes coupes indicatrices. Ce cadre unifie plusieurs méthodes auparavant distinctes exploitant la monotonie des sous-problèmes. Deux formulations MILP des coupes proposées sont développées, ainsi que deux techniques d’implémentation visant à améliorer les performances computationnelles.

La méthode proposée est testée sur un problème de conception d’un système énergétique multiphase. Les résultats numériques montrent que les coupes indicatrices surpassent significativement CPLEX en temps de calcul et en qualité de solution, et que les performances observées sont cohérentes avec les prédictions théoriques.