Complexité \ Demande de référence pour la variante du problème de débit maximal

Question

Dans le problème de flux de coût maximum standard avec des capacités d'arc, le coût d'utilisation d'un arc est proportionnel au flux à travers l'arc. Par exemple, si$f_{uv}$ est le flux à travers l'arc $(u,v)$, alors le coût d'utilisation de cet arc est donné par $\mathbf{c}_{uv} f_{uv}$, où $\mathbf{c}_{uv}$est un nombre réel prédéfini. Donc, l'objectif que nous voulons maximiser est$\underset{(u, v) \in E}{\sum} \mathbf{c}_{uv} f_{uv}$, où $E$représente les arêtes du graphique. Vous pouvez supposer que le graphe contient une source et un nœud récepteur, et que tous les flux émanent de la source et se drainent dans le nœud récepteur.

Considérons la variante dans laquelle le coût associé à l'utilisation de l'arc $(u,v)$est à la place donné par: \ begin {cases} \ mathbf {c} _ {uv} f_ {uv} + \ mathbf {b} _ {uv}, \ text {if} f_ {uv}> 0, \\ 0, \ text {sinon} \ end {cas} où$\mathbf{b}_{uv}$ est un nombre positif prédéfini.

1. La variante du problème de débit maximal admet-elle une solution en temps polynomial?
2. Si non, y a-t-il des références auxquelles vous pouvez me référer?

PS Je sais que la variante que j'ai énoncée peut être facilement posée comme un MILP, cependant, je suis intéressé à en savoir plus sur les résultats structurels et la complexité de ce problème.

Answer 1

je suppose qu'il n'existe même pas de solution optimale.

Tu veux avoir $\epsilon$- circuler sur chaque bord pour collecter tous les coûts $b_{uv}$. D'autre part, vous souhaitez maximiser le flux sur les bords avec le coût le plus élevé$c_{uv}$. Cela conduit à la pression d'avoir$\epsilon$ aussi petit que possible, tout en restant $\epsilon > 0$. Un tel$\epsilon$ ne peut pas exister.