Perilaku seperti XOR dalam jaringan aliran

XOR bukan nama yang tepat, tetapi saya mencari semacam perilaku eksklusif.

Saat ini saya sedang memecahkan serangkaian masalah (penugasan) yang berbeda dengan memodelkan jaringan aliran dan menjalankan algoritma min-cost-max-flow. Jaringan aliran sangat berguna karena banyak masalah dapat dikurangi menjadi mereka dengan cara yang mudah dan dapat dimengerti. Dalam kasus saya ini adalah pencocokan dengan beberapa kendala tambahan. Karena kendala-kendala ini semakin kompleks, saya bertanya-tanya apakah ada konstruksi yang ada untuk memodelkan perilaku tertentu.

Dalam hal ini saya ingin membatasi aliran keluar node ke satu tepi.

Diberikan grafik , kapasitas integral dan biaya . Node sewenang-wenang disebut . Tetangga langsungnya disebut . Bisakah kita mengganti tepi (merah) dengan beberapa konstruksi sehingga hanya satu sisi yang dapat menerima aliran ? Yang berarti bahwa jika mendapat aliran (mis. ) tidak ada tepi (merah) lainnya yang dapat menerima aliran.$G=(V, E)$$c(u,v)$$k(u,v)$$A$$B_1, ..B_n$$AB_1,...AB_n$$AB_1$$5/10$

Kita dapat menambahkan node / tepi perantara dan bermain dengan biaya dan kapasitas. Total kapasitas konstruksi baru kami harus tetap sama dan biaya berbagai alternatif harus tetap proporsional.

Jadi pertanyaan saya adalah:

1. Apakah ada konstruksi seperti ini secara umum? (Kata kunci, tautan, makalah apa saja)
2. Bisakah Anda menyarankan solusi untuk masalah spesifik saya?

Secara umum, jawabannya adalah tidak. Jika kita menempatkan batasan seperti XOR pada tepi verteks yang keluar, kita dapat membuktikan bahwa menemukan min-cut-max-flow adalah NP-Hard. Tekniknya adalah mengurangi 3-SAT.

Anggaplah ada variabel dalam klausa 3-SAT dan . Kami membuat grafik mengkodekan instance dari masalah 3-SAT. Untuk setiap variabel , kita membuat simpul terhubung ke sumber dengan tepi kapasitas. Dua simpul lagi , yang terhubung ke , dibuat untuk mewakili mengambil nilai 0 atau 1 juga dengan tepi kapasitas .$n$$x_1, x_2, ..., x_n$$m$$c_1, c_2, ..., c_m$$G(V,E)$$x_i$$v_i$$s$$\infty$$u_i, w_i$$v_i$$x_i$$\infty$

Untuk setiap klausa , kita membuat simpul terkait dengannya dan terhubung ke variabel atau negasinya dalam klausa dengan tepi kapasitas . Misalnya, jika , kami menghubungkannya ke dengan tepi kapasitas. Semua terhubung ke wastafel dengan tepi kapasitas 1.$c_i$$o_i \in G$$o_i$$1$$c_i = (x_3 \lor x_4 \lor \neg x_5)$$u_3, u_4, w_5$$o_i$

Karena dan tidak dapat mengambil nilai yang sama, kami menempatkan batasan XOR di tepian , , . Dapat dibuktikan bahwa ada aliran maksimum ukuran jika dan hanya jika instance 3-SAT memuaskan. Karena masalahnya sepele dalam dan pengurangannya jumlahnya banyak, kami menyimpulkan versi keputusan aliran jaringan pembatasan XOR adalah NP-Lengkap.$x_i$$\neg x_i$$(v_i, u_i)$$(v_i, w_i)$$\forall i = 1,2,3,...,n$$m$$NP$

Untuk pertanyaan pertama Anda, saya tidak tahu teknik umum atau aturan praktis yang dapat Anda gunakan untuk memodelkan pembatasan sewenang-wenang dalam jaringan aliran. Kebanyakan contoh yang saya lihat umumnya didasarkan pada beberapa intuisi tentang sifat pembatasan, dan seringkali pada awalnya tampak sewenang-wenang.

Untuk kasus khusus Anda, saya belum sampai pada pemetaan yang baik untuk max-flow. Namun, saya dapat menyarankan solusi alternatif sederhana (Anda mungkin sudah tahu itu): Kedalaman Pencarian Pertama dari sumber$s$.

