Skip to content
Kembali ke hasil pencarian

Pemrograman Linear Robust — Optimasi di Bawah Ketidakpastian

Diperkenalkan oleh
Ben-Tal, A. and Nemirovski, A.; further developed by Bertsimas, D. and Sim, M.
Tahun
1999–2004
Jenis
Uncertainty-robust linear optimization
Keluarga
Simulation / optimization

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

Ukuran huruf

Apa fungsinya?

Pemrograman Linear Robust (RLP) memperluas pemrograman linear klasik untuk menangani ketidakpastian dalam data masalah — koefisien biaya, koefisien kendala, atau sisi kanan — dengan mengharuskan solusi tetap layak dan mendekati optimal di seluruh realisasi parameter yang tidak pasti dalam himpunan ketidakpastian yang terdefinisi.

RLP menggantikan asumsi probabilistik dengan jaminan kasus terburuk (worst-case), membuatnya praktis ketika pengetahuan distribusi terbatas.

Intuisi di balik metode

Pemrograman linear biasa menemukan solusi terbaik dengan asumsi semua data diketahui secara pasti. Dalam praktiknya, koefisien diestimasi, diramalkan, atau diukur dengan kesalahan. RLP bertanya: apa keputusan terbaik yang tetap layak tidak peduli bagaimana parameter yang tidak pasti bervariasi dalam rentang yang masuk akal? Analis menentukan himpunan ketidakpastian — kotak, elipsoid, atau wilayah polihedral — dan pemecah (solver) menemukan rencana yang optimal untuk kasus terburuk di dalam himpunan tersebut. Formulasi anggaran ketidakpastian (budget-of-uncertainty) oleh Bertsimas dan Sim memungkinkan analis menyetel konservatisme: parameter Gamma mengontrol berapa banyak koefisien yang diizinkan menyimpang secara bersamaan, melakukan interpolasi antara LP nominal dan kasus terburuk yang sepenuhnya konservatif.

Sejarah

Optimasi robust ditempatkan pada pijakan teoretis yang kuat oleh Ben-Tal dan Nemirovski (1999), yang menunjukkan bahwa program linear yang tidak pasti dengan himpunan ketidakpastian elipsoidal menghasilkan program kerucut orde kedua yang dapat ditangani. Bertsimas dan Sim (2004) memperkenalkan kerangka kerja anggaran-ketidakpastian (budget-of-uncertainty), yang menjaga reformulasi sebagai program linear dan membuat robustnes dapat disetel melalui satu parameter, yang sangat memperluas adopsi praktis dalam riset operasi dan rekayasa.

Kapan digunakan

Gunakan RLP ketika ketidakpastian data nyata tetapi distribusi probabilitas tidak diketahui atau tidak dapat diandalkan, seperti dalam perencanaan rantai pasokan dengan permintaan yang tidak pasti, pengiriman energi dengan kesalahan perkiraan, atau konstruksi portofolio keuangan di bawah rentang pengembalian yang ambigu. RLP sesuai ketika kelayakan kendala di bawah semua skenario tidak dapat dinegosiasikan. Hindari RLP ketika ketidakpastian dapat diabaikan dibandingkan dengan skala tujuan, ketika distribusi probabilitas dikarakterisasi dengan baik (pemrograman stokastik mungkin lebih disukai), ketika jumlah parameter yang tidak pasti sangat besar sehingga padanan robustnya menjadi tidak dapat ditangani (intractable), atau ketika skenario kasus terburuk terlalu pesimis secara tidak realistis untuk aplikasinya.

Batasan dan pertimbangan

  • Orientasi kasus terburuk dapat menghasilkan solusi yang terlalu konservatif ketika skenario ekstrem sangat tidak mungkin terjadi.
  • Himpunan ketidakpastian elipsoidal menghasilkan program kerucut orde kedua (second-order cone programs) yang dapat ditangani tetapi bukan lagi LP murni, meningkatkan persyaratan pemecah.
  • Memerlukan analis untuk menentukan himpunan ketidakpastian, yang merupakan pilihan pemodelan tersendiri yang secara signifikan memengaruhi hasil.
  • Tidak secara langsung memberikan pernyataan probabilitas pelanggaran; pemrograman stokastik lebih baik jika probabilitas ekor (tail probabilities) penting.
  • Merupakan degenerasi menjadi LP nominal ketika Gamma = 0, tidak memberikan perlindungan terhadap ketidakpastian.

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

