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?

cc.complexity-theory integer-programming 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

.

0 \leq x_{i} \leq 1

$0 \le x_i \le 1$

x_{i}

$x_i$

Jukka Suomela

3

Apa itu "program 0-1 dengan jumlah kendala konstan"? Apakah batasan

tidak masuk hitungan?

0 \leq x_{i} \leq 1

$0\le x_i \le 1$

Jeffε

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

$A_{m,n}$ $b \in \mathbb{Z}^m$
$x \in \mathbb{Z}^n$ $Ax \le b$

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

$k$ $2^k$

pengguna8477
sumber

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

Jawaban: