Efisien menyelesaikan sistem ketidaksetaraan linear yang ketat dengan semua koefisien sama dengan 1 tanpa menggunakan LP solver umum?

Per judul, selain menggunakan LP solver tujuan umum, apakah ada pendekatan untuk memecahkan sistem ketidaksetaraan atas variabel mana ketidaksetaraan memiliki bentuk ? Bagaimana dengan kasus khusus ketidaksetaraan yang membentuk urutan total atas jumlah anggota set daya ? $x_i, \ldots, x_k$ $\sum_{i \in I} x_i < \sum_{j \in J} x_j$ $\{x_i, \ldots, x_k\}$

ds.algorithms linear-algebra linear-programming jonderry
sumber

@Ankur: tidak masalah apakah itu bilangan bulat atau asli. Jika ini adalah ketidaksetaraan yang ketat, Anda dapat membulatkannya ke rasional, dan kemudian mengalikannya dengan penyebut yang paling tidak umum untuk mendapatkan solusi integer.

Peter Shor

Saya tidak tahu kode apa yang dapat Anda kode dalam 30 menit (dalam bahasa apa?). Jika itu adalah kriteria untuk "sederhana," apakah ini benar-benar sebuah pertanyaan dalam ilmu komputer teoritis?

Tsuyoshi Ito

Poin bagus, Peter Shor. jonderry, saya mengambil kembali pernyataan saya. Saya berpikir bahwa masalah kombinatorial untuk memenuhi ketidaksetaraan yang ketat ini dan masalah analitik cembung menemukan titik interior kerucut secara kualitatif berbeda. Saya salah.

Ankur

@ Tsuyoshi: Tidak perlu sepele, tapi saya ingin tahu apakah ini dapat dilakukan dari prinsip pertama tanpa menggunakan semua kekuatan ekstra dari solver LP penuh, terutama untuk kasus khusus di mana kami memiliki pemesanan dari semua subset-jumlah (perhatikan dalam kasus ini bahwa waktu polinomial adalah eksponensial dalam jumlah variabel).

jonderry

Kemudian saya berpikir bahwa "Bisakah masalah ini diselesaikan secara efisien tanpa menggunakan algoritma umum untuk pemrograman linier?" adalah cara yang baik untuk merumuskan pertanyaan Anda dengan lebih baik.

Tsuyoshi Ito

Jawaban:

Untuk pertanyaan pertama Anda, tanpa urutan total, jawaban untuk pertanyaan Anda adalah bahwa pada dasarnya sama sulitnya dengan pemrograman linier. Inilah garis besar bukti.

Pertama, mari kita membuat variabel , yang kita sebut . Sekarang, mari kita pilih variabel lain , yang akan kita panggil . Kami ingin memastikan bahwa Untuk melakukan ini, pertimbangkan ketidaksetaraan dan seterusnya. Dengan rantai yang cukup panjang, ini akan memberi tahu kita bahwa , atau , untuk beberapa sangat besar ( adalah angka Fibonacci, dan tumbuh secara eksponensial di ). $x_1>0$ $\epsilon$ $x_i$ $1$

ϵ ≪ 1 .

$\epsilon \ll 1\, .$

x_{1} < x_{2},

$x_1 < x_2,$

x_{1} + x_{2} < x_{3},

$x_1 + x_2 < x_3,$

x_{2} + x_{3} < x_{4},

$x_2+x_3 < x_4,$

N x_{1} < x_{i}

$Nx_1 < x_i$

ϵ < 1 / N

$\epsilon < 1/N$

N

$N$

N

$N$

i

$i$

Kami sekarang dapat memproduksi program linier dengan koefisien integer. Jika kita menginginkan koefisien 3 pada , kita menambahkan ketidaksetaraan dan biarkan berdiri dalam untuk 3 . Jika Anda ingin koefisien yang lebih besar, Anda bisa mendapatkannya dengan mengekspresikan koefisien dalam notasi biner, dan membuat ketidaksetaraan yang menjamin bahwa , , dan seterusnya. Untuk mendapatkan sisi kanan, kita melakukan hal yang sama dengan variabel $x_t$

x_{t} < x_{t^{'}} < x_{t^{″}} < x_{t} + ϵ

$x_t < x_{t'} < x_{t''} < x_t + \epsilon$

x_{t} + x_{t^{'}} + x_{t^{″}}

$x_t + x_{t'} + x_{t''}$

x_{t}

$x_t$

x_{u} \approx 2 x_{t}

$x_u \approx 2x_t$

x_{v} \approx 2 x_{u}

$x_v \approx 2x_u$

x_{i} = 1

$x_i = 1$ . Teknik ini akan membiarkan kita menggunakan program linier dari bentuk OP untuk kira-kira memeriksa kelayakan untuk program linear sewenang-wenang dengan koefisien bilangan bulat, tugas yang pada dasarnya sekeras pemrograman linier.

Saya tidak tahu bagaimana menganalisis pertanyaan kedua, bertanya tentang kasus di mana ada total pesanan pada semua himpunan bagian.

Peter Shor
sumber