Skip to content
Kembali ke hasil pencarian

Pemrograman Integer Stokastik — Mengoptimalkan Keputusan Diskrit di Bawah Ketidakpastian

Diperkenalkan oleh
Dantzig, G. B.; Beale, E. M. L.
Tahun
1955
Jenis
Optimization under uncertainty with discrete decisions
Keluarga
Simulation / optimization

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Pemrograman Integer Stokastik (SIP) adalah kerangka kerja optimasi yang menggabungkan variabel keputusan integer (diskrit) dengan pemodelan probabilistik eksplisit terhadap ketidakpastian.

SIP mencari keputusan terbaik di awal (here-and-now) yang meminimalkan ekspektasi biaya (atau memaksimalkan ekspektasi manfaat) di seluruh distribusi skenario masa depan, dengan mempertimbangkan fakta bahwa beberapa keputusan harus dibuat sebelum ketidakpastian terselesaikan.

Intuisi di balik metode

Banyak keputusan di dunia nyata bersifat diskrit (membangun fasilitas atau tidak; menugaskan pekerja atau tidak) dan tidak pasti (permintaan, biaya, dan kendala tidak diketahui pada saat keputusan dibuat). SIP menangani kedua tantangan ini secara bersamaan. SIP memodelkan masa depan yang tidak pasti sebagai serangkaian skenario dengan probabilitas terkait, kemudian menemukan solusi integer yang berkinerja terbaik secara rata-rata — atau yang melakukan lindung nilai terhadap hasil terburuk. Berbeda dengan pemrograman linear stokastik, struktur diskrit membuat masalah ini secara kombinatorial lebih sulit, tetapi keputusan yang dihasilkan dapat langsung diimplementasikan tanpa pembulatan atau aproksimasi.

Sejarah

Pemrograman stokastik berakar dari Dantzig (1955) dan Beale (1955), yang secara independen mengusulkan model penanggulangan dua tahap untuk program linear di bawah ketidakpastian. Perluasan integer muncul seiring dengan matangnya pemrograman integer melalui tahun 1960-an–1980-an. Buku teks Birge dan Louveaux tahun 1997 mengkodifikasi bidang ini, dan Kleywegt et al. (2002) menetapkan Sample Average Approximation sebagai pendekatan komputasi standar untuk optimasi diskrit stokastik skala besar.

Kapan digunakan

Gunakan Pemrograman Integer Stokastik ketika keputusan secara inheren bersifat diskrit (pilihan biner, alokasi unit utuh, penugasan rute) dan parameter kunci tidak pasti pada saat keputusan dibuat. SIP sangat cocok untuk perencanaan kapasitas, desain jaringan rantai pasokan, penjadwalan di bawah ketidakpastian permintaan, pengiriman energi, dan alokasi sumber daya dengan hasil acak. JANGAN gunakan SIP ketika semua variabel kontinu (pemrograman linear stokastik sudah cukup), ketika ketidakpastian dapat diabaikan atau sepenuhnya teramati sebelum memutuskan, ketika skala masalah membuat enumerasi skenario tidak dapat dihitung secara komputasi tanpa infrastruktur dekomposisi, atau ketika hanya satu skenario deterministik yang relevan.

Batasan dan pertimbangan

  • Kompleksitas komputasi tumbuh pesat seiring dengan jumlah skenario dan variabel integer; instansi besar bersifat NP-hard.
  • Pembuatan skenario memerlukan distribusi probabilitas yang kredibel, yang mungkin sulit untuk diperoleh atau diestimasi dari data terbatas.
  • Ekstensi multi-tahap (lebih dari dua tahap) menghadapi pertumbuhan eksponensial dalam pohon skenario dan jarang dapat dihitung secara komputasi di atas tiga tahap.
  • Keterampilan pemodelan diperlukan untuk menentukan kelayakan penanggulangan, kendala non-antisipatif, dan struktur penalti dengan benar.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Secara eksplisit memodelkan ketidakpastian daripada menggunakan estimasi titik, menghasilkan solusi yang kuat terhadap skenario yang terwujud.
  • Menangani keputusan diskrit dan biner secara native, sehingga solusi dapat langsung diimplementasikan tanpa pembulatan pasca-pemrosesan.
  • Kerangka kerja dua tahap secara jelas memisahkan keputusan strategis tahap pertama dari tindakan penanggulangan operasional tahap kedua.
  • Mendukung struktur penanggulangan yang kaya termasuk pengadaan sumber daya, biaya penalti, dan penjadwalan korektif.
  • Batas kualitas statistik (melalui SAA) memungkinkan praktisi untuk mensertifikasi kedekatan optimalitas dengan kepercayaan yang terukur.

Penerapan

  • Desain jaringan rantai pasokan di bawah permintaan dan waktu tunggu stokastik
  • Perencanaan ekspansi pembangkit listrik dengan keluaran terbarukan yang tidak pasti
  • Penjadwalan ruang operasi rumah sakit di bawah durasi prosedur yang bervariasi
  • Penjadwalan kru maskapai dengan penundaan penerbangan stokastik
  • Penempatan awal logistik kemanusiaan pasokan bantuan sebelum bencana
  • Optimasi portofolio keuangan dengan pemilihan aset diskrit dan pengembalian berbasis skenario

Cara kerjanya

Cara kerjanya

1

Formulasikan masalah tahap pertama: pilih variabel keputusan integer (atau campuran integer) x sebelum ketidakpastian terungkap. Definisikan tujuan yang mencakup biaya langsung dan ekspektasi biaya penanggulangan (recourse) di semua skenario. Kendala yang menghubungkan x dengan kondisi kelayakan ditentukan di sini.

Rumus
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]
2

Representasikan ketidakpastian melalui himpunan skenario yang terbatas. Setiap skenario menetapkan nilai spesifik untuk parameter acak (tingkat permintaan, biaya, ketersediaan sumber daya). Skenario dapat dihasilkan melalui pengambilan sampel historis, penarikan Monte Carlo dari distribusi yang disesuaikan, atau kasus representatif yang ditentukan pakar. Setiap skenario memiliki bobot probabilitas yang berjumlah satu.

3

Dalam formulasi dua tahap standar, setelah x ditetapkan dan skenario xi terwujud, masalah penanggulangan (tahap kedua) menentukan tindakan korektif y. Masalah penanggulangan sering kali merupakan program linear atau integer. Model lengkap meminimalkan c^T x ditambah ekspektasi biaya penanggulangan E[Q(x, xi)].

Rumus
Q(x, \xi) = \min_{y \geq 0} q(\xi)^T y \;\text{ s.t. } W(\xi)y = h(\xi) - T(\xi)x
4

Selesaikan submasalah skenario untuk mengevaluasi biaya penanggulangan untuk setiap skenario berdasarkan x. Teknik yang digunakan meliputi branch-and-bound, dekomposisi Benders, relaksasi Lagrangian, dan metode Sample Average Approximation (SAA). Untuk pohon skenario yang besar, algoritma dekomposisi memanfaatkan struktur blok di seluruh skenario.

5

Agregasikan hasil submasalah untuk memperkirakan ekspektasi biaya penanggulangan. Dalam SAA, ini adalah rata-rata dari S skenario yang disampel. Aproksimasi yang dihasilkan konvergen ke ekspektasi sebenarnya seiring bertambahnya S. Batas statistik pada kualitas solusi dapat dihitung dari varians sampel.

Rumus
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)
6

Verifikasi optimalitas atau kedekatan optimalitas melalui celah optimalitas (optimality gaps), kriteria konvergensi, atau interval kepercayaan statistik dari SAA. Jika celah tidak dapat diterima, perbaiki himpunan skenario, tingkatkan ukuran sampel, atau perketat relaksasi. Laporkan solusi tahap pertama x* dan ekspektasi total biayanya.

Kesalahan umum

  • Menggunakan terlalu sedikit skenario menghasilkan solusi yang terlalu percaya diri; menggunakan terlalu banyak membuat masalah menjadi tidak layak secara komputasi — seimbangkan melalui diagnostik konvergensi SAA.
  • Mengabaikan integritas pada tahap kedua padahal sebenarnya diperlukan mengarah pada estimasi biaya yang optimis dan tindakan penanggulangan yang tidak layak.
  • Mengasumsikan independensi skenario ketika parameter berkorelasi (misalnya, permintaan dan harga yang berkorelasi) menimbulkan bias sistematis dalam estimasi biaya ekspektasi.
  • Melupakan kendala non-antisipatif dalam masalah multi-tahap memungkinkan model untuk memanfaatkan informasi masa depan yang tidak akan tersedia dalam praktik.

Pertanyaan yang sering diajukan

Bagaimana Pemrograman Integer Stokastik berbeda dari optimasi robust?

SIP meminimalkan ekspektasi biaya di seluruh himpunan skenario berbobot probabilitas, menerima bahwa beberapa skenario mungkin menghasilkan biaya tinggi jika tidak mungkin terjadi. Optimasi robust meminimalkan biaya kasus terburuk di seluruh himpunan ketidakpastian, tanpa membuat asumsi probabilistik. SIP memerlukan distribusi probabilitas; optimasi robust hanya memerlukan himpunan ketidakpastian. SIP umumnya kurang konservatif tetapi membutuhkan lebih banyak data.

Berapa banyak skenario yang dibutuhkan dalam praktik?

Ini tergantung pada dimensi masalah dan akurasi yang diinginkan. Pendekatan Sample Average Approximation (SAA) memberikan interval kepercayaan statistik pada celah optimalitas. Studi terapan tipikal menggunakan puluhan hingga ribuan skenario; diagnostik konvergensi (varians estimator batas) memandu pilihan. Untuk masalah terstruktur, teknik pengurangan skenario (misalnya, Heitsch-Romisch) dapat secara substansial mengurangi jumlah skenario.

Bisakah Pemrograman Integer Stokastik menangani lebih dari dua tahap?

Ya, tetapi SIP multi-tahap secara signifikan lebih sulit. Pohon skenario tumbuh secara eksponensial dengan tahap, dan kendala non-antisipatif harus ditegakkan di setiap node. Dalam praktik, model tiga tahap adalah norma untuk aplikasi yang dapat dihitung secara komputasi; di luar itu, aproksimasi seperti horizon bergulir atau pengurangan pohon skenario biasanya diperlukan.

Perangkat lunak apa yang dapat menyelesaikan model Pemrograman Integer Stokastik?

Solver umum meliputi CPLEX dan Gurobi (melalui bahasa pemodelan aljabar seperti AMPL, JuMP di Julia, atau PuLP/Pyomo di Python), yang mendukung dekomposisi skenario. Kerangka kerja pemrograman stokastik khusus meliputi PySP (Python), solver format SMPS, dan paket Julia StochasticPrograms.jl, yang mengimplementasikan SAA dan progressive hedging.

Apakah Pemrograman Integer Stokastik sama dengan Pemrograman Campuran Integer Stokastik?

Pemrograman Integer Stokastik adalah kelas yang lebih luas; Pemrograman Campuran Integer Stokastik (SMIP) secara khusus mengacu pada model di mana beberapa variabel kontinu dan yang lainnya integer dalam satu atau kedua tahap. SMIP adalah bentuk yang paling umum dan paling sering ditemui dalam praktik.

Metode terkait

Sumber

  1. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    ISBN: 978-1-4614-0237-4
    Disalin.
  2. Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.

    Buka referensi DOI
    Disalin.