Apakah pemrograman 0-1 dengan jumlah konstan yang secara polinomi dapat dipecahkan?

11

Itu ditunjukkan dalam makalah "Program Integer dengan Jumlah Variabel Tetap" bahwa program integer dengan jumlah konstan kendala (atau variabel) dapat dipecahkan secara polinomi.

Apakah ini berlaku untuk pemrograman 0-1?

Keteraturan
sumber
Bukankah 0-1 pemrograman merupakan kasus khusus pemrograman integer?
Nathann Cohen
3
Saya kira bagian nontrivial adalah ini: jika Anda memiliki algoritma kotak hitam A yang mampu menyelesaikan program integer dengan sejumlah kendala konstan (tetapi banyak variabel sewenang-wenang), tidak jelas bagaimana menggunakan A untuk menyelesaikan program 0-1 dengan jumlah kendala yang konstan. Anda tidak bisa dengan mudah menambahkan batasan dari bentuk untuk setiap variabel x i . 0xsaya1xsaya
Jukka Suomela
3
Apa itu "program 0-1 dengan jumlah kendala konstan"? Apakah batasan tidak masuk hitungan? 0xsaya1
Jeffε

Jawaban:

20

Saya berasumsi bahwa dengan "pemrograman 0-1 dengan jumlah kendala konstan" yang Anda maksud adalah masalah berikut:

Maksimalkan beberapa fungsi linier dari (x_1, x_2, ..., x_n) dengan batasan bahwa setiap x_i ada di {0,1} dan jumlah konstan kendala linear tambahan.

Masalah ini NP-complete bahkan dengan 1 kendala tambahan karena 0-1 knapsack dapat ditulis dalam formulir ini.

Robin Kothari
sumber
1
Juga, "ransel tidak terikat," di mana Anda memiliki batasan non-negatif dan batasan integral tanpa batas atas 1, masih NP-hard.
daveagp
0

Lenstra menunjukkan dalam makalah yang disebutkan, bahwa Masalah Kelayakan Program Integer Linear

SEBUAHm,nbZm
xZnSEBUAHxb

dapat dipecahkan secara polinomi, jika n atau m konstan. (Perhatikan tidak adanya fungsi tujuan.) Hasil ini biasanya digunakan dalam analisis masalah parameter, yaitu dapat digunakan untuk membuktikan traktabilitas parameter-tetap dengan pengurangan.

muede
sumber
3
Saya tidak yakin mengapa Anda memposting ini, tetapi jika Anda menyiratkan bahwa perbedaan antara versi kelayakan dan versi optimisasi adalah penting, maka tidak, itu tidak penting: algoritma waktu polinomial untuk versi kelayakan dapat digunakan untuk menyelesaikan versi optimisasi juga dalam waktu polinomial dengan menggabungkannya dengan pencarian biner.
Tsuyoshi Ito
-1

0-1 integer programming atau binary integer programming (BIP) adalah kasus khusus pemrograman integer di mana variabel harus 0 atau 1 (bukan bilangan bulat acak). Masalah ini juga diklasifikasikan sebagai NP-hard, dan pada kenyataannya versi keputusannya adalah NP-Complete.

Karan Sapra
sumber
3
Meskipun IP dan BIP keduanya NP-hard, ini tidak mengatakan banyak tentang apakah IP dan BIP dengan jumlah konstan adalah NP-hard. Memang, IP dengan jumlah konstan kendala dalam P, sedangkan BIP dengan jumlah konstan kendala masih NP-keras.
Robin Kothari
-1

k2k

pengguna8477
sumber