Solutions intégrales au problème de circulation

Question

Supposons que nous ayons un problème de circulation (avec un seul produit), où toutes les limites inférieures, supérieures et les coûts sont des entiers. Sommes-nous garantis que s'il y a une solution, alors il y a une solution intégrale? Existe-t-il un algorithme qui peut en trouver un en temps polynomial?

Pour un flux réseau standard, nous savons qu'il existe un flux maximum intégral, et il existe des algorithmes en temps polynomial qui peuvent trouver un tel flux intégral. Je me demande si la même chose est vraie pour les problèmes de circulation, qui sont une généralisation du débit maximal.

Answer 1

Les problèmes de circulation ne sont pas seulement une généralisation du débit maximal, il y a aussi une réduction à l'envers. Supposons que nous ayons un graphe orienté$G = (V, E)$ avec des coûts de pointe, des capacités et des limites inférieures.

Tout bord $u \to v$ dans $G$ avec on peut remplacer par deux nœuds $s, t$ et deux bords $s \to v$ et $u \to t$où l'un des bords a le coût d'origine, les capacités et les limites inférieures et l'autre est gratuit et illimité. Appelez ce graphique$G'(e)$, où $e = u\to v$ est le bord qui a été remplacé.

Ensuite, si un flux avec un certain coût existe dans $G'(\cdot)$, il doit aussi exister en tant que circulation en $G$avec le même coût. Vice versa, si une diffusion existe en$G$ et il utilise le bord $u \to v$, alors ce flux existe également dans $G'(u\to v)$ avec le même coût.

Par conséquent, pour résoudre le problème de circulation, nous pouvons choisir un bord arbitraire $e$, calculer $G'(e)$et utilisez un algorithme de flux réseau traditionnel pour trouver le flux optimal. Selon les arguments traditionnels, ce flux optimal est intégral. Nous choisissons ensuite un autre bord (en évitant les bords qui faisaient partie d'un flux optimal précédent) et répétons, en conservant la meilleure solution, jusqu'à ce qu'il ne reste plus de bords inconnus.

Puisque dans le pire des cas, cela ajoute un facteur de $|E|$à la complexité de la complexité polynomiale, c'est encore polynomial. Et bien sûr, l'optimum de tous les flux intégraux trouvés est lui-même intégral.

Pour gérer les limites inférieures sur les bords de $G'$, on peut soit noter que la matrice de contraintes de programmation linéaire est unimodulaire (voir ces notes de cours du MIT ), d'où il résulte qu'il existe une solution intégrale s'il y a une solution; ou on peut utiliser une réduction standard pour éliminer les bornes inférieures (voir, par exemple, Ahuja et al, Network Flows , page 39) et ensuite résoudre avec un algorithme standard pour le flux de réseau.