0-1 Pemrograman Linier: menghitung Formulasi Optimal

Pertimbangkan ruang $n$ dimensi $\{0,1\}^n$ , dan mari menjadi batasan linear dari bentuk , di mana , dan .$c$$a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$$a_i \in \mathbb{R}$$x_i \in \{0,1\}$$k \in \mathbb{R}$

Jelas, memiliki efek pemisahan dalam dua himpunan bagian dan . berisi semua dan hanya titik-titik yang memuaskan , sedangkan berisi semua dan hanya titik-titik yang memalsukan .{ 0 , 1 } n S c S ¬ c S c c S ¬ c$c$$\{0,1\}^n$$S_c$$S_{\lnot c}$$S_c$$c$$S_{\lnot c}$$c$

Asumsikan bahwa . Sekarang, biarkan O menjadi subset dari S_c sedemikian rupa sehingga semua tiga pernyataan berikut ini berlaku:O S $|S_c| \geq n$$O$$S_c$

1. $O$ berisi persis $n$ poin.
2. Seperti $n$ poin adalah bebas linear.
3. Seperti $n$ poin adalah mereka pada jarak minimum dari hyperplane diwakili oleh $c$ . Lebih tepatnya, misalkan $d( x, c )$ menjadi jarak dari titik $x \in \{0,1\}^n$ dari hyperplane $c$ . Kemudian, $\forall B \subseteq S_c$ sedemikian sehingga $B$ memenuhi 1 dan 2 itu adalah kasus yang $\sum_{x \in B} d(x, c) \geq \sum_{x \in O} d(x, c)$ . Dengan kata lain $O$ adalah, di antara semua himpunan bagian $S_c$ memenuhi kedua kondisi 1 dan 2, salah satu yang meminimalkan jumlah jarak titik-titiknya dari hyperplane $c$ .

Pertanyaan

1. Mengingat , apakah mungkin untuk menghitung efisien? $c$$O$
2. Algoritme manakah yang paling dikenal untuk menghitungnya?

$\ $

Contoh dengan $n = 3$

$S_{\lnot c} = \{ ( 1, 0, 1 ) \}$ , .$O = \{ ( 0, 0, 1 ), ( 1, 1, 1 ), ( 1, 0, 0 ) \}$

$\ $

Pembaruan 05/12/2012

Motivasi

Motivasi adalah bahwa menggunakan itu harus mungkin untuk menentukan kendala yang optimal , sebagaimana mestinya hyperplane didefinisikan oleh poin di . c ∗ n $O$$c^*$$n$$O$

Batasan optimal adalah salah satu yang mengarah ke polytope optimal .P $c^*$$P^*$

Polytope optimal adalah yang memiliki semua simpul dan hanya simpul bilangan bulat dari polytope awal (simpul bilangan bulat adalah simpul yang koordinatnya semua bilangan bulat).$P^*$$P$

Proses dapat diulang untuk setiap kendala dari 0-1 misalnya , setiap kali mengganti dengan kendala optimal yang sesuai . Pada akhirnya, ini akan menyebabkan optimal polytope dari . Kemudian, karena simpul dari semua dan hanya simpul integer dari polytope awal dari , setiap algoritma untuk dapat digunakan untuk menghitung solusi optimal integer. Saya tahu bahwa dapat menghitung efisien akan menyiratkan , namun pertanyaan tambahan berikut masih ada:$c$$LP$$I$$c$$c^*$$P^*$$I$$P^*$$P$$I$$LP$$P^*$$P = NP$

Pertanyaan tambahan

Apakah ada pekerjaan sebelumnya di sepanjang garis ini? Apakah ada yang sudah menyelidiki tugas komputasi, diberi polytope , yang sesuai dengan polytope optimal ? Algoritme manakah yang paling dikenal untuk melakukan itu?P $P$$P^*$

Ini tampaknya NP-sulit dilakukan dengan tepat, dengan reduksi dari jumlah subset. Misalkan kita memiliki prosedur yang efisien untuk menghitung . Dengan bilangan bulat positif v 1 , … , v n yang dikodekan dalam biner, kami ingin menguji apakah ada subset penjumlahan ke s . Preprocess dengan membuang bilangan bulat yang lebih besar dari s .$O$$v_1,\dots,v_n$$s$$s$

Panggil prosedur untuk mendapatkan seperangkat kecil poin yang memenuhi v 1 x 1 + ⋯ + v 1 x n ≤ s , memenuhi kondisi minimum Anda (proses pra-pemrosesan memastikan | S c | ≥ n ). Set ini pasti akan berisi titik pada hyperplane v 1 x 1 + ⋯ + v 1 x n = s jika ada.$O$$v_1x_1+\dots+v_1x_n\leq s$$|S_c|\geq n$$v_1x_1+\dots+v_1x_n= s$

Sepertinya saya Anda mencoba untuk mendapatkan lambung cembung IP - pada dasarnya inilah yang algoritma capai coba capai. Meskipun ada yang menarik metode ini ongkosnya buruk dalam praktek.

Ada semua teori tentang generasi ketidaksetaraan yang valid. Titik awal yang baik adalah teori buku integer tentang shrijver.