Solusi pemrograman linier dalam satu lintasan dengan variabel yang dipesan

Saya memiliki keluarga masalah pemrograman linier: memaksimalkan subjek A x ≤ b , x ≥ 0 . Elemen-elemen A , b , dan c adalah bilangan bulat tidak negatif, $c' x$$A x\le b$$x\ge0$$A$$b$$c$$c$ sangat positif. ( juga harus integral tetapi saya akan khawatir tentang itu nanti.)$x$

Sering terjadi dalam aplikasi saya bahwa koefisien dan c sedemikian rupa sehingga algoritma satu langkah yang disederhanakan memberikan solusi optimal untuk setiap pilihan b : algoritma satu jalur menentukan elemen x 1 , … , x n secara berurutan, memilih setiap x j menjadi nilai terbesar yang mungkin konsisten dengan nilai yang sudah ditentukan x 1 , … , x j - 1 . Dalam bahasa simpleks, urutan memasukkan variabel hanya x 1 hingga x $A$$c$$b$$x_1,\dots,x_n$$x_j$$x_1,\dots,x_{j-1}$$x_1$$x_n$ , dan berakhir setelah itu langkah. Ini menghemat banyak waktu dibandingkan dengan simpleks penuh.$n$

Algoritma ini berfungsi ketika kolom dan elemen c telah diurutkan dari "murah" ke "mahal". Variabel "murah" adalah kolom A dengan nilai yang umumnya kecil, di mana elemen yang sesuai dari c adalah besar: untuk elemen x Anda mendapatkan banyak output dengan permintaan yang tidak terlalu banyak pada kendala b . Jadi algoritma hanya mengatakan "lakukan hal-hal yang mudah dulu."$A$$c$$A$$c$$x$$b$

Pertanyaan saya adalah: properti apa dari dan c yang akan meyakinkan kami bahwa algoritma yang disederhanakan ini bekerja untuk semua b ? Dugaan awal saya adalah bahwa elemen bukan nol dari A harus meningkat di setiap baris, tetapi itu tidak benar.$A$$c$$b$$A$

Berikut adalah beberapa contoh, semuanya dengan : A 1 = ( 1 1 1 1 2 3 3 2 0 ) , A 2 = ( 0 0 1 3 0 2 0 3 2 ) , A 3 = ( 1 1 1 1 0 0 1 0 1 ) = ( $c=(1,1,1)$$A_1=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 2 & 3 \\ 3 & 2 & 0\end{pmatrix}$$A_2=\begin{pmatrix} 0 & 0 & 1 \\ 3 & 0 & 2 \\ 0 & 3 & 2 \end{pmatrix}$$A_3=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{pmatrix}$ , . Untuk semua ini, algoritma sekuensial memberikan solusi optimal untuk semua nilaib(dengan eksperimen numerik). Angka3adalah satu-satunya yang semua permutasi kolom juga berfungsi. A1danA3sangat membingungkan, karena(1,1,3)terlihat lebih mahal daripada(1,3,0)1,1)lebih mahal daripada$A_4=\begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}$$b$$A_3$$A_1$$A_3$$(1,1,3)$$(1,3,0)$ dan $(1,1,1)$ .$(1,0,0)$

Saya akan sangat berterima kasih atas petunjuk pada literatur, untuk masalah seperti ini, atau saran sama sekali. Pasti ada kasus-kasus lain di mana beberapa variabel dapat ditentukan sebagai "lebih murah" daripada yang lain dan dapat dilakukan dengan aman terlebih dahulu. Dengan semua pekerjaan yang telah dilakukan pada pemrograman linear selama bertahun-tahun, tampaknya sesuatu yang serupa pasti muncul, tetapi saya belum dapat menemukannya.

Mungkin contoh paling terkenal di mana algoritma serakah diketahui untuk menyelesaikan LP adalah untuk kasus khusus masalah transportasi. Hoffman ("Pada program linear sederhana", dalam Convexity , vol. 7 dari Prosiding Simposium dalam Matematika Murni , halaman 317-327, 1963) membuktikan bahwa jika matriks biaya untuk masalah transportasi (maksimalisasi) memenuhi properti Monge ( ketika 1 ≤ i < k ≤ n , 1 ≤ $c_{ij} + c_{kl} \geq c_{il} + c_{kj}$$1 \leq i < k \leq n$ ) maka solusi optimal dapat ditemukan dengan cara serakah seperti yang Anda jelaskan. $1 \leq j < l \leq n$

Hoffman juga memiliki kertas survei (" Pada algoritma serakah yang berhasil ") dari tahun 1985 di mana ia membahas kasus-kasus yang diketahui di mana algoritma serakah memberikan solusi optimal untuk LP. Selain karyanya sendiri yang dikutip di atas (tentang yang ia katakan, "sebagian besar masalah pemrograman linier yang dikenal [pada 1963] rentan terhadap algoritma serakah adalah kasus-kasus khusus dari ide Monge"), ia menyebutkan interpretasi pemrograman linear Edmonds tentang suatu generalisasi dari matroid dan diskusi tentang kasus ketika $A$ tidak negatif, antara lain.

Saya membayangkan ada hasil yang lebih baru, tetapi mudah-mudahan ini setidaknya sebagian menjawab pertanyaan Anda dan memberi Anda beberapa ide dari mana lagi mencari.

Berkat saran Prof Spivey, saya akhirnya menemukan apa yang saya pikir adalah seni: Ulrich Faigle, Alan J. Hoffman, dan Walter Kern, "Karakterisasi Matriks Kotak-Greedy Nonnegatif", SIAM J. Disc. Matematika 9 (1996) hlm 1-6. Matriks adalah "serakah" jika algoritma yang saya jelaskan di atas memberikan solusi optimal untuk semua . Matriks adalah "kotak-serakah" jika algoritma serakah memberikan solusi optimal dengan kondisi tambahan x ≤ d untuk semua b dan semua d ≥ 0 . Jelas, rakus kotak adalah kondisi yang lebih kuat daripada rakus.$b$$x\le d$$b$$d\ge0$

Selalu berasumsi bahwa . Faigle, Hoffman, dan Kern membuktikan bahwa A adalah kotak serakah jika dan hanya jika ia tidak memiliki k × ( k + 1 ) (untuk setiap k ) submatrix dari bentuk ( r 1 s $c_1\ge\dots\ge c_n>0$$A$$k\times(k+1)$$k$dengan masing-masingrj>0dan∑i:si>0r$\begin{pmatrix} r_1 & s_1 & & & \\ r_2 & & s_2 & & \\ \vdots & & & \ddots \\ r_k & & & & s_k \end{pmatrix}$$r_j>0$. Dalam mengekstraksi submatrices, permutasi baris sewenang-wenang diizinkan tetapi tidak kolom, dan subset sewenang-wenang dari baris dan kolom diperbolehkan. Jadi secara khusus, dengank=1, elemen bukan nol di setiap barisAharus tidak menurun.$\sum_{i:s_i>0} \frac{r_i}{s_i} > 1$$k=1$$A$

Ternyata, sayangnya, bahwa dalam masalah saya matriks tidak serakah kotak meskipun saya masih percaya mereka serakah. Sebagai contoh, dalam saya di atas kondisinya dilanggar dan matriks ini tidak serakah kotak meskipun serakah. Sejauh yang saya tahu, tidak ada hasil mengidentifikasi matriks serakah.$A_1$

Contoh termudah untuk sesuatu seperti ini mungkin masalah ransel fraksional di mana item diizinkan untuk difraksinasi. masalah ini (dan dual lpnya) dapat diselesaikan dengan menyortir item untuk laba per berat, memilih urutan terpanjang dalam urutan ini yang layak dan memfraksinasi item terakhir.