Dekomposisi Benders
- Diperkenalkan oleh
- Jacques F. Benders
- Tahun
- 1962
- Jenis
- algorithm
- Keluarga
- Optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Dekomposisi Benders, diperkenalkan oleh Jacques F. Benders pada tahun 1962, adalah kerangka kerja algoritmik yang ampuh untuk memecahkan masalah pemrograman campuran-bilangan bulat (MIP) berskala besar.
Metode ini mendekomposisi masalah menjadi masalah utama (mengendalikan variabel yang mempersulit) dan submasalah (menangani variabel yang tersisa), menggunakan bidang potong (cutting planes) yang dihasilkan dari informasi dual submasalah untuk secara iteratif memperketat masalah utama.
Intuisi di balik metode
Metode ini mengakui bahwa variabel tertentu (disebut variabel yang mempersulit) membuat masalah sulit untuk diselesaikan secara langsung, sementara variabel yang tersisa dapat ditangani dengan mudah. Dengan memperbaiki nilai variabel yang mempersulit dan menyelesaikan submasalah yang dihasilkan untuk variabel yang tersisa, algoritma memperoleh informasi dual yang menghasilkan bidang potong. Potongan-potongan ini memperkuat masalah utama, yang kemudian memilih nilai yang lebih baik untuk variabel yang mempersulit. Proses iteratif ini berlanjut hingga konvergensi. Wawasan kuncinya adalah bahwa dekomposisi mengubah masalah yang sulit menjadi banyak submasalah yang lebih mudah ditambah masalah utama yang lebih kecil.
Sejarah
Benders memperkenalkan metode dekomposisinya pada tahun 1962 untuk mempartisi masalah pemrograman campuran-bilangan bulat. Geoffrion menggeneralisasi pendekatan tersebut pada tahun 1972 untuk menangani masalah nonlinier, menciptakan kerangka kerja yang digunakan dalam aplikasi modern. Metode ini mendapatkan perhatian dengan kemajuan dalam kekuatan komputasi dan pemecah. Perkembangan terbaru meliputi bidang potong Benders kombinatorial, varian multi-potong, dan integrasi dengan algoritma branch-and-cut modern, menjadikannya teknik utama dalam optimasi tingkat lanjut.
Kapan digunakan
Terapkan Dekomposisi Benders pada masalah pemrograman campuran-bilangan bulat berskala besar, terutama yang memiliki struktur khusus (tangga, blok-sudut) yang dapat dieksploitasi oleh dekomposisi. Metode ini sangat efektif untuk masalah di mana metode solusi langsung secara komputasi tidak memungkinkan. Gunakan untuk masalah lokasi fasilitas, perencanaan produksi, dan desain jaringan. Untuk masalah kecil atau yang tidak memiliki struktur khusus, pemecah MIP langsung mungkin lebih efisien.
Batasan dan pertimbangan
- Memerlukan struktur masalah yang sesuai untuk dekomposisi; mungkin tidak efisien pada masalah yang sepenuhnya umum
- Pembuatan bidang potong dapat menciptakan banyak kendala, berpotensi memperlambat penyelesaian masalah utama
- Konvergensi bisa lambat, membutuhkan banyak iterasi dengan toleransi yang ketat
- Kompleksitas implementasi lebih besar daripada metode solusi langsung
- Masalah stabilitas numerik dimungkinkan dengan koefisien bidang potong
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Secara efektif memecahkan program campuran-bilangan bulat berskala besar yang tidak dapat diatasi dengan metode standar
- Secara alami mengeksploitasi struktur masalah dengan bentuk blok-sudut atau tangga
- Menyediakan batas bawah dan atas, memungkinkan jaminan kualitas sebelum konvergensi
- Dekomposisi memungkinkan penyelesaian paralel submasalah independen
- Dekomposisi Benders Umum menangani submasalah nonlinier, memperluas penerapan
Penerapan
- Lokasi fasilitas: menentukan lokasi gudang dan alokasi produk untuk meminimalkan total biaya
- Perencanaan produksi: penjadwalan produksi di berbagai fasilitas dengan kendala inventaris dan kapasitas
- Perutean kendaraan: perencanaan rute pengiriman dengan keputusan komposisi armada
- Desain jaringan: pemilihan fasilitas, tautan, dan kapasitas dalam jaringan telekomunikasi atau transportasi
- Sistem tenaga: keputusan dispatch ekonomi dan komitmen unit dengan kendala transmisi
- Optimasi rantai pasokan: mengoordinasikan pengadaan, produksi, dan distribusi di seluruh jaringan
Cara kerjanya
Cara kerjanya
Siapkan masalah utama hanya dengan variabel yang mempersulit dan kendala placeholder. Inisialisasi batas atas dan bawah; batas bawah dari masalah utama, batas atas dari solusi yang layak.
Perbaiki variabel yang mempersulit pada nilai mereka saat ini dan selesaikan submasalah untuk variabel yang tersisa. Jika tidak layak, hasilkan bidang potong kelayakan (feasibility cut); jika layak, ekstrak informasi dual dan hasilkan bidang potong optimalitas (optimality cut).
Tambahkan bidang potong ke masalah utama yang mencerminkan wawasan submasalah. Selesaikan kembali masalah utama dan ulangi hingga celah antara batas atas dan bawah dapat diterima.
Kesalahan umum
- Memilih nilai yang buruk untuk variabel yang mempersulit, menghasilkan submasalah yang sulit
- Gagal mengimplementasikan teknik stabilisasi (daerah kepercayaan, metode tingkat) untuk mempercepat konvergensi
- Pembuatan bidang potong yang lemah yang tidak cukup memperkuat masalah utama
- Mengabaikan pra-pemrosesan dan permulaan hangat (warm starts) dari solusi yang layak
Pertanyaan yang sering diajukan
Apa itu variabel yang mempersulit dan bagaimana cara mengidentifikasinya?
Variabel yang mempersulit adalah variabel yang nilainya, ketika diperbaiki, membuat masalah yang tersisa mudah diselesaikan. Variabel tersebut diidentifikasi dengan memeriksa struktur masalah: variabel yang muncul dalam kendala yang menghubungkan submasalah yang seharusnya independen, atau variabel diskrit dalam masalah yang seharusnya kontinu, adalah kandidat umum.
Apa perbedaan antara bidang potong kelayakan dan bidang potong optimalitas?
Bidang potong kelayakan dihasilkan ketika submasalah tidak layak, menghilangkan nilai variabel yang mempersulit yang tidak layak dari masalah utama. Bidang potong optimalitas menggabungkan informasi dual dari submasalah yang layak untuk meningkatkan perkiraan tujuan masalah utama.
Bagaimana Dekomposisi Benders menjamin konvergensi?
Bidang potong kelayakan dan optimalitas memastikan bahwa relaksasi masalah utama memberikan batas bawah yang valid. Batas atas berasal dari solusi yang layak untuk masalah lengkap. Ketika batas-batas konvergen dalam toleransi, optimalitas dijamin. Konvergensi bersifat terhingga untuk masalah bilangan bulat yang terbatas.
Kapan Dekomposisi Benders lebih disukai daripada menyelesaikan masalah secara langsung dengan pemecah MIP?
Dekomposisi Benders lebih disukai ketika masalahnya besar, memiliki struktur khusus yang dapat dieksploitasi oleh dekomposisi, atau pemecah langsung kehabisan waktu. Untuk masalah kecil atau yang tidak memiliki struktur, pemecah MIP modern seringkali lebih cepat dan lebih sederhana.
Metode terkait
Sumber
Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4(1), 238-252.
Buka referensi DOIDisalin.Geoffrion, A. M. (1972). Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10(4), 237-260.
Buka referensi DOIDisalin.