Saya tertarik untuk mengimplementasikan tugas SM untuk LP, namun saya telah mendengar tentang kemungkinan jebakan: Buku Cormen mengatakan bahwa adalah mungkin untuk memiliki data input yang akan membuat implementasi naif untuk berperilaku dalam waktu yang eksponensial. Saya juga mendengar bahwa implementasi yang naif dapat mengulang untuk beberapa jenis data.
Apakah ada buku / kertas / sumber yang menjelaskan nuansa implementasi praktis SM?
Terima kasih sebelumnya.
Jawaban:
Saya sangat merekomendasikan makalah oleh Bixby, "bapak" dari CPLEX, yang mensurvei tidak hanya pada aspek implementasi dari algoritma simpleks (revisi): Robert E. Bixby , Memecahkan Program Linear Dunia Nyata: Satu Dekade dan Lebih Banyak Kemajuan , Operasi Penelitian (50) 2002, 3-15 .
sumber
Algoritma simpleks tidak dalam P. CLRS karena itu menyatakan bahwa, meskipun dalam praktiknya bekerja "baik", ada beberapa input yang menyebabkan algoritma untuk berjalan dalam waktu eksponensial. Ini benar-benar terkait dengan algoritma, bukan pada implementasinya: Anda akan menghadapi ini secara independen dari seberapa tepatnya Anda mengimplementasikan algoritma. Namun, LP ada di P. Ini dibuktikan oleh Khachian pada 1979, namun algoritma ellipsoidnya tidak praktis. Saat ini, metode titik interior banyak digunakan. Yang pertama ditemukan oleh Karmarkar pada tahun 1984.
Jika Anda tertarik dengan implementasi praktis, lihat:
GUROBI, gratis untuk penggunaan akademis, saat ini merupakan pengoptimal terbaik yang tersedia (baik versi paralel berurutan maupun memori bersama):
http://www.gurobi.com
perpustakaan GLPK:
http://www.gnu.org/software/glpk/
ini adalah proyek open source, menyediakan implementasi untuk:
sumber
Buku Pemrograman Linier Vanderbei membahas banyak detail tingkat rendah ... Tetapi seperti jawaban / komentar lain yang disarankan, menerapkan solver LP adalah tugas yang sulit dan tanpa pamrih. Off the shelf solver mungkin adalah cara untuk pergi ... (Ada juga beberapa pemecah LP open source ...)
sumber
Bukan hanya implementasi naif yang terkadang berperilaku dalam waktu eksponensial. Bahkan, saya pikir semua aturan deterministik dan acak yang diketahui memiliki input kasus terburuk super-polinomial. Sebagian besar input diketahui yang menghasilkan perilaku kasus terburuk ini sangat terstruktur, pertanyaan terkait:
Struktur instance patologis untuk algoritma simpleks
Namun, dalam praktiknya SM berfungsi dengan baik. Ini telah diformalkan dengan diperkenalkannya analisis yang dihaluskan yang pada dasarnya merupakan analisis kasus terburuk dengan input yang sedikit terganggu. Di bawah analisis ini, SM adalah polytime, dengan kata lain, untuk setiap input (bahkan yang patologis) ada sedikit gangguan yang memungkinkan algoritma bekerja dengan baik. Wawasan ini telah ditransformasikan menjadi algoritma acak yang berkinerja dalam polytime. Namun, sejauh yang saya mengerti, masih ada beberapa perdebatan tentang apakah algoritma ini memenuhi syarat sebagai algoritma simpleks 'benar'. Saya juga tidak mengetahui apakah paket standar mengimplementasikan sesuatu seperti ini, tetapi Anda harus dapat menemukan beberapa implementasi jika Anda mencari di sekitar, karena hasilnya berusia 5+ tahun.
sumber
Anda dapat memeriksa Luenberger, Ye, Linear and Nonlinear Programming, edisi ke-3. Kelihatannya cukup komprehensif, tetapi saya belum sampai sejauh ini untuk mengatakan apakah itu sepenuhnya menjawab pertanyaan Anda.
sumber