Kelebihan

  • Memberikan jaminan kelayakan kasus terburuk yang keras tanpa memerlukan asumsi distribusi.
  • Formulasi anggaran Bertsimas-Sim menghasilkan padanan LP yang dapat ditangani yang dapat dipecahkan dengan pemecah siap pakai (off-the-shelf solvers).
  • Anggaran robustnes Gamma memberi analis tombol intuitif untuk menukar kualitas solusi dengan konservatisme.
  • Efisien secara komputasi — padanan robust untuk himpunan anggaran memiliki kompleksitas yang mirip dengan LP asli.
  • Sangat cocok untuk masalah di mana pelanggaran kendala mahal atau tidak aman.

Penerapan

  • Desain jaringan rantai pasokan dengan biaya transportasi dan permintaan yang tidak pasti
  • Pengiriman sistem tenaga listrik di bawah ketidakpastian perkiraan energi terbarukan
  • Optimasi portofolio dengan rentang pengembalian aset yang ambigu
  • Perencanaan perawatan terapi radiasi dengan ketidakpastian gerakan pasien
  • Penjadwalan kru maskapai di bawah penundaan penerbangan yang tidak pasti
  • Alokasi sumber daya air dengan ketidakpastian curah hujan dan penguapan

Cara kerjanya

Cara kerjanya

1

Formulasikan program linear nominal: minimalkan fungsi tujuan linear c^T x tunduk pada kendala ketidaksetaraan linear Ax <= b dan non-negativitas. Identifikasi koefisien mana — biasanya entri matriks kendala a_ij — yang tidak pasti. Langkah ini mencerminkan pemodelan LP standar tetapi menandai setiap parameter yang tidak pasti.

Rumus
\min c^T x \text{ s.t. } Ax \leq b, \; x \geq 0
2

Konstruksi himpunan ketidakpastian U yang menangkap rentang nilai parameter yang masuk akal tanpa memerlukan distribusi probabilitas. Pilihan umum adalah himpunan kotak (setiap parameter bervariasi secara independen dalam [a_bar - a_hat, a_bar + a_hat]), himpunan elipsoidal (Ben-Tal dan Nemirovski, 1999), dan himpunan anggaran (Bertsimas dan Sim, 2004). Parameter anggaran Gamma membatasi berapa banyak parameter yang dapat secara bersamaan mengambil nilai kasus terburuknya.

Rumus
\mathcal{U} = \{ a_i : a_i = \bar{a}_i + \hat{a}_i \xi_i, \; \|\xi\|_\infty \leq 1 \}
3

Ganti setiap kendala yang tidak pasti dengan padanan robustnya (robust counterpart): mensyaratkan kelayakan untuk setiap realisasi dalam U. Ini mengubah masalah asli menjadi program semi-tak terhingga — tak terhingga banyaknya kendala, satu per elemen U.

Rumus
\max_{a_i \in \mathcal{U}} a_i^T x \leq b_i \quad \forall i
4

Turunkan padanan deterministik yang dapat ditangani (tractable deterministic equivalent). Untuk himpunan ketidakpastian anggaran, padanan robustnya diformulasikan ulang sebagai LP standar atau LP campuran-integer (mixed-integer LP) dengan ukuran serupa, yang dapat dipecahkan dengan pemecah konvensional. Reformulasi kuncinya memperkenalkan variabel bantu yang melinearkan maksimisasi bagian dalam (inner maximization) atas himpunan ketidakpastian.

Rumus
\bar{a}_i^T x + \Gamma_i \max_{\{S: |S| \leq \Gamma_i\}} \sum_{j \in S} \hat{a}_{ij} |x_j| \leq b_i
5

