Kesetaraan pengecekan kelayakan dan optimisasi untuk sistem linier

Salah satu cara untuk menunjukkan bahwa memeriksa kelayakan sistem linear ketidaksetaraan sama sulitnya dengan pemrograman linear adalah melalui pengurangan yang diberikan oleh metode ellipsoid. Cara yang lebih mudah adalah menebak solusi optimal dan memperkenalkannya sebagai kendala melalui pencarian biner.

Kedua pengurangan ini polinomial, tetapi tidak sangat polinomial (yaitu mereka bergantung pada jumlah bit dalam koefisien ketidaksetaraan).

Apakah ada pengurangan polinomial dari optimasi LP ke kelayakan LP?

ds.algorithms linear-programming Suresh Venkat
sumber

sebenarnya tidak. Seperti yang Anda katakan. Saya menyadari bahwa optimasi LP memecahkan kelayakan LP. Saya meminta pengurangan sebaliknya.

Suresh Venkat

Nah, output untuk optimasi dapat memiliki bit sebanyak "jumlah bit dalam koefisien", sedangkan kelayakannya adalah ya / tidak. Dengan demikian, jika dengan reduksi berarti sesuatu "kotak hitam" -ya maka jawabannya pasti negatif.

Noam

Tetapi, jika pemeriksaan kelayakan tidak hanya memberikan jawaban ya / tidak seperti yang dibahas oleh Noam di atas, tetapi dalam kasus kelayakan memberikan solusi yang layak, maka jawabannya adalah ya, oleh dualitas LP.

Kristoffer Arnsfelt Hansen

@ SureshVenkat: Misalkan primal adalah program maksimalisasi dalam variabel

, dengan dual kemudian menjadi program minimisasi dalam variabel

. Kemudian membentuk sistem ketidaksetaraan dalam variabel

, dengan mengambil kendala dari kedua primal dan ganda, bersama dengan ketidaksetaraan yang menyatakan bahwa nilai solusi primal setidaknya nilai dari solusi ganda. Kasus-kasus LP yang tidak layak dan tidak terikat juga dapat ditangani.

x

$x$

y

$y$

x, y

$x,y$

Kristoffer Arnsfelt Hansen

Bagaimana dengan polytopes / polyhedra yang didefinisikan oleh kendala implisit?

Chandra Chekuri

Jawaban:

Jawabannya adalah ya, dan pada kenyataannya orang bahkan dapat mengurangi masalah keputusan kelayakan linear ketidaksetaraan!

Kita sebagai input diberikan instance LP P: . $\max c^Tx\ \text{s.t.}\ Ax \leq b\ ;\ x\geq 0$

Kami juga memiliki akses ke oracle yang memberikan sistem ketidaksetaraan mengembalikan ya / tidak, apakah sistem tersebut layak atau tidak. $S=\{Bz \leq d\}$

Pengurangan sekarang menghasilkan sebagai berikut:

Tes jika layak. Jika tidak, kami dapat melaporkan bahwa P INFEASIBLE. $S_1=\{Ax \leq b\ ;\ x \geq 0\}$
Bentuk program dual D: . $\min b^Ty\ \text{s.t.}\ A^Ty \geq c\ ;\ y \geq 0$
Tes jika layak. Jika tidak, kami dapat melaporkan bahwa P TIDAK DIUNDANG. $S_2=\{Ax \leq b\ ;\ x\geq 0\ ;\ A^Ty\geq c\ ;\ y\geq0 \ ;\ b^Ty \leq c^Tx\}$
Iterasi atas ketidaksetaraan dan coba tambahkan satu per satu sebagai persamaan (yaitu, tambahkan ketidaksetaraan terbalik) ke sistem . Jika sistem tetap layak kami menjaga kendala di , dan jika tidak menghapusnya lagi. Biarkan menjadi sistem kendala (persamaan linear) yang ditambahkan dengan cara ini. Sistem sekarang akan sepenuhnya menentukan solusi dasar yang optimal untuk P. $S_1$ $S_2$ $S_2$ $S_3$ $S_3$
Menggunakan Gaussian Elimination pada sistem menghitung solusi optimal to P. $S_3$ $x$

Kristoffer Arnsfelt Hansen
sumber

S_{2}

$S_2$

P

$P$

@ Hengxin. Itu menulis di baris pertama dari jawaban saya bahwa jawabannya adalah ya bahkan ketika mempertimbangkan untuk mengurangi masalah keputusan. Di bawah ini saya jelas membuat asumsi itu, dan karenanya langkah 4 dan 5 diperlukan.

Kristoffer Arnsfelt Hansen