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

G-96-30

Étude comparative des algorithmes de flot maximum pour le problème des contours dans une mine à ciel ouvert

et

Cet article présente une étude comparative des algorithmes de flot maximum pour la résolution du problème de fermeture maximale sur un graphe. Plusieurs applications au problème de fermeture maximale sont connues dont particulièrement le problème des contours finaux d'une mine à ciel ouvert. Dans cet article, nous considérons des graphes provenant de cette application. Cet article expose les meilleurs algorithmes de flot maximum connus et propose des améliorations pratiques visant à réduire le temps de calcul sur les graphes de grande taille. Des expérimentations sur le problème des contours finaux sont présentées. Les résultats montrent que le problème des contours finaux sur un graphe présentant plus de 150 000 noeuds et 1500 000 arcs se résout en moins de 15 secondes CPU sur une machine HP9000/735.

, 19 pages

Ce cahier a été révisé en février 1997