Algoritma branch and bound dipakai untuk menyelesaikan masalah optimasi kombinatorial dengan memecah ruang solusi menjadi cabang-cabang dan memangkas cabang yang tidak mungkin menghasilkan solusi terbaik. Panduan langkah demi langkah menyusun algoritma branch and bound ini membahas konsep, langkah penyusunan, dan contoh penerapan.
Apa Itu Algoritma Branch and Bound?
Branch and bound (B&B) adalah paradigma algoritma untuk masalah optimasi diskrit dan kombinatorial. Brute force mengevaluasi semua kemungkinan solusi, sedangkan B&B membagi masalah menjadi subproblem (branch) dan memakai batas (bound) untuk mengeliminasi subproblem yang tidak menjanjikan. Tujuannya menemukan solusi optimal tanpa harus menjelajahi seluruh ruang solusi.
Algoritma ini sering diterapkan pada traveling salesman, knapsack, penjadwalan, dan assignment. Efisiensinya bergantung pada seberapa baik batas bawah (untuk minimasi) atau batas atas (untuk maksimasi) dihitung dan seberapa cepat pencarian memangkas cabang yang tidak perlu.
Konsep Dasar: Branch, Bound, dan Pruning
Dalam B&B, kita membangun pohon pencarian (search tree) di mana setiap simpul merepresentasikan subproblem. Cabang (branch) adalah proses membagi subproblem menjadi subproblem yang lebih kecil. Batas (bound) adalah nilai estimasi terbaik yang mungkin diperoleh dari subproblem tersebut. Jika batas suatu simpul tidak lebih baik dari solusi terbaik yang sudah ditemukan (disebut incumbent), simpul itu dipangkas (pruning) karena tidak akan menghasilkan solusi yang lebih baik.
Pruning menentukan efisiensi B&B. Ada tiga jenisnya: pruning berdasarkan batas (bound pruning), pruning berdasarkan kelayakan (feasibility pruning), dan pruning berdasarkan dominasi (dominance pruning). Ketiganya mengurangi jumlah simpul yang dieksplorasi.
Langkah demi Langkah Menyusun Algoritma Branch and Bound
Berikut panduan sistematis untuk merancang algoritma B&B pada masalah optimasi. Contoh yang dipakai adalah knapsack 0/1: sejumlah barang dengan berat dan nilai, serta tas berkapasitas terbatas. Tujuannya memilih barang untuk memaksimalkan nilai total tanpa melebihi kapasitas.
Langkah 1: Definisikan Masalah dan Representasi Solusi
Rumuskan masalah secara formal. Untuk knapsack 0/1, kita memiliki n barang, masing-masing dengan berat w_i dan nilai v_i, serta kapasitas W. Solusi direpresentasikan sebagai vektor biner x = (x_1, …, x_n) di mana x_i = 1 jika barang i dipilih. Fungsi tujuan: maksimalkan Σ v_i x_i dengan kendala Σ w_i x_i ≤ W.
Langkah 2: Tentukan Strategi Pencarian (Traversal)
Ada dua strategi umum: Breadth-First Search (BFS) dan Depth-First Search (DFS). BFS memakai antrian (queue) dan menjelajahi level demi level, sedangkan DFS memakai stack dan menjelajahi sedalam mungkin sebelum backtrack. DFS lebih hemat memori dan sering dipakai dalam B&B karena dapat menemukan solusi awal dengan cepat. Untuk masalah knapsack, DFS dengan urutan barang berdasarkan rasio nilai/berat menurun dapat mempercepat pruning.
Langkah 3: Rancang Fungsi Batas (Bound Function)
Fungsi batas memberikan estimasi terbaik yang mungkin dicapai dari suatu simpul. Untuk maksimasi, batas atas (upper bound) dihitung dengan mengabaikan kendala integralitas (relaksasi linier). Pada knapsack, batas atas dapat dihitung dengan metode greedy: ambil barang dengan rasio nilai/berat tertinggi lebih dulu, dan jika kapasitas tersisa tidak cukup untuk mengambil seluruh barang, ambil sebagian (fraksi) dari barang tersebut. Batas ini harus admissible, artinya tidak pernah underestimate nilai optimal sebenarnya.
Langkah 4: Inisialisasi Solusi Terbaik (Incumbent)
Mulai dengan solusi awal yang layak (feasible) untuk mendapatkan nilai incumbent. Solusi awal bisa diperoleh dari heuristik greedy. Incumbent menjadi pembanding untuk pruning. Semakin baik incumbent awal, semakin banyak simpul yang dapat dipangkas.
Langkah 5: Kembangkan Aturan Cabang (Branching Rule)
Pada setiap simpul, pilih variabel keputusan yang belum ditetapkan dan buat dua cabang: satu dengan variabel = 1 (ambil barang) dan satu dengan variabel = 0 (tidak ambil). Urutan pemilihan variabel mempengaruhi efisiensi. Memilih variabel dengan rasio tertinggi lebih dulu dapat membantu menemukan solusi baik lebih cepat.
Langkah 6: Terapkan Pruning
Setelah menghitung batas untuk suatu simpul, bandingkan dengan incumbent. Jika batas ≤ incumbent (untuk maksimasi), simpul tersebut tidak perlu dieksplorasi lebih lanjut. Jika simpul tidak layak (misalnya kapasitas terlampaui), pruning juga dilakukan. Terapkan pruning secara konsisten saat menjelajahi pohon.
Langkah 7: Ulangi Hingga Semua Simpul Diproses atau Dipangkas
Lanjutkan proses branching dan bounding secara rekursif atau iteratif hingga tidak ada simpul yang tersisa dalam antrian/stack. Solusi terbaik yang ditemukan selama proses adalah solusi optimal.
Contoh Penerapan pada Knapsack 0/1
Misalkan kita memiliki 4 barang dengan data sebagai berikut:
| Barang | Berat | Nilai | Rasio |
|---|---|---|---|
| A | 2 | 40 | 20 |
| B | 3 | 50 | 16.67 |
| C | 4 | 60 | 15 |
| D | 5 | 70 | 14 |
Kapasitas knapsack W = 7. Kita urutkan barang berdasarkan rasio menurun: A, B, C, D.
Langkah-langkah B&B:
- Inisialisasi incumbent = 0 (atau gunakan greedy: ambil A (2,40), B (3,50), total berat 5, nilai 90; tambah C? berat 9 > 7, jadi ambil fraksi? Untuk incumbent awal, kita bisa ambil solusi integer: A+B = 90, atau A+C = 100 dengan berat 6, atau B+C = 110 dengan berat 7. Jadi incumbent = 110 dengan B dan C).
- Mulai dari simpul akar (semua variabel bebas). Hitung batas atas: ambil A (2,40), B (3,50), sisa kapasitas 2, ambil 2/4 dari C (nilai 30). Total batas = 40+50+30 = 120.
- Cabang pada barang A: x_A=1. Berat terpakai 2, nilai 40. Batas: ambil B (3,50), sisa 2, ambil 2/4 C (30) => total 120 masih.
- Cabang pada B: x_B=1. Berat 5, nilai 90. Batas: sisa 2, ambil 2/4 C (30) => total 120.
- Cabang pada C: x_C=1. Berat 9 > 7, tidak layak. Pruning.
- Cabang pada C: x_C=0. Berat 5, nilai 90. Batas: sisa 2, ambil 2/5 D (28) => total 118. Karena 118 > incumbent 110, lanjut.
- Cabang pada D: x_D=1. Berat 10 > 7, pruning.
- Cabang pada D: x_D=0. Berat 5, nilai 90. Batas = 90 ≤ incumbent 110, pruning.
- Kembali ke simpul B=0: x_A=1, x_B=0. Berat 2, nilai 40. Batas: ambil C (4,60), sisa 1, ambil 1/5 D (14) => total 40+60+14=114 > 110, lanjut.
- Cabang pada C: x_C=1. Berat 6, nilai 100. Batas: sisa 1, ambil 1/5 D (14) => total 114 > 110.
- Cabang pada D: x_D=1. Berat 11 > 7, pruning.
- Cabang pada D: x_D=0. Berat 6, nilai 100. Batas = 100 ≤ 110, pruning.
- Kembali ke simpul C=0: x_A=1, x_B=0, x_C=0. Berat 2, nilai 40. Batas: ambil D (5,70) => total 110 ≤ incumbent 110, pruning.
- Kembali ke simpul A=0: x_A=0. Batas: ambil B (3,50), C (4,60) => total 110 ≤ incumbent, pruning.
Solusi optimal ditemukan: x_B=1, x_C=1 dengan nilai 110. Proses di atas menunjukkan bagaimana batas dan pruning mengurangi jumlah simpul yang dievaluasi.
Tips Optimasi dan Catatan Implementasi
Untuk meningkatkan kinerja B&B, pertimbangkan hal berikut:
- Pilih strategi pencarian yang sesuai: DFS untuk memori terbatas, BFS untuk eksplorasi paralel.
- Gunakan fungsi batas yang ketat (tight) namun tetap admissible. Batas yang lebih ketat mempercepat pruning.
- Terapkan heuristik untuk mendapatkan incumbent awal yang baik, misalnya dengan algoritma greedy.
- Urutkan variabel berdasarkan rasio atau kepentingan untuk mempercepat penemuan solusi.
- Implementasikan struktur data efisien seperti priority queue untuk best-first search.
Dalam praktiknya, B&B sering dikombinasikan dengan teknik lain seperti divide and conquer untuk memecah masalah, atau dengan algoritma Floyd-Warshall untuk masalah jalur terpendek. Pemilihan bahasa pemrograman juga mempengaruhi, seperti dibahas dalam perbandingan bahasa pemrograman untuk belajar algoritma.
Untuk pengembangan antarmuka pengguna yang efisien, Anda dapat membaca artikel tentang mengukur beban kognitif antarmuka. Jika Anda tertarik memulai dengan jQuery, ada tips praktis untuk pemula.
Untuk memperkaya wawasan, situs berita indowarta menyajikan berita berdasarkan fakta dengan penulis berpengalaman, sehingga Anda dapat mempercayai informasinya.
Ringkasan
Menyusun algoritma branch and bound memerlukan pemahaman masalah, perancangan fungsi batas yang baik, dan penerapan pruning yang tepat. Dengan mengikuti langkah-langkah di atas, Anda dapat mengimplementasikan B&B untuk berbagai masalah optimasi kombinatorial. Latihan dengan contoh seperti knapsack akan membantu mengasah keterampilan ini.
Pertanyaan yang Sering Diajukan
Apa perbedaan branch and bound dengan backtracking?
Backtracking mencari semua solusi yang layak dan berhenti ketika menemukan solusi, sedangkan branch and bound digunakan untuk optimasi dan menggunakan batas untuk memangkas cabang yang tidak menjanjikan solusi lebih baik.
Apakah branch and bound selalu menemukan solusi optimal?
Ya, selama fungsi batas yang digunakan admissible (tidak pernah underestimate untuk minimasi atau overestimate untuk maksimasi) dan semua simpul potensial dievaluasi atau dipangkas dengan benar, B&B menjamin solusi optimal.
Bagaimana cara memilih antara BFS dan DFS dalam branch and bound?
DFS lebih baik jika memori terbatas karena tidak menyimpan banyak simpul, dan sering menemukan solusi awal dengan cepat. BFS atau best-first search dapat lebih efisien jika kita ingin menjelajahi simpul yang paling menjanjikan terlebih dahulu, tetapi membutuhkan memori lebih besar.
