Problème de fermeture - Closure problem
Dans la théorie des graphes et optimisation combinatoire , une fermeture d'un graphe orienté est un ensemble de sommets C , de telle sorte que aucune arête quittent C . Le problème de fermeture est la tâche de trouver la fermeture de poids maximum ou minimum dans un graphe orienté pondéré par les sommets. Il peut être résolu en temps polynomial en utilisant une réduction au problème de débit maximum . Il peut être utilisé pour modéliser divers problèmes d'application consistant à choisir un sous-ensemble optimal de tâches à effectuer, avec des dépendances entre des paires de tâches, un exemple étant dans l' exploitation à ciel ouvert .
Algorithmes
Condensation
La fermeture de poids maximum d'un graphe G donné est la même que le complément de la fermeture de poids minimum sur le graphe de transposition de G , donc les deux problèmes sont équivalents en complexité de calcul. Si deux sommets du graphe appartiennent au même composant fortement connexe , ils doivent se comporter de la même manière pour toutes les fermetures: il n'est pas possible pour une fermeture de contenir un sommet sans contenir l'autre. Pour cette raison, le graphe d'entrée d'un problème de fermeture peut être remplacé par sa condensation , dans laquelle chaque composant fortement connecté est remplacé par un seul sommet. La condensation est toujours un graphe acyclique dirigé .
Réduction au débit maximal
Comme l'a montré Picard (1976) , une fermeture de poids maximum peut être obtenue à partir de G en résolvant un problème d'écoulement maximum sur un graphe H construit à partir de G en y ajoutant deux sommets supplémentaires s et t . Pour chaque sommet v de poids positif dans G , le graphe augmenté H contient une arête de s à v de capacité égale au poids de v , et pour chaque sommet v de poids négatif dans G , le graphe augmenté H contient une arête de v à t dont la capacité est la négation du poids de v . Toutes les arêtes de G sont donnés capacité infinie en H .
Une coupe minimale séparant s de t dans ce graphique ne peut avoir aucune arête de G passant dans le sens avant à travers la coupe: une coupe avec une telle arête aurait une capacité infinie et ne serait pas minimale. Par conséquent, l'ensemble des sommets sur le même côté de la découpe en tant que s forme automatiquement une fermeture C . La capacité de la coupe est égale au poids de tous les sommets de poids positif moins le poids des sommets en C , qui est minimisé lorsque le poids de C est maximisé. Par le théorème de coupe minimale de débit maximal , une coupe minimale et la fermeture optimale qui en dérive peuvent être trouvées en résolvant un problème de débit maximal.
Algorithmes alternatifs
Des algorithmes alternatifs pour le problème de fermeture maximale qui ne calculent pas de flux ont également été étudiés. Leur durée de fonctionnement est similaire à celle des algorithmes de flux connus les plus rapides.
Applications
L'exploitation minière à ciel ouvert
Une mine à ciel ouvert peut être modélisée comme un ensemble de blocs de matériaux qui peuvent être enlevés en la minant une fois que tous les blocs directement au-dessus ont été enlevés. Un bloc a une valeur totale, égale à la valeur des minéraux qui peuvent en être extraits moins le coût d'enlèvement et d'extraction; dans certains cas, un bloc n'a pas de valeur d'extraction mais doit quand même être supprimé pour atteindre d'autres blocs, ce qui lui donne une valeur négative. On peut définir un réseau acyclique qui a comme sommets les blocs d'une mine, avec une arête de chaque bloc aux blocs au-dessus de lui qui doit être supprimée avant elle. Le poids de chaque sommet de ce réseau est la valeur totale de son bloc, et le plan le plus rentable pour l'exploitation minière peut être déterminé en trouvant une fermeture de poids maximum, puis en formant un ordre topologique des blocs dans cette fermeture.
Ciblage militaire
Dans les opérations militaires, les cibles de grande valeur telles que les centres de commandement sont fréquemment protégées par des couches de systèmes de défense, qui peuvent à leur tour être protégées par d'autres systèmes. Afin d'atteindre une cible, toutes ses défenses doivent être abattues, ce qui en fait une cible secondaire. Chaque cible a besoin d'une certaine quantité de ressources pour lui être allouée afin de réussir une attaque. L'ensemble optimal de cibles à attaquer, pour obtenir le maximum de valeur pour les ressources dépensées, peut être modélisé comme un problème de fermeture.
Conception du réseau de transport
Le problème de la planification d'un système de livraison de fret peut être modélisé par un réseau dans lequel les sommets représentent des villes et les bords (non dirigés) représentent des itinéraires potentiels de livraison de fret entre des paires de villes. Chaque itinéraire peut réaliser un certain bénéfice, mais ne peut être utilisé que si des dépôts de fret sont construits à ses deux extrémités, avec un certain coût. Le problème de la conception d'un réseau qui maximise la différence entre les bénéfices et les coûts peut être résolu comme un problème de fermeture, en subdivisant chaque bord non dirigé en deux bords dirigés, tous deux dirigés vers l'extérieur à partir du point de subdivision. Le poids de chaque point de subdivision est un nombre positif, le bénéfice de l'itinéraire correspondant, et le poids de chaque sommet du graphe d'origine est un nombre négatif, le coût de construction d'un dépôt dans cette ville. Avec l'exploitation à ciel ouvert, c'était l'une des applications motivantes originales pour étudier le problème de fermeture; il a été étudié à l'origine en 1970, dans deux articles indépendants publiés dans le même numéro de la même revue par JMW Rhys et Michel Balinski .
Planification des tâches
Sidney (1975) et Lawler (1978) décrivent une application du problème de fermeture à une version de la planification des ateliers de travail dans laquelle on se voit attribuer un ensemble de tâches à exécuter, une à la fois. Chaque tâche est associée à deux nombres: un poids ou une priorité, et un temps de traitement, le temps qu'il faut pour effectuer cette tâche. De plus les tâches ont des contraintes de précédence: certaines tâches doivent être effectuées avant d'autres. Ces contraintes de précédence peuvent être décrites par un graphe acyclique dirigé G dans lequel une arête d'une tâche à une autre indique que la première tâche doit être exécutée avant la seconde. Le but est de choisir un ordre qui est cohérent avec ces contraintes (un ordre topologique de G ) qui minimise le temps total pondéré de réalisation des tâches.
Bien que (comme le montre Lawler) ce problème d'ordonnancement soit NP-complet en général, Sidney décrit une méthode de décomposition qui peut aider à résoudre le problème en le réduisant à plusieurs problèmes plus petits du même type. En particulier, si S est un sous-ensemble des tâches qui (parmi tous les sous-ensembles) a le plus grand rapport possible entre son poids total et son temps de traitement total, et de plus S est minimal parmi tous les ensembles avec le même rapport, alors il existe un calendrier optimal dans lequel toutes les tâches en S sont exécutées avant toutes les autres tâches. Tant que S n'est pas l'ensemble des tâches, cette partition des tâches divise le problème d'ordonnancement en deux problèmes plus petits, l'un d'ordonnancement S et l'autre d'ordonnancement des tâches restantes. Bien que S soit une fermeture (pour un graphique avec des arêtes inversées à partir de G ), le problème de trouver S n'est pas exactement un problème de fermeture de poids maximum, car la valeur de S est un rapport plutôt qu'une somme de poids. Néanmoins, Lawler montre que S peut être trouvé en temps polynomial par un algorithme de recherche binaire dans lequel chaque étape de la recherche utilise une instance du problème de fermeture comme sous-programme.