Parça bazında maliyetlerle maksimum akış sorunu

Question

Bu soru, daha önce göndermiş olduğum bir sorunun bir çeşididir ve aynı zamanda önceki gönderideki bazı yazım hatalarını da düzeltir ( Karmaşıklık \ Maksimum akış sorununun varyantı için referans isteği ). Değişikliklerden bazıları kalın italik olarak vurgulanmıştır ve temel fark, Eşitlik (\ ref {Eq: 1}) 'de gösterilen amaç işlevindedir.

Ark kapasiteleri ile standart maksimum maliyet akışı probleminde, ark kullanmanın maliyeti ark boyunca akışla orantılıdır. Örneğin, eğer$f_{uv}$ ark boyunca akış $(u,v)$, daha sonra bu yayı kullanmanın maliyeti şu şekilde verilir: $\mathbf{c}_{uv} f_{uv}$, nerede $\mathbf{c}_{uv}$önceden tanımlanmış negatif olmayan bir sayıdır. Dolayısıyla, maksimize etmekle ilgilendiğimiz hedef,$\underset{(u, v) \in E}{\sum} \mathbf{c}_{uv} f_{uv}$, nerede $E$grafikteki kenarlardır. Grafiğin bir kaynak ve bir havuz düğümü içerdiğini ve tüm akışların kaynaktan yayıldığını ve havuz düğümüne aktığını varsayabilirsiniz.

Herhangi bir ark kullanımıyla ilişkili maliyetin hangi varyantta olduğunu düşünün $(u,v)$ bunun yerine noktasal maksimum iki doğrusal fonksiyon tarafından verilir:

$$\max{\left(\mathbf{c}_{uv}^{1} f_{uv} , \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)} \tag{1} \label{Eq:1}$$ nerede $\mathbf{b}_{uv}^{2} \leq 0$ önceden tanımlanmış pozitif olmayan bir sayıdır ve $\mathbf{c}_{uv}^{1}, \mathbf{c}_{uv}^{2} \geq 0$önceden tanımlanmış, negatif olmayan sayılardır . Eskisi gibi$f_{uv}$ ark boyunca akış $(u,v)$. Eşitlik (\ ref {Eq: 1}) 'den gözlemleyebileceğiniz gibi, bazı sabitler olabilir.$\lambda \geq 0$öyle ki \ start {equation} \ tag {2} \ label {Eq: 2} \ begin {case} \ 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 {aksi halde} \ end {case } \ end {equation} Denklem (\ ref {Eq: 2}) 'den, bir yay (may) anahtarı (farklı bir işleve) kullanmanın maliyetinin, eşiği aşması durumunda yay boyunca akışa bağlı olduğunu gözlemleyebiliriz.$\lambda$.

1. Maksimum akış probleminin varyantı mı (şimdi hedefi $\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)}$ polinom zamanlı hesaplanabilir optimal çözümü kabul ediyor musunuz?
2. Bir maksimum elde edilemiyorsa, problem için üstünlüğü hesaplamanın etkili bir yöntemi var mı?
3. Beni gösterebileceğin referanslar var mı?

Not: Belirtmiş olduğum varyantın bir MILP olarak sunulabileceğini biliyorum, ancak bu sorunun yapısal sonuçlarını ve karmaşıklığını öğrenmekle ilgileniyorum.

Önceki sorum ( Karmaşıklık \ Maksimum akış sorununun varyantı için referans isteği ), burada yayınlanan sorunu basitleştirme girişimiydi. Önceki soru açıklamada hatalar içerdiği için yeni bir soruyu yeniden gönderiyorum.

Answer 1

Maksimum maliyet akışı problemini objektif olarak yeniden yazabilirsiniz $$\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)}$$ asgari maliyet akışı sorunu olarak $$\underset{(u, v) \in E}{\sum} g_{uv}(f_{uv})$$ içbükey işlev için $g_{uv}(f_{uv}) = -\max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$.

Bu sorun, minimum içbükey maliyetli ağ akış sorunu (MCCNFP) olarak bilinir.$\mathcal{NP}$-örneğin bu makaleye göre genel olarak zor . Elbette, belirli varyantınızın daha kolay olması hala mümkündür.

MCCNFP ile ilgili pek çok literatür var, ancak sorunun bir MILP olarak modellenmesi ve makul bir sürede çözülüp çözülmediğinin test edilmesi en basit başlangıç ​​gibi görünüyor.