Solusi efisien dari program linear integer campuran

12

Banyak masalah penting dapat diekspresikan sebagai program linear integer campuran . Sayangnya menghitung solusi optimal untuk kelas masalah ini adalah NP-Complete. Untungnya ada algoritma perkiraan yang terkadang dapat memberikan solusi berkualitas dengan hanya perhitungan dalam jumlah sedang.

Bagaimana saya harus menganalisis program linear integer campuran tertentu untuk melihat apakah itu cocok untuk salah satu algoritma perkiraan ini? Apa ciri-ciri atau kualitas yang relevan yang mungkin dimiliki oleh suatu program?

Apa algoritma yang relevan yang digunakan saat ini dan bagaimana kualitas ini dipetakan ke dalam algoritma ini?

Paket perangkat lunak apa yang harus saya cari untuk eksperimen?

MRocklin
sumber

Jawaban:

15

Meskipun mixed-integer linear programming (MILP) memang NP-complete, ada contoh (nontrivial) yang dapat dipecahkan dari pemrograman linear integer campuran.

NP-complete berarti pemrograman linear integer campuran adalah:

a) dipecahkan dalam waktu polinomial dengan mesin Turing nondeterministic (bagian NP)

b) waktu polinomial direduksi menjadi 3-SAT (bagian lengkap; untuk sisa diskusi, bagian ini benar-benar tidak masalah)

O(2n)n

Pernyataan itu tidak berarti bahwa contoh "kecil" tidak dapat dipecahkan. Sayangnya, saya tidak bisa membuat pernyataan yang tepat tentang apa arti kecil untuk contoh MILP. Saya memecahkan masalah yang memiliki 3.000 atau lebih variabel keputusan biner secara rutin. Tergantung pada perumusan masalah, masalah bisa memakan waktu kurang dari 0,01 detik (yang merupakan kasus untuk masalah yang relatif tidak terbatas) atau lebih dari satu jam (yang merupakan masalah untuk masalah di mana banyak kendala aktif), karena masalah tersebut tampaknya untuk memiliki struktur yang menguntungkan. Saya dapat mengatakan bahwa solver LP yang mutakhir dapat memecahkan piringan hitam dengan beberapa juta variabel keputusan kontinu, dan bahwa tanpa struktur khusus, sangat tidak mungkin bahwa sebuah contoh masalah dengan sekitar 1.000 hingga 10,

Jika Anda merasa memiliki instance MILP yang dapat dipecahkan, Anda akan ingin menggunakan algoritma branch-and-bound atau branch-and-cut. Implementasi terbaik adalah CPLEX dan Gurobi . Keduanya adalah produk komersial yang memiliki lisensi akademik gratis jika Anda menggali cukup banyak. Jika Anda benar-benar membutuhkan pemecah sumber terbuka, proyek-proyek dalam komunitas COIN-OR lebih tepat, meskipun paket-paket sumber kadang-kadang bisa rewel. Proyek yang paling relevan adalah pemecah cabang-dan-cut CBC , pemecah SYMPHONY , pemecah harga memotong-cabang BCP , dan pemecah cabang-dan-potong ABACUS . Semua proyek ini akan membutuhkan beberapa paket dari COIN-OR, karena struktur modularnya.

Jika Anda ingin opsi untuk mencoba beberapa solver , taruhan terbaik Anda adalah dengan menggunakan Open Solver Interface dari COIN-OR . Maklum bahwa sebagian dari antarmuka ini hanya akan membiarkan Anda mengatur opsi solver dasar, dan bahwa untuk menetapkan opsi lanjutan untuk solver, Anda harus berkonsultasi dengan milis COIN-OR untuk perincian lebih lanjut. Pemecah MILP komersial lebih BANYAK (kadang-kadang urutan besarnya atau lebih) lebih cepat dari pemecah open source. Pilihan lain untuk membuat prototipe adalah penggunaan bahasa pemodelan aljabar seperti GAMS atau AMPL . Kedua paket perangkat lunak bersifat komersial, tetapi memiliki versi uji coba yang dapat digunakan pada contoh masalah kecil. Untuk contoh masalah yang lebih besar, Anda bisa mengirimkan file GAMS atau AMPL keNEOS server harus dipecahkan; server ini tersedia untuk umum.

