Les contraintes de capacités arrondies sont principalement connues dans le CVRP (Capacitated Vehicle Routing Problem). Pour rappel, le CVRP consiste à déterminer des tournées de véhicules permettant des quantités données de produits à un ensemble de clients, et ce, en tenant compte de la capacité limitée du véhicule. Les contraintes capacité arrondies modélisent le nombre d’arêtes minimum dans l’arête devant exister entre un groupe quelconque de clients et le dépôt des véhicules, dans une solution réalisable du CVRP. D’un point de vu pratique, ces contraintes se sont avérées efficaces pour résoudre le CVRP. D’autres problèmes d’optimisation combinatoire font intervenir des contraintes similaires.

Etant donné qu’elles apparaissent en nombre exponentiel dans les formulations mathématiques, leur utilisation dans un algorithme de type Branch-and-Cut nécessite de résoudre le problème dit de séparation qui leur est associé. Même si l’importance de ces contraintes est désormais reconnue, la complexité théorique du problème de séparation des contraintes de capacité arrondies est resté inconnue pendant des décennies.

Dans cet exposé, nous démontrons que le problème de séparation associé aux contraintes de capacité arrondie est NP-difficile. Nous explorons aussi des cas où le problème peut être résolu en temps polynomial et discutons des conséquences de ces résultats.

Les divers résultats que nous présenterons s’appuient sur l’introduction de nouvelles classes de problèmes ainsi que sur l’exploitation de fonction sous-modulaires particulières. 

Retour page d'accueil du séminaire