Pemrograman Campuran-Bilangan Bulat Robust — Optimasi dengan variabel bilangan bulat di bawah ketidakpastian
- Diperkenalkan oleh
- Ben-Tal & Nemirovski; Bertsimas & Sim
- Tahun
- 1998–2004
- Jenis
- Deterministic robust reformulation of MIP under uncertainty
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman Campuran-Bilangan Bulat Robust (RMIP) menggabungkan pemrograman campuran-bilangan bulat dengan optimasi robust untuk menemukan solusi yang tetap layak dan mendekati optimal meskipun ada parameter yang tidak pasti.
Alih-alih mengasumsikan data tetap, ia melindungi keputusan terhadap realisasi terburuk atau adversarial dari input yang tidak pasti, menggunakan himpunan ketidakpastian eksplisit untuk mengontrol tingkat konservatisme sambil mempertahankan struktur kombinatorial dari keputusan bilangan bulat.
Intuisi di balik metode
Program campuran-bilangan bulat klasik mengasumsikan semua data diketahui secara pasti, tetapi dalam praktiknya biaya, permintaan, dan waktu pemrosesan berfluktuasi. RMIP bertanya: keputusan bilangan bulat dan kontinu mana yang terbaik jika parameter yang tidak pasti mengambil nilai terburuk yang masuk akal dalam rentang yang ditentukan? Dengan menyematkan ketidakpastian langsung ke dalam model optimasi, RMIP menghasilkan rencana yang kebal terhadap variasi data tanpa perlu skenario probabilistik berganda. Pendekatan anggaran-ketidakpastian Bertsimas-Sim memungkinkan praktisi untuk memilih antara ketahanan penuh dan efisiensi kasus rata-rata, membuat trade-off antara perlindungan dan biaya menjadi eksplisit.
Sejarah
Optimasi robust sebagai paradigma yang dapat ditangani didirikan oleh Ben-Tal dan Nemirovski pada akhir 1990-an untuk masalah kontinu. Bertsimas dan Sim (2004) memperluasnya ke program linier dengan himpunan anggaran-ketidakpastian yang mempertahankan kelayakan linier. Karya selanjutnya mengintegrasikan kerangka kerja ini dengan pemrograman bilangan bulat, menghasilkan RMIP, yang diadopsi secara luas dalam penelitian rantai pasokan, energi, dan transportasi melalui tahun 2010-an.
Kapan digunakan
Gunakan RMIP ketika keputusan melibatkan pilihan bilangan bulat atau biner (lokasi fasilitas, penentuan ukuran lot, desain jaringan, penjadwalan) dan beberapa parameter input tidak pasti tetapi distribusi probabilitas tidak tersedia atau tidak dapat diandalkan. Ini sesuai ketika pelanggaran kendala tidak dapat diterima (persyaratan kelayakan keras) dan jaminan deterministik yang konservatif lebih disukai daripada optimasi nilai yang diharapkan. JANGAN gunakan ketika distribusi ketidakpastian dikarakterisasi dengan baik dan aproksimasi rata-rata sampel atau MIP stokastik layak; ketika semua variabel keputusan kontinu (gunakan LP robust sebagai gantinya); atau ketika himpunan ketidakpastian begitu besar sehingga model menjadi tidak dapat ditangani tanpa strategi dekomposisi.
Batasan dan pertimbangan
- Konservatif berdasarkan desain — tujuan kasus terburuk biasanya lebih buruk daripada tujuan kasus rata-rata dari pemrograman stokastik.
- Memilih himpunan ketidakpastian yang sesuai memerlukan pengetahuan domain; himpunan yang dipilih dengan buruk mengarah pada perlindungan berlebih atau perlindungan kurang.
- Reformulasi robust dapat secara signifikan meningkatkan ukuran model (variabel dan kendala tambahan), meningkatkan beban komputasi untuk kasus besar.
- Tidak memberikan pernyataan probabilitas tentang kinerja solusi; MIP stokastik lebih cocok ketika ukuran risiko probabilistik diperlukan.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Memberikan jaminan kelayakan kasus terburuk yang deterministik tanpa memerlukan distribusi probabilitas untuk parameter yang tidak pasti.
- Parameter anggaran-ketidakpastian (Gamma) memberikan kontrol intuitif yang dapat disesuaikan atas trade-off antara ketahanan dan optimalitas.
- Reformulasi mempertahankan struktur MIP, memungkinkan penggunaan pemecah komersial yang matang dan teknologi branch-and-cut.
- Dapat diterapkan pada masalah kombinatorial yang sulit seperti desain jaringan, lokasi fasilitas, dan penjadwalan produksi.
- Secara komputasi lebih dapat ditangani daripada MIP stokastik penuh dengan banyak skenario.
Penerapan
- Desain jaringan rantai pasokan di bawah ketidakpastian permintaan dan waktu tunggu
- Perencanaan ekspansi kapasitas sistem energi dengan ketidakpastian pembangkitan terbarukan
- Lokasi fasilitas kesehatan di bawah ketidakpastian permintaan pasien
- Penjadwalan kru maskapai dengan ketidakpastian penundaan penerbangan
- Penentuan ukuran lot manufaktur di bawah ketidakpastian biaya dan waktu pemrosesan
- Perutean jaringan telekomunikasi dengan ketidakpastian volume lalu lintas
Cara kerjanya
Cara kerjanya
Formulasikan MIP nominal: identifikasi variabel keputusan (biner atau bilangan bulat y, kontinu x), fungsi tujuan, dan kendala. Tentukan parameter mana (koefisien biaya, nilai sisi kanan, entri matriks teknologi) yang tidak pasti dan harus dilindungi.
Definisikan himpunan ketidakpastian U untuk parameter yang tidak pasti. Pilihan umum adalah himpunan kotak (rentang interval untuk setiap parameter), himpunan elipsoidal (ketidakpastian berkorelasi), atau himpunan anggaran Bertsimas-Sim (paling banyak Gamma parameter menyimpang secara bersamaan), di mana Gamma mengontrol konservatisme.
Ganti setiap kendala yang tidak pasti dengan padanan robustnya, yang harus berlaku untuk semua realisasi di U. Untuk ketidakpastian anggaran, ini menghasilkan reformulasi yang dapat ditangani: kendala asli ditambah dengan suku penalti yang mengontrol jumlah deviasi kasus terburuk. Hasilnya adalah model yang lebih besar tetapi masih dapat ditangani oleh MIP.
Selesaikan MIP yang diformulasikan ulang secara robust dengan pemecah branch-and-bound atau branch-and-cut standar (misalnya, CPLEX, Gurobi, SCIP). Reformulasi mempertahankan persyaratan integritas pada y. Untuk kasus skala besar, dekomposisi Benders atau metode cutting-plane dapat mendekomposisi masalah.
Evaluasi solusi robust dengan: (a) menghitung nilai tujuannya di bawah parameter nominal dan kasus terburuk, (b) melakukan benchmark terhadap solusi pemrograman stokastik menggunakan skenario Monte Carlo, dan (c) melaporkan harga ketahanan — biaya tambahan yang dibayarkan untuk perlindungan ketidakpastian.
Kesalahan umum
- Memilih Gamma=0 (tidak ada anggaran ketidakpastian) mereproduksi MIP nominal dan tidak memberikan perlindungan; Gamma yang terlalu besar mengarah pada solusi yang terlalu konservatif dan tidak praktis secara operasional.
- Memperlakukan semua parameter sebagai tidak pasti secara bersamaan dapat membuat reformulasi tidak dapat ditangani — identifikasi parameter kritis yang tidak pasti untuk dilindungi secara selektif.
- Mengabaikan struktur korelasi ketidakpastian dapat menghasilkan himpunan ketidakpastian yang terlalu pesimis; himpunan elipsoidal lebih disukai ketika korelasi diketahui.
- Melaporkan hanya tujuan kasus terburuk tanpa membandingkannya dengan benchmark nominal atau stokastik memberikan gambaran kualitas solusi yang tidak lengkap.
Pertanyaan yang sering diajukan
Bagaimana RMIP berbeda dari pemrograman campuran-bilangan bulat stokastik?
MIP stokastik menggunakan distribusi probabilitas dan mengoptimalkan kinerja rata-rata di seluruh skenario yang disampel, sementara RMIP melindungi terhadap kasus terburuk dalam himpunan ketidakpastian tanpa memerlukan informasi distribusi. RMIP memberikan satu solusi robust deterministik; MIP stokastik memberikan kebijakan yang baik secara rata-rata.
Apa itu 'harga ketahanan' dan seberapa besar biasanya?
Harga ketahanan adalah peningkatan persentase dalam nilai tujuan dibandingkan dengan optimum nominal (tanpa ketidakpastian). Bertsimas dan Sim menunjukkan bahwa harganya tumbuh secara linier dengan Gamma tetapi tetap moderat untuk nilai anggaran tipikal, seringkali 5–15% dalam aplikasi praktis.
Bisakah RMIP menangani nilai sisi kanan yang tidak pasti serta koefisien biaya yang tidak pasti?
Ya. Ketidakpastian pada nilai sisi kanan kendala mengarah pada kendala kelayakan robust, sementara ketidakpastian pada koefisien tujuan memengaruhi optimalitas robust. Keduanya dapat ditangani secara bersamaan dalam kerangka anggaran-ketidakpastian, meskipun struktur reformulasi berbeda.
Apakah RMIP dapat diselesaikan dengan pemecah MIP standar?
Untuk himpunan anggaran Bertsimas-Sim, reformulasi robust tetap merupakan MIP dan dapat diselesaikan langsung dengan pemecah seperti CPLEX atau Gurobi. Himpunan ketidakpastian elipsoidal menghasilkan program kerucut orde kedua campuran-bilangan bulat (MISOCP), yang juga didukung oleh pemecah modern.
Kapan saya harus memilih himpunan ketidakpastian kotak daripada himpunan anggaran-ketidakpastian?
Himpunan kotak melindungi terhadap semua parameter yang menyimpang secara bersamaan ke nilai ekstremnya, yang seringkali terlalu konservatif. Himpunan anggaran (Gamma) lebih disukai ketika deviasi kasus terburuk simultan dari semua parameter tidak mungkin terjadi, karena menghasilkan solusi yang kurang konservatif dan lebih hemat biaya.
Metode terkait
Sumber
Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.
Buka referensi DOIDisalin.Ben-Tal, A., El Ghaoui, L., Nemirovski, A. (2009). Robust Optimization. Princeton University Press, Princeton, NJ.
ISBN: 9780691143682Disalin.