Problème de débit maximal avec des coûts par pièce
Cette question est une variante d'une question que j'ai postée plus tôt et corrige également quelques fautes de frappe dans le post précédent ( Complexity \ Reference request for variant of max flow problem ). Certains des changements sont mis en évidence en italiques gras et la principale différence réside dans la fonction objectif indiquée dans Eqn (\ ref {Eq: 1}).
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 non négatif prédéfini . L'objectif que nous souhaitons maximiser est donc$\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érez la variante dans laquelle le coût associé à l'utilisation de n'importe quel arc $(u,v)$ est plutôt donnée par le maximum ponctuel de deux fonctions linéaires:
$$\max{\left(\mathbf{c}_{uv}^{1} f_{uv} , \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)} \tag{1} \label{Eq:1}$$ où $\mathbf{b}_{uv}^{2} \leq 0$ est un nombre non positif prédéfini, et $\mathbf{c}_{uv}^{1}, \mathbf{c}_{uv}^{2} \geq 0$sont des nombres non négatifs prédéfinis . Comme avant$f_{uv}$ est le flux à travers l'arc $(u,v)$. Comme vous pouvez l'observer à partir de Eqn (\ ref {Eq: 1}), il peut exister une constante$\lambda \geq 0$tel que \ begin {équation} \ tag {2} \ label {Eq: 2} \ begin {cases} \ mathbf {c} _ {uv} ^ {1} f_ {uv} \ geq \ mathbf {c} _ { uv} ^ {2} f_ {uv} + \ mathbf {b} _ {uv} ^ {2}, \ text {if} f_ {uv} \ leq \ lambda \\ \ mathbf {c} _ {uv} ^ {1} f_ {uv} \ leq \ mathbf {c} _ {uv} ^ {2} f_ {uv} + \ mathbf {b} _ {uv} ^ {2}, \ text {sinon} \ end {cas } \ end {équation} A partir de l'Eqn (\ ref {Eq: 2}), nous pouvons observer que le coût d'utilisation d'un arc (peut) basculer (vers une fonction différente) en fonction du flux à travers l'arc s'il dépasse le seuil$\lambda$.
- La variante du problème de débit max (dont l'objectif est maintenant $\underset{(u, v) \in E}{\sum} \max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$ admettre une solution optimale calculable en temps polynomial?
- S'il n'est pas possible d'atteindre un maximum, existe-t-il une méthode efficace pour calculer le supremum du problème?
- Pouvez-vous m'indiquer des références?
PS Je sais que la variante que j'ai énoncée peut être 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.
Ma question précédente ( Complexity \ Reference request for variant of max flow problem ) était une tentative de simplifier le problème posté ici. Je republie une nouvelle question car la question précédente contenait des erreurs dans la description.
Réponses
Vous pouvez réécrire le problème de flux de coûts maximum avec objectif $$\underset{(u, v) \in E}{\sum} \max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$$ comme problème de flux de coût minimum avec objectif $$\underset{(u, v) \in E}{\sum} g_{uv}(f_{uv})$$ pour la fonction concave $g_{uv}(f_{uv}) = -\max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$.
Ce problème est connu sous le nom de problème de flux réseau à coût concave minimal (MCCNFP), qui est$\mathcal{NP}$-hard en général, selon cet article , par exemple. Bien sûr, il est toujours possible que votre variante spécifique soit plus facile.
Il y a beaucoup de littérature sur le MCCNFP, mais il semble que modéliser le problème comme un MILP et tester s'il résout dans un délai raisonnable est le début le plus simple.