Groupe d’études et de recherche en analyse des décisions

Simplex en nombres entiers pour les problèmes de partitionnement

Abdelouahab Zaghrouti

Depuis les années 70s, plusieurs chercheurs ont étudié la structure du polytope du problème de partitionnement et ont proposé des adaptations de l'algorithme du simplexe pour trouver une solution optimale à partir d'une suite de solutions entières. Mais, à cause de la dégénérescence, il est difficile de trouver les termes de la suite. La méthode de «décomposition» utilise des idées d'IPS (improved primal simplex) pour traiter efficacement la dégénérescence. En résolvant itérativement des sous-problèmes, elle permet de trouver le prochain terme de la suite en n'effectuant que des pivots entiers positifs.

Nous vous remercions de confirmer votre présence.