Generasi Kolom (Dantzig-Wolfe)
- Diperkenalkan oleh
- George B. Dantzig and Philip Wolfe
- Tahun
- 1960
- Jenis
- algorithm
- Keluarga
- Optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Generasi Kolom, dikembangkan oleh George B. Dantzig dan Philip Wolfe pada tahun 1960, adalah teknik optimasi yang ampuh untuk menyelesaikan masalah pemrograman linier skala besar dengan struktur khusus.
Juga dikenal sebagai Dekomposisi Dantzig-Wolfe, metode ini menguraikan masalah menjadi masalah induk (terbatas pada subset variabel/kolom) dan submasalah penetapan harga (mengidentifikasi variabel baru), secara iteratif meningkatkan solusi dengan hanya memperkenalkan kolom yang relevan.
Intuisi di balik metode
Metode ini mengakui bahwa banyak masalah optimasi besar memiliki struktur khusus: banyak variabel tetapi sedikit kendala yang benar-benar penting, atau submasalah yang dapat didekomposisi secara alami. Alih-alih menyelesaikan masalah penuh dengan semua kemungkinan variabel, generasi kolom hanya mempertahankan subset kecil dari kolom (variabel) yang menjanjikan. Masalah penetapan harga, yang diselesaikan menggunakan biaya tereduksi dan struktur masalah, mengidentifikasi kolom baru yang meningkatkan solusi induk. Dengan secara iteratif menambahkan kolom yang paling menjanjikan, algoritma membangun solusi secara efisien, menghindari beban komputasi penanganan semua kolom secara bersamaan.
Sejarah
Dantzig dan Wolfe memperkenalkan prinsip dekomposisi untuk program linier pada tahun 1960, membangun dasar teoretis. Gilmore dan Gomory (1961) menerapkannya pada masalah pemotongan stok, menunjukkan kekuatan praktis. Metode ini mendapatkan perhatian untuk masalah perutean kendaraan dan penjadwalan pada tahun 1980-an-90-an. Integrasi dengan branch-and-bound, menciptakan algoritma branch-and-price, memperluas penerapan ke pemrograman integer. Aplikasi modern termasuk penjadwalan kru maskapai, perutean kapal, dan optimasi logistik skala besar.
Kapan digunakan
Terapkan generasi kolom saat menyelesaikan program linier skala besar dengan struktur khusus, terutama ketika jumlah variabel sangat besar tetapi subset kecil mendominasi solusi optimal. Ini ideal untuk masalah pemotongan stok, perutean kendaraan, penjadwalan kru, dan pengemasan bin. Gunakan ketika struktur masalah memungkinkan solusi submasalah penetapan harga yang efisien. Untuk masalah tanpa struktur yang dapat dieksploitasi atau ukuran sedang, pemecah LP standar lebih praktis.
Batasan dan pertimbangan
- Memerlukan struktur masalah yang memungkinkan solusi submasalah penetapan harga yang efisien
- Konvergensi bisa lambat, terutama di dekat optimalitas (efek tailing-off)
- Solusi submasalah penetapan harga harus andal dan efisien, atau keuntungan efisiensi akan hilang
- Kompleksitas implementasi lebih besar daripada metode LP standar
- Masalah stabilitas numerik dengan nilai dual dan biaya tereduksi yang besar
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menyelesaikan masalah skala besar yang tidak dapat diatasi oleh metode standar karena ledakan kolom
- Mengeksploitasi struktur masalah untuk menghasilkan hanya kolom yang relevan
- Memberikan batas kualitas solusi selama iterasi
- Secara alami cocok untuk masalah dengan substruktur khusus (submasalah identik, simetri)
- Dapat diintegrasikan dengan branch-and-bound untuk program integer (branch-and-price)
Penerapan
- Masalah pemotongan stok: meminimalkan limbah saat memotong bahan menjadi ukuran yang dibutuhkan
- Perutean kendaraan: mengoptimalkan rute untuk pengiriman dan transportasi dengan jendela waktu dan batasan kapasitas
- Penjadwalan kru: menugaskan anggota kru ke penerbangan atau shift meminimalkan total biaya
- Pengemasan bin: mengemas barang ke dalam wadah secara efisien untuk meminimalkan limbah dan jumlah wadah
- Penyusunan jadwal: menjadwalkan pekerja di berbagai shift dengan menghormati batasan ketersediaan dan preferensi
- Perencanaan maskapai: penjadwalan penerbangan, penugasan kru, dan koordinasi pemeliharaan pesawat
Cara kerjanya
Cara kerjanya
Mulai dengan masalah induk terbatas yang hanya berisi subset kolom yang diperlukan untuk solusi layak awal.
Selesaikan dual dari masalah induk terbatas saat ini menggunakan tabel simplex. Identifikasi biaya tereduksi dan siapkan submasalah penetapan harga untuk menemukan variabel dengan biaya tereduksi negatif (untuk minimisasi).
Selesaikan submasalah penetapan harga menggunakan struktur khususnya. Jika kolom baru dengan biaya tereduksi negatif ditemukan, tambahkan ke masalah induk dan ulangi. Jika tidak ada kolom yang membaik, solusi saat ini optimal.
Kesalahan umum
- Memilih algoritma submasalah penetapan harga yang tidak efisien, meniadakan keuntungan efisiensi dari generasi kolom
- Gagal mengenali struktur masalah yang dapat didekomposisi, mengakibatkan kinerja buruk
- Deteksi konvergensi yang tidak memadai atau toleransi yang terlalu ketat, membuang iterasi
- Tidak mengimplementasikan teknik stabilisasi untuk mengatasi efek tailing-off
Pertanyaan yang sering diajukan
Apa itu masalah penetapan harga dalam generasi kolom dan bagaimana hubungannya dengan biaya tereduksi?
Masalah penetapan harga mengidentifikasi variabel baru (kolom) dengan biaya tereduksi negatif yang meningkatkan solusi induk. Nilai biaya tereduksi berasal dari dual masalah induk terbatas dan memandu pencarian dalam submasalah penetapan harga.
Mengapa generasi kolom lebih baik daripada menyelesaikan masalah penuh dengan semua kolom?
Dalam banyak masalah, jumlah kolom potensial bersifat eksponensial atau tak terbatas, membuatnya tidak mungkin untuk menghitung semuanya. Generasi kolom menghasilkan hanya kolom yang diperlukan sesuai permintaan, secara drastis mengurangi beban komputasi.
Apa itu efek tailing-off dan bagaimana cara mengatasinya?
Tailing-off terjadi ketika generasi kolom membuat kemajuan lambat di dekat optimalitas, menghasilkan banyak kolom dengan peningkatan minimal. Teknik stabilisasi (penghalusan dual, metode wilayah kepercayaan, strategi pemotongan) mengurangi dampaknya.
Bagaimana branch-and-price memperluas generasi kolom ke pemrograman integer?
Branch-and-price menggabungkan generasi kolom dengan branch-and-bound: di setiap node, generasi kolom menyelesaikan relaksasi LP, dan keputusan percabangan selanjutnya membatasi masalah ketika solusi LP bersifat fraksional.
Metode terkait
Sumber
Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.
Buka referensi DOIDisalin.Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.
Buka referensi DOIDisalin.