Pemrograman Campuran-Integer Stokastik — Optimasi di Bawah Ketidakpastian dengan Keputusan Diskrit dan Kontinu
- Diperkenalkan oleh
- Birge, J. R.; Louveaux, F.; Sen, S.
- Tahun
- 1990s–2000s
- Jenis
- Stochastic optimization model
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman Campuran-Integer Stokastik (SMIP) adalah kerangka kerja optimasi yang menemukan kombinasi terbaik dari keputusan biner, integer, dan kontinu ketika parameter kunci — biaya, permintaan, kapasitas — tidak pasti dan dimodelkan sebagai distribusi probabilitas atas serangkaian skenario.
Ini memperluas MIP klasik dengan menyematkan pohon skenario atau tujuan nilai-ekspektasi yang melindungi dari ketidakpastian sambil menghormati kendala kombinatorial.
Intuisi di balik metode
Banyak masalah perencanaan nyata memaksa pilihan ya/tidak atau bilangan bulat — membangun fasilitas atau tidak, menugaskan sejumlah kendaraan integer — namun masa depan tidak pasti. SMIP memformalkan ini dengan mempertimbangkan kumpulan skenario masa depan yang masuk akal dan memilih komitmen tahap pertama (sebelum ketidakpastian terungkap) yang meminimalkan biaya yang diharapkan atau memaksimalkan manfaat yang diharapkan di semua skenario. Kendala integer membuat masalah ini sulit secara kombinatorial, tetapi algoritma dekomposisi memanfaatkan struktur skenario untuk membuat instansi besar dapat dipecahkan.
Sejarah
Pemrograman stokastik berasal dari Dantzig (1955) dan Beale (1955) sebagai LP dua tahap. Perluasan campuran-integer muncul secara menonjol pada tahun 1990-an dengan adaptasi metode L-shaped untuk rekursi integer oleh Laporte dan Louveaux (1993) dan perlakuan komprehensif dalam buku teks Birge dan Louveaux tahun 1997. Algoritma C3/D2 Sen dan Higle (2005) memajukan pemecah SMIP yang dapat diskalakan, menetapkan bidang ini sebagai disiplin yang matang dalam riset operasi.
Kapan digunakan
Gunakan SMIP ketika keputusan melibatkan pilihan diskrit atau biner (investasi/tidak investasi, jumlah unit yang akan dibuka) dan parameter masukan kunci benar-benar tidak pasti dengan distribusi probabilitas yang dapat dikuantifikasi. Ideal untuk desain jaringan rantai pasokan di bawah ketidakpastian permintaan, ekspansi kapasitas energi, perencanaan fasilitas kesehatan, dan penempatan awal tanggap bencana. Jangan gunakan ketika semua keputusan kontinu (gunakan LP stokastik sebagai gantinya), ketika ketidakpastian tidak dapat dikuantifikasi secara bermakna sebagai distribusi, ketika jumlah skenario yang diperlukan untuk mewakili ketidakpastian mengarah pada ukuran model yang tidak dapat dipecahkan dan dekomposisi tidak tersedia, atau ketika heuristik berbasis simulasi cukup untuk kualitas keputusan yang diperlukan.
Batasan dan pertimbangan
- Kompleksitas komputasi tumbuh secara kombinatorial dengan jumlah skenario dan variabel integer; instansi besar mungkin tidak dapat dipecahkan tanpa dekomposisi yang efektif.
- Memerlukan distribusi probabilitas eksplisit atau himpunan skenario — model ketidakpastian yang salah spesifikasi mengarah pada solusi yang berkinerja buruk di luar sampel.
- Formulasi dua tahap mungkin terlalu menyederhanakan keputusan multi-periode; SMIP multi-tahap secara signifikan lebih sulit.
- Rekursi tahap kedua integer menghancurkan konveksitas yang dieksploitasi oleh pemotongan Benders standar, memerlukan pemotongan L-shaped integer khusus.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menangani keputusan diskrit kombinatorial di bawah ketidakpastian dalam satu model optimasi yang koheren.
- Menghasilkan rencana tahap pertama yang terhedging yang menyeimbangkan kinerja yang diharapkan di semua skenario.
- Metrik VSS dan EVPI memberikan justifikasi transparan untuk nilai pemodelan stokastik.
- Algoritma dekomposisi (L-shaped, progressive hedging) diskalakan ke himpunan skenario yang besar.
- Didukung secara luas dalam pemecah komersial (CPLEX, Gurobi) dan bahasa pemodelan (AMPL, Pyomo).
Penerapan
- Desain jaringan rantai pasokan dengan permintaan pelanggan yang tidak pasti dan keputusan lokasi fasilitas biner.
- Perencanaan ekspansi kapasitas tenaga listrik di bawah generasi terbarukan yang tidak pasti dan pertumbuhan beban.
- Alokasi sumber daya sistem kesehatan (staf integer, pembukaan klinik biner) di bawah ketidakpastian epidemiologis.
- Penempatan awal logistik kemanusiaan pasokan bantuan diskrit sebelum skenario bencana.
- Optimasi portofolio keuangan dengan biaya transaksi dan kendala ukuran lot integer di bawah ketidakpastian pasar.
- Penjadwalan kru maskapai di bawah penundaan penerbangan yang tidak pasti dengan variabel penugasan biner.
Cara kerjanya
Cara kerjanya
Identifikasi variabel keputusan: keputusan tahap pertama x yang dibuat sebelum ketidakpastian terungkap (integer dan/atau biner di antaranya), dan variabel rekursi tahap kedua y(xi) yang dibuat setelah skenario xi terwujud. Tentukan koefisien tujuan, matriks kendala, dan distribusi probabilitas atau himpunan skenario diskrit untuk parameter yang tidak pasti.
Konstruksi himpunan skenario hingga {xi_1, ..., xi_S} dengan probabilitas terkait {p_1, ..., p_S} yang mendekati distribusi yang mendasarinya. Skenario dapat diturunkan dari data historis, elisitasi ahli, pengambilan sampel Latin hypercube, atau metode pencocokan momen. Kualitas skenario secara langsung memengaruhi kualitas solusi.
Formulasikan ekuivalen deterministik: minimalkan c'x + jumlah_s p_s Q(x, xi_s) tunduk pada kendala tahap pertama dan integritas. Q(x, xi_s) adalah fungsi nilai tahap kedua — biaya optimal tindakan rekursi mengingat x dan skenario xi_s. Program gabungan adalah MIP besar yang ukurannya bertambah dengan jumlah skenario.
Rumus
\min_{x \in X} c^T x + \mathbb{E}_\xi[Q(x,\xi)] \quad \text{s.t. } Ax = b,\; x \in \mathbb{Z}^p \times \mathbb{R}^{n-p}Selesaikan menggunakan algoritma dekomposisi — metode L-shaped (dekomposisi Benders) untuk tahap kedua yang cembung, branch-and-cut dengan submasalah skenario, atau progressive hedging untuk dekomposisi paralel skenario. Integritas pada tahap kedua memerlukan pemotongan tambahan (pemotongan L-shaped integer, lift-and-project). Pemecah modern (CPLEX, Gurobi dengan callback, atau pustaka khusus SMIP) mengimplementasikan rutinitas ini.
Evaluasi solusi melalui Nilai Solusi Stokastik (VSS = EEV - RP) dan Nilai yang Diharapkan dari Informasi Sempurna (EVPI = RP - WS), di mana RP adalah nilai optimal masalah rekursi, EEV adalah biaya yang diharapkan dari penggunaan solusi nilai-rata deterministik, dan WS adalah nilai tunggu-dan-lihat. Metrik ini mengukur manfaat pemodelan ketidakpastian secara eksplisit.
Kesalahan umum
- Menggunakan terlalu sedikit skenario mewakili ketidakpastian secara tidak memadai, menghasilkan solusi yang terlalu percaya diri; terlalu banyak membuat model menjadi tidak layak secara komputasi.
- Mencampur peran variabel tahap pertama dan tahap kedua mengarah pada formulasi yang tidak menghormati waktu pengungkapan informasi.
- Mengandalkan solusi nilai-ekspektasi (mengabaikan stokastisitas) bisa sangat suboptimal — selalu hitung VSS untuk membenarkan upaya SMIP.
- Mengabaikan integritas pada tahap rekursi ketika sebenarnya ada menghasilkan relaksasi yang solusinya mungkin tidak layak dalam praktik.
- Pengaturan default pemecah untuk MIP seringkali perlu disesuaikan (prioritas percabangan, strategi pemotongan) dalam kerangka kerja dekomposisi SMIP.
Pertanyaan yang sering diajukan
Bagaimana SMIP berbeda dari Pemrograman Campuran-Integer biasa?
MIP biasa mengoptimalkan di bawah parameter tetap yang diketahui. SMIP secara eksplisit memodelkan parameter yang tidak pasti sebagai serangkaian skenario dengan probabilitas, mengoptimalkan kinerja yang diharapkan di semua skenario sambil memastikan keputusan tahap pertama dibuat sebelum ketidakpastian terungkap.
Berapa banyak skenario yang saya butuhkan?
Tidak ada aturan universal. Sesedikit 10–50 skenario mungkin cukup untuk keputusan tahap pertama yang stabil dalam beberapa masalah; yang lain membutuhkan ribuan. Teknik pengurangan skenario dan uji stabilitas (memeriksa bahwa solusi optimal tidak berubah saat Anda menambahkan lebih banyak skenario) membantu menentukan kecukupan.
Apa itu metode L-shaped?
Metode L-shaped adalah dekomposisi Benders yang diadaptasi untuk program stokastik. Ini secara iteratif memecahkan MIP master atas variabel tahap pertama dan submasalah skenario, menambahkan pemotongan optimalitas dan kelayakan ke master hingga konvergensi. Untuk rekursi integer, pemotongan L-shaped integer menggantikan pemotongan Benders standar.
Kapan saya harus menggunakan progressive hedging daripada L-shaped?
Progressive hedging terdekomposisi berdasarkan skenario daripada struktur submasalah, membuatnya cocok untuk komputasi paralel. Ini lebih disukai ketika skenario banyak dan submasalah besar, dan ketika algoritma dapat dijalankan di kluster. L-shaped umumnya lebih disukai untuk skenario yang lebih sedikit dan terstruktur dengan baik.
Bisakah SMIP menangani lebih dari dua tahap?
Ya, tetapi SMIP multi-tahap memerlukan pohon skenario yang tumbuh secara eksponensial dalam jumlah tahap, dan dekomposisi menjadi jauh lebih kompleks. Dalam praktiknya, sebagian besar model SMIP terapan menggunakan dua tahap, memperkirakan dinamika multi-periode melalui horizon bergulir atau agregasi.
Metode terkait
Sumber
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer.
ISBN: 9780387982175Disalin.Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20.
Buka referensi DOIDisalin.