Karena aliran dibatasi hanya untuk satu tepi keluar untuk setiap titik, apa yang Anda miliki adalah jalur dari sumber ke target. Jalur ini memenuhi dua properti yang dapat membawa aliran maksimum di antara jalur lain dari sumber$s$ untuk menargetkan $t$, dan memiliki biaya terendah di antara semua jalur yang dapat membawa aliran yang sama $s$ untuk $t$.

• Mulai DFS dari $s$
• Saat Anda menuruni DFS, pantau kapasitas minimum saat ini dari semua sisi yang ditemui sejauh ini.
• Juga melacak biaya total saat ini (panjang jalur) yang ditemui sejauh ini.
• Jika $t$ tercapai selama DFS, bandingkan dua nilai ini dengan nilai global, dan perbarui nilai global jika perlu.
• Mundur dari $t$ dan lanjutkan dengan DFS.

Pada dasarnya, Anda menyebutkan semua jalur dari $s$ untuk $t$menggunakan DFS, dan pilih yang memenuhi kriteria min-cost dan max-flow Anda. DFS itu sendiri mengambil$O(|E|)$ waktu, yang lebih efisien daripada algoritma aliran maks.

Untuk membangun pada jawaban Paresh, jika semua kapasitas maks adalah satu (dan semua yang lain adalah bilangan bulat), Anda juga dapat membagi setiap simpul menjadi dua sehingga simpul (n-) memiliki semua tepi, simpul (n +) memiliki semua yang keluar edge, dan (n-) dan (n +) terhubung dengan edge of max capacity 1. Pecahkan jaringan min-cost baru ini dan Anda selesai.

Jika kapasitas maks tidak semuanya satu, maka masalahnya lebih sulit. Anda dapat merumuskan masalah sebagai MIP (Program Integer Campuran). Satu-satunya batasan integer adalah batasan XOR.

Untungnya, ini dapat dimodelkan sebagai Set Pesanan Khusus - tipe SOS1 (lihat http://en.wikipedia.org/wiki/Special_ordered_set ). Sebagian besar pemecah MIP secara khusus mewakili kendala SOS1 dan akan menanganinya dengan lebih efisien (kadang-kadang Anda perlu mengatakannya, kadang-kadang akan mengatasinya - periksa dokumen solver Anda).

Meskipun MIP pada akhirnya akan menyatu ke jawaban optimal, untuk model yang sangat besar, Anda mungkin tidak punya waktu untuk menunggu sampai selesai. Mendapatkan MIP besar untuk bertemu seringkali lebih merupakan seni daripada rekayasa.

Saran berikutnya adalah lebih banyak pekerjaan. Anda dapat menggunakan pemecah jaringan biaya-min sebagai subrutin dan apakah Anda memiliki percabangan di tepi XOR menggunakan teknik SOS1. Sebagai contoh, pada setiap cabang, matikan 1/2 tepi yang paling jarang digunakan, selesaikan jaringan biaya minimum (sangat cepat), ulangi sampai semua kendala XOR terpenuhi.

Anda dapat memprioritaskan urutan percabangan dengan kriteria Anda sendiri (volume aliran, biaya volume X, kapasitas yang dipesan, jumlah sisi yang mungkin, dll.). Dengan memandu pencarian sendiri, Anda dapat mengasah bagian-bagian dari solusi yang paling penting bagi Anda.

Anda tidak menunjukkan apakah Anda selalu tahu apakah masalah Anda layak atau tidak. Jika selalu layak, Anda mungkin bisa lolos dengan strategi percabangan yang "mundur bebas", yaitu, Anda mengikutinya seperti heuristik.

Jika masalah tidak dijamin layak, MIP bisa hilang selamanya. Heuristik berdasarkan hal di atas mungkin masih bernilai untuk menemukan solusi dengan cepat dengan jumlah pelanggaran yang relatif rendah.

Secara umum, jawabannya tidak diketahui, bukan tidak mungkin!

kami menyimpulkan versi keputusan aliran jaringan pembatasan XOR adalah NP-Complete. oleh karena itu (dimungkinkan, kita dapat melakukannya) jika dan hanya jika P = NP.