Jika Anda memiliki instance MILP yang cukup besar, maka tidak satu pun dari pemecah ini yang akan bekerja dengan baik. Anda bisa mengendurkan variabel integer ke variabel kontinu, memecahkan masalah, dan kemudian membulatkan ke kumpulan variabel integer terdekat yang merupakan solusi yang layak dari instance masalah Anda. Solusi optimal dari relaksasi LP dari MILP Anda akan memberi Anda batas bawah pada nilai fungsi objektif MILP Anda yang optimal (tentu saja dengan asumsi minimisasi), dan solusi yang layak dari MILP Anda akan memberi Anda batas atas pada tujuan optimal nilai fungsi MILP Anda.

Jika Anda benar-benar beruntung dan matriks kendala Anda benar - benar unimodular , maka Anda dapat menggunakan LP solver untuk menghasilkan solusi integer untuk MILP Anda, dan Anda dapat menyelesaikan masalah Anda secara efisien meskipun ukurannya besar. Kelas masalah lain memiliki algoritma aproksimasi cepat, seperti masalah ransel dan masalah pemotongan stok . Algoritma penguraian MILP khusus juga ada untuk masalah yang memiliki struktur khusus, meskipun saya tidak akrab dengan rincian, karena topik-topik tersebut agak khusus dan di luar ruang lingkup tesis saya.

Saya tidak mengetahui skema perkiraan waktu sepenuhnya polinomial (FPTAS) khusus untuk MILP, meskipun FPTAS dari kelas masalah yang mencakup MILP ada (lihat makalah ini). Rekomendasi saya adalah untuk menggunakan salah satu pemecah pemrograman linier campuran-bilangan bulat di atas dalam hubungannya dengan batas waktu dan toleransi yang sesuai pada kesenjangan optimalitas. Melakukan hal itu akan memberi Anda solusi layak yang terbaik untuk MILP Anda dalam batas waktu, dan jika pemecah berakhir dengan sukses sebelum batas waktu, solusi yang layak akan optimal ke dalam toleransi kesenjangan optimal yang Anda tetapkan. Tindakan ini masih akan memberi Anda batas pada kualitas solusi, karena solusi yang layak Anda akan menjadi batas atas, dan pemecah dapat memberi Anda batas bawah yang sesuai. Batas tidak akan dijamin berada dalam solusi optimal faktor tertentu, tetapi sekali lagi, FPTAS akan menjadi lebih mahal karena perkiraannya menjadi lebih baik.

Hal terpenting yang dapat Anda lakukan sebelum menentukan formulasi MILP adalah memilih formulasi terkuat yang dapat Anda temukan; Anda dapat menemukan saran tentang cara memilih formulasi yang kuat dalam Pengantar Optimalisasi Linier oleh Bertsimas dan Tsitsiklis. Gagasan utamanya adalah memilih formulasi yang batasannya mendefinisikan polytope yang sedekat mungkin dengan lambung cembung formulasi (juga lihat catatan kursus ini ). Memilih formulasi yang kuat dapat membuat perbedaan besar dalam waktu yang dibutuhkan untuk menyelesaikan masalah.

Geoff Oxberry
sumber
Apa contoh struktur yang disukai yang Anda maksud? Apa saja pertanyaan yang harus saya tanyakan tentang program saya?
MRocklin
Selain unimodularity, masalah ransel, dan masalah pemotongan stok, jika masalah Anda adalah program stokastik multi-tahap, ada strategi dekomposisi untuk mengambil keuntungan dari struktur itu. Anda dapat menggunakan metode seperti (umum) dekomposisi Benders, dekomposisi Dantzig-Wolfe, dan dekomposisi berbentuk-L. Anda juga dapat memanfaatkan struktur blok-sudut dalam kendala Anda. Dekomposisi Dantzig-Wolfe, dekomposisi Benders, dan dekomposisi Benders yang digeneralisasi adalah metode yang pernah saya gunakan sekali atau dua kali di masa lalu untuk masalah pekerjaan rumah.
Geoff Oxberry
Ada beberapa trik dan jebakan lain yang tidak disebutkan oleh Geoff, tetapi sulit untuk menghasilkan saran khusus tanpa melihat masalah atau kelas yang tepat.
Aron Ahmadia
Server NEOS adalah cara yang bagus untuk mengetahui apakah bahkan server komersial dapat membantu Anda mengatasi masalah.
Ant6n