Pecahkan LP yang diformulasikan ulang menggunakan pemecah standar (simplex atau interior-point). Evaluasi solusi: periksa pelanggaran kendala kasus terburuk di seluruh himpunan ketidakpastian, laporkan harga robustnes (peningkatan tujuan relatif terhadap LP nominal), dan lakukan analisis sensitivitas pada anggaran robustnes Gamma.

Kesalahan umum

  • Menetapkan Gamma terlalu tinggi membuat setiap kendala menjadi kasus terburuk secara bersamaan, menghasilkan solusi yang terlalu konservatif dan mahal.
  • Salah menentukan himpunan ketidakpastian (misalnya, mengabaikan struktur korelasi) dapat menyebabkan perlindungan berlebih atau kurang.
  • Mencampuradukkan LP robust dengan LP stokastik: RLP memaksimalkan kinerja kasus terburuk, bukan kinerja yang diharapkan.
  • Mengabaikan laporan harga robustnes — selalu bandingkan tujuan robust dengan tujuan LP nominal untuk mengukur biaya konservatisme.
  • Menerapkan RLP pada masalah dengan variabel integer tanpa beralih ke formulasi campuran-integer robust, yang memerlukan reformulasi berbeda.

Pertanyaan yang sering diajukan

Bagaimana RLP berbeda dari LP Stokastik?

LP Stokastik mengoptimalkan kinerja yang diharapkan mengingat distribusi probabilitas atas skenario, memerlukan pengetahuan distribusi. RLP mengoptimalkan kinerja kasus terburuk atas himpunan ketidakpastian, hanya memerlukan batas — tanpa distribusi probabilitas. RLP lebih disukai ketika distribusi tidak dapat diandalkan; LP stokastik lebih disukai ketika distribusi diperkirakan dengan baik.

Berapa harga robustnes?

Harga robustnes adalah peningkatan nilai tujuan (biaya) solusi robust relatif terhadap solusi LP nominal. Bertsimas dan Sim (2004) membuktikan harga ini tumbuh hanya sebanding dengan akar kuadrat jumlah parameter yang tidak pasti untuk himpunan anggaran, membuat robustnes secara mengejutkan terjangkau.

Apa itu anggaran robustnes Gamma?

Gamma adalah parameter dalam model Bertsimas-Sim yang mengontrol berapa banyak koefisien yang tidak pasti yang diizinkan secara bersamaan mengambil nilai kasus terburuknya. Gamma = 0 mengembalikan LP nominal; Gamma = n melindungi terhadap semua n parameter yang menyimpang sekaligus. Analis biasanya memilih Gamma berdasarkan batas probabilitas pelanggaran yang dapat diterima.

Apakah RLP memerlukan pemecah khusus?

Tidak. Untuk himpunan ketidakpastian kotak dan anggaran, padanan robustnya adalah program linear itu sendiri, yang dapat dipecahkan dengan pemecah LP standar apa pun (CPLEX, Gurobi, HiGHS, dll.). Himpunan elipsoidal memerlukan pemecah program kerucut orde kedua, yang juga didukung secara luas.

Kapan saya harus menggunakan Pemrograman Campuran-Integer Robust (Robust Mixed-Integer Programming) sebagai gantinya?

Jika variabel keputusan harus berupa integer (misalnya, keputusan ya/tidak biner, ukuran lot), padanan robustnya berisi variabel integer dan menjadi Program Campuran-Integer Robust. Pendekatan himpunan ketidakpastian sama, tetapi persyaratan reformulasi dan pemecah berubah sesuai.

Metode terkait

Sumber

  1. Bertsimas, D., Sim, M. (2004). The price of robustness. Operations Research, 52(1), 35–53.

    Buka referensi DOI
    Disalin.
  2. Ben-Tal, A., Nemirovski, A. (1999). Robust solutions of uncertain linear programs. Operations Research Letters, 25(1), 1–13.

    Buka referensi DOI
    Disalin.