Masalah aliran maksimum dengan biaya potongan

Aug 19 2020

Pertanyaan ini adalah varian dari pertanyaan yang saya posting sebelumnya dan juga memperbaiki beberapa kesalahan ketik di posting sebelumnya ( Permintaan Kompleksitas \ Referensi untuk varian masalah aliran maks ). Beberapa perubahan disorot dalam huruf miring tebal dan perbedaan utamanya adalah pada fungsi tujuan yang ditunjukkan dalam Persamaan (\ ref {Persamaan: 1}).

Dalam masalah aliran biaya maks standar dengan kapasitas busur, biaya menggunakan busur sebanding dengan aliran melalui busur. Misalnya, jika$f_{uv}$ adalah aliran melalui busur $(u,v)$, maka biaya menggunakan busur ini diberikan oleh $\mathbf{c}_{uv} f_{uv}$, dimana $\mathbf{c}_{uv}$adalah beberapa bilangan non-negatif yang telah ditentukan sebelumnya . Jadi tujuan yang ingin kami maksimalkan adalah$\underset{(u, v) \in E}{\sum} \mathbf{c}_{uv} f_{uv}$, dimana $E$adalah tepi dalam grafik. Anda dapat berasumsi bahwa grafik berisi sumber dan node sink, dan semua aliran berasal dari sumber dan mengalir ke node sink.

Pertimbangkan varian di mana biaya terkait dengan penggunaan busur apa pun $(u,v)$ sebagai gantinya diberikan oleh maksimum runcing dari dua fungsi linier:

$$\max{\left(\mathbf{c}_{uv}^{1} f_{uv} , \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)} \tag{1} \label{Eq:1}$$ dimana $\mathbf{b}_{uv}^{2} \leq 0$ adalah bilangan non-positif yang telah ditentukan sebelumnya, dan $\mathbf{c}_{uv}^{1}, \mathbf{c}_{uv}^{2} \geq 0$adalah bilangan non-negatif yang telah ditentukan sebelumnya . Seperti sebelumnya$f_{uv}$ adalah aliran melalui busur $(u,v)$. Seperti yang dapat Anda amati dari Persamaan (\ ref {Persamaan: 1}), mungkin ada beberapa konstanta$\lambda \geq 0$sedemikian rupa sehingga \ begin {persamaan} \ tag {2} \ label {Persamaan: 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 {jika tidak} \ end {case } \ end {persamaan} Dari Persamaan (\ ref {Persamaan: 2}), kita dapat mengamati bahwa biaya menggunakan sakelar busur (mungkin) (ke fungsi yang berbeda) berdasarkan aliran melalui busur jika melebihi ambang batas$\lambda$.

  1. Apakah varian dari masalah aliran maks (yang tujuannya sekarang adalah $\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)}$ mengakui solusi optimal yang dapat dihitung waktu polinomial?
  2. Jika maksimum tidak dapat dicapai, apakah ada metode yang efisien untuk menghitung supremum untuk masalah tersebut?
  3. Apakah ada referensi yang bisa Anda tunjukkan?

PS Saya tahu bahwa varian yang saya nyatakan dapat dianggap sebagai MILP, namun saya tertarik untuk mempelajari tentang hasil struktural dan kompleksitas masalah ini.

Pertanyaan saya sebelumnya ( Permintaan Kompleksitas \ Referensi untuk varian masalah aliran maks ) adalah upaya untuk menyederhanakan masalah yang diposting di sini. Saya memposting ulang pertanyaan baru karena pertanyaan sebelumnya berisi kesalahan dalam deskripsi.

Jawaban

3 KevinDalmeijer Aug 19 2020 at 07:56

Anda dapat menulis ulang masalah arus biaya maksimum dengan objektif $$\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)}$$ sebagai masalah arus biaya minimum dengan tujuan $$\underset{(u, v) \in E}{\sum} g_{uv}(f_{uv})$$ untuk fungsi cekung $g_{uv}(f_{uv}) = -\max{\left(\mathbf{c}_{uv}^{1} f_{uv}, \mathbf{c}_{uv}^{2} f_{uv} + \mathbf{b}_{uv}^{2}\right)}$.

Masalah ini dikenal sebagai masalah aliran jaringan biaya cekung minimum (MCCNFP), yaitu$\mathcal{NP}$-hard pada umumnya, menurut makalah ini , misalnya. Tentu saja, varian spesifik Anda masih mungkin lebih mudah.

Ada banyak literatur tentang MCCNFP, tetapi tampaknya memodelkan masalah sebagai MILP dan menguji apakah dapat diselesaikan dalam waktu yang wajar adalah permulaan yang paling mudah.