Cabang dan Batas
- Diperkenalkan oleh
- Ailsa Land & Alison Doig
- Tahun
- 1960
- Jenis
- Exact combinatorial optimization algorithm
- Keluarga
- Mathematical programming
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Branch and Bound adalah algoritma eksak sistematis untuk masalah optimasi kombinatorial dan integer, yang diperkenalkan oleh Ailsa Land dan Alison Doig pada tahun 1960.
Algoritma ini mengorganisasi ruang pencarian sebagai pohon submasalah, menggunakan batas atas yang diturunkan dari relaksasi untuk memangkas cabang yang tidak dapat meningkatkan solusi terbaik yang diketahui, dan menjamin penemuan solusi integer optimal secara global. Algoritma ini merupakan tulang punggung pemecah masalah pemrograman campuran integer modern yang digunakan dalam riset operasi, logistik, penjadwalan, dan desain teknik.
Intuisi di balik metode
Bayangkan mencari item bernilai tertinggi yang tersembunyi di labirin ruangan yang luas. Alih-alih memeriksa setiap ruangan, Anda memperkirakan nilai maksimum yang dapat dicapai dari setiap koridor sebelum memasukinya. Jika batas atas ini lebih rendah dari item terbaik yang sudah Anda miliki, Anda melewati seluruh koridor tanpa melihat ke dalamnya. Branch and Bound bekerja dengan cara yang sama: memecah masalah menjadi bagian-bagian yang lebih kecil, menghitung batas atas optimis untuk setiap bagian, dan segera membuang bagian mana pun yang terbukti tidak dapat mengalahkan solusi terbaik saat ini.
Sejarah
Land dan Doig menerbitkan makalah dasar Branch and Bound di Econometrica pada tahun 1960, membingkainya sebagai metode otomatis untuk pemrograman diskrit. Little dkk. (1963) menerapkan teknik ini pada masalah pedagang keliling, memperkuat perannya dalam optimasi kombinatorial. Dakin (1965) memperkenalkan percabangan relaksasi LP, bentuk yang paling umum digunakan saat ini. Dekade berikutnya menyaksikan integrasi bidang potong (branch-and-cut) dan generasi kolom (branch-and-price), menjadikan Branch and Bound sebagai mesin di dalam semua pemecah pemrograman integer komersial utama.
Kapan digunakan
Gunakan Branch and Bound ketika Anda harus menemukan solusi yang terbukti optimal untuk program linear campuran integer atau integer murni dan tidak dapat menerima jawaban perkiraan. Algoritma ini mengasumsikan masalah dapat diformulasikan dengan relaksasi linear (atau cembung) yang memberikan batas yang berguna. Algoritma ini kurang cocok untuk instansi yang sangat besar di mana pohon enumerasi meledak, untuk program integer non-linear tanpa relaksasi yang ketat, atau untuk pengaturan waktu nyata di mana waktu komputasi sangat terbatas. Dalam kasus seperti itu, heuristik atau metaheuristik mungkin lebih disukai.
Batasan dan pertimbangan
- Kompleksitas kasus terburuk bersifat eksponensial; pada instansi yang terstruktur buruk, pohon dapat tumbuh sangat besar.
- Kinerja sangat sensitif terhadap pilihan variabel percabangan dan strategi pemilihan node.
- Membutuhkan relaksasi yang dapat ditangani yang memberikan batas atas yang bermakna; batas yang lemah menghasilkan pemangkasan minimal.
- Persyaratan memori bisa cukup besar ketika banyak node terbuka harus disimpan secara bersamaan.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menjamin optimalitas global untuk program integer dan kombinatorial.
- Secara dramatis mengurangi pencarian melalui pemangkasan berbasis batas — seringkali hanya sebagian kecil dari pohon enumerasi penuh yang dieksplorasi.
- Fleksibel: dapat menggabungkan bidang potong (branch-and-cut) atau batas heuristik (branch-and-price) untuk efisiensi lebih lanjut.
- Diimplementasikan secara luas dalam pemecah komersial yang matang (CPLEX, Gurobi) dan alat sumber terbuka (GLPK, CBC).
Penerapan
- Penjadwalan kru maskapai dan penugasan armada dalam riset operasi.
- Desain jaringan rantai pasokan dan masalah lokasi fasilitas.
- Tata letak sirkuit VLSI dan alokasi register dalam rekayasa komputer.
- Prediksi struktur protein dan perakitan genom dalam biologi komputasi.
- Optimasi portofolio keuangan dengan kendala kardinalitas.
Cara kerjanya
Cara kerjanya
Algoritma dimulai dengan menyelesaikan versi relaksasi dari masalah — biasanya relaksasi LP — yang mengabaikan kendala integritas. Relaksasi ini menghasilkan batas atas pada nilai optimal yang sebenarnya karena setiap solusi integer yang layak juga layak dalam relaksasi. Jika solusi relaksasi secara kebetulan bernilai integer, masalah tersebut diselesaikan segera.
Rumus
\text{Solve LP relaxation: } z^* = \max\{\mathbf{c}^\top \mathbf{x} \mid A\mathbf{x} \leq \mathbf{b},\, \mathbf{x} \geq 0\}Ketika solusi relaksasi mengandung variabel fraksional, algoritma mempartisi daerah layak dengan menambahkan kendala komplementer yang memaksa variabel tersebut menjadi nilai lantai atau langit-langitnya. Setiap partisi menciptakan node anak baru di pohon pencarian, secara efektif membagi satu submasalah menjadi dua submasalah yang lebih kecil dengan domain yang lebih ketat.
Rumus
\text{Select fractional variable } x_j \notin \mathbb{Z}\text{; create sub-problems: } x_j \leq \lfloor x_j^* \rfloor \text{ and } x_j \geq \lceil x_j^* \rceilSetiap node aktif menerima batas relaksasi LP-nya sendiri. Node yang batasnya tidak melebihi solusi integer terbaik yang ditemukan sejauh ini — yang disebut incumbent — tidak dapat berisi solusi yang lebih baik, sehingga dipangkas. Batas yang ketat sangat penting: semakin ketat batasnya, semakin sedikit node yang perlu dieksplorasi.
Rumus
\text{Compute bound } UB_k \text{ for node } k\text{; prune if } UB_k \leq z_{\text{inc}}Sebuah node dinyatakan fathomed (ditutup secara permanen) dalam tiga kondisi: relaksasinya tidak layak, batasnya tidak lebih baik dari incumbent, atau solusi relaksasinya sudah layak integer. Dalam kasus terakhir, incumbent diperbarui jika solusi baru memperbaikinya. Algoritma berakhir ketika semua node telah fathomed, pada saat itu incumbent adalah optimum global.
Rumus
\text{Fathom node } k \text{ if infeasible, or } UB_k \leq z_{\text{inc}}, \text{ or } \mathbf{x}^*_k \in \mathbb{Z}^n\text{; update } z_{\text{inc}} \leftarrow \max(z_{\text{inc}}, z_k)Kesalahan umum
- Memilih variabel percabangan yang buruk (misalnya, selalu melakukan percabangan pada variabel fraksional pertama) sering kali menghasilkan pohon yang dalam, tidak seimbang, dan konvergensi yang lambat.
- Mengabaikan ketidaksetaraan yang valid (bidang potong) berarti kehilangan kesempatan untuk memperketat batas relaksasi secara signifikan.
- Penghentian prematur dengan celah sub-optimalitas yang tidak dilaporkan sebagai demikian dapat menyesatkan praktisi untuk memperlakukan solusi yang mendekati optimal sebagai solusi yang tepat.
- Menerapkan Branch and Bound pada relaksasi non-linear atau non-cembung tanpa konveksifikasi khusus dapat menghasilkan batas yang tidak valid dan hasil yang salah.
Pertanyaan yang sering diajukan
Bagaimana Branch and Bound berbeda dari enumerasi menyeluruh?
Enumerasi menyeluruh mengevaluasi setiap solusi integer yang layak secara eksplisit, yang secara komputasi tidak mungkin dilakukan untuk masalah besar. Branch and Bound menghindarinya dengan menghitung batas atas berbasis relaksasi di setiap node pohon pencarian dan memangkas seluruh subpohon kapan pun batas tidak dapat melebihi solusi terbaik yang sudah ditemukan. Dalam praktiknya, hanya sebagian kecil dari pohon yang pernah diperiksa.
Apa peran relaksasi LP dalam Branch and Bound?
Relaksasi LP menghilangkan kendala integritas, membuat masalah dapat diselesaikan dalam waktu polinomial oleh metode simpleks atau titik interior. Nilai optimalnya berfungsi sebagai batas atas untuk submasalah integer yang sesuai. Ketika batas ini ketat — dekat dengan optimum integer yang sebenarnya — lebih sedikit cabang yang perlu dieksplorasi. Relaksasi yang lebih ketat, yang sering dicapai dengan menambahkan ketidaksetaraan yang valid, secara dramatis mempercepat algoritma secara keseluruhan.
Kapan saya harus menggunakan Branch and Bound dibandingkan dengan metaheuristik seperti algoritma genetik?
Pilih Branch and Bound ketika Anda memerlukan sertifikat optimalitas dan mampu menanggung waktu komputasi. Algoritma ini ideal untuk masalah berukuran sedang dengan relaksasi LP yang terstruktur dengan baik. Metaheuristik lebih disukai ketika masalahnya sangat besar, tidak memiliki relaksasi yang berguna, atau harus diselesaikan dalam anggaran waktu yang ketat di mana solusi yang mendekati optimal dapat diterima. Banyak praktisi menggabungkan keduanya: gunakan Branch and Bound dengan toleransi celah penghentian dini.
Metode terkait
Sumber
Land, A. H., & Doig, A. G. (1960). An automatic method of solving discrete programming problems. Econometrica, 28(3), 497–520.
Buka referensi DOIDisalin.