🧮
Desain dan Analisis Algoritma

Paradigma Branch and Bound

Optimisasi · State-Space Tree · Bounding

Fokus
Optimization
TSP, Knapsack, Assignment
Teknik
Branch
Bangun cabang solusi
Teknik
Bound
Buang cabang yang tidak optimal
Definisi & Intuisi

Apa itu Branch and Bound?

Branch and Bound (B&B) adalah paradigma desain algoritma untuk masalah optimisasi diskrit & kombinatorial. Algoritma ini mengeksplorasi state-space tree dari semua solusi kandidat dan menggunakan fungsi bound untuk membuang cabang yang tidak bisa mengalahkan solusi terbaik saat ini. [web:101][web:102]

Mirip dengan backtracking karena sama‑sama memakai tree, tetapi: [web:94][web:97]

  • • Dipakai khusus untuk optimization problems (minimisasi/maksimisasi biaya). [web:94][web:101]
  • • Setiap node punya nilai bound (lower/upper bound) dari solusi terbaik yang mungkin dari node itu. [web:102]
  • • Node yang bound‑nya lebih buruk dibanding solusi terbaik saat ini → dipruning. [web:102][web:99]

Istilah Kunci

  • Branch: memecah masalah menjadi submasalah (node anak) dengan menambahkan keputusan baru (misal, pilih item, pilih kota berikutnya). [web:97][web:102]
  • Bound: nilai batas optimis (atau pesimis) untuk solusi terbaik yang mungkin dari node tersebut. [web:101][web:102]
  • Promising node: node yang bound‑nya masih berpotensi menghasilkan solusi lebih baik daripada solusi terbaik saat ini. [web:102][web:99]
B&B vs Backtracking

Apa Bedanya dengan Backtracking?

Keduanya memakai state-space tree dan bisa memakai DFS, tetapi orientasi dan fungsi utamanya berbeda. [web:95][web:98][web:101]

Aspek Backtracking Branch and Bound
Tipe masalah Decision / feasibility (ada solusi valid atau tidak). [web:95][web:101] Optimization (cari solusi terbaik menurut fungsi objektif). [web:95][web:101]
Fungsi utama Feasibility function – cek solusi parsial valid/tidak. [web:98][web:101] Bounding function – hitung batas terbaik/terburuk yang mungkin. [web:98][web:101]
Tujuan pruning Buang cabang yang tidak bisa memberi solusi valid. [web:101] Buang cabang yang tidak bisa mengalahkan solusi terbaik saat ini. [web:101][web:102]
Traversal Umumnya DFS. [web:95][web:98] Bisa DFS, BFS, atau best‑first (prio queue berdasarkan bound). [web:99][web:102]
Komponen Utama

Elemen dalam Algoritma Branch and Bound

1. Representasi Solusi

Tentukan bagaimana solusi parsial direpresentasikan dalam node state-space tree (misal: subset item, urutan kota yang sudah dikunjungi). [web:97][web:102]

Contoh: di TSP, node menyimpan urutan kota yang sudah dikunjungi dan biayanya. [web:96][web:100]

2. Fungsi Bound

Hitung lower/upper bound untuk nilai objektif terbaik yang mungkin dari node tersebut. [web:101][web:102]

Bound harus mudah dihitung dan cukup ketat agar pruning efektif. [web:102][web:99]

3. Strategi Ekspansi

Tentukan node mana yang diekspansi berikutnya: FIFO (BFS), LIFO (DFS), atau best‑bound (LC – least cost). [web:99][web:96]

LC Branch and Bound memakai priority queue berdasarkan bound terendah/tertinggi. [web:99][web:101]

Contoh — 0/1 Knapsack

Branch and Bound untuk 0/1 Knapsack

Masalah 0/1 Knapsack: pilih subset item dengan bobot wᵢ dan nilai vᵢ untuk memaksimalkan total nilai, dengan total berat ≤ kapasitas W. [web:97][web:96]

Ide Branch

  • • Urutkan item menurut rasio vᵢ/wᵢ (seperti greedy fractional knapsack). [web:102]
  • • Setiap level k: cabang “ambil item k” atau “tidak ambil item k”. [web:97]
  • • Node menyimpan (nilai saat ini, berat saat ini, indeks item berikutnya). [web:97]

Ide Bound

Bound atas (upper bound) dihitung dengan mengisi sisa kapasitas W secara greedy seperti fractional knapsack → memberikan estimasi nilai maksimum yang mungkin. [web:97][web:102]

// Sketsa node untuk B&B Knapsack (maksimisasi) struct Node: level // indeks item terakhir diproses profit // nilai total saat ini weight // berat total saat ini bound // upper bound maximal profit dari node ini // bound dihitung dengan mengisi knapsack sisa // menggunakan fractional knapsack (heuristik)
Pruning pada Knapsack

Node Mana yang Dipruning?

  • • Jika berat node > W → node tidak feasible → prune. [web:97]
  • • Jika bound(node) ≤ profit terbaik saat ini → node tidak promising → prune. [web:99][web:102]
  • • Hanya node promising yang dimasukkan ke queue untuk diekspansi. [web:97][web:99]

Dengan strategi ini, Branch and Bound menghindari mengeksplorasi banyak kombinasi subset yang sudah pasti tidak akan memberikan nilai lebih baik dari solusi terbaik yang sudah ditemukan. [web:97][web:99]

Sketsa Algoritma (LC Branch and Bound)

// LC Branch and Bound untuk 0/1 Knapsack bestProfit ← 0 PQ ← priority queue diurutkan menurun berdasar bound buat rootNode dengan level = -1, profit = 0, weight = 0 rootNode.bound ← hitungBound(rootNode) PQ.push(rootNode) while PQ tidak kosong: node ← PQ.pop() // node dengan bound tertinggi if node.bound ≤ bestProfit: continue // tidak menjanjikan // branch 1: ambil item berikutnya child1 ← node dengan level+1, tambah weight & profit if child1.weight ≤ W and child1.profit > bestProfit: bestProfit ← child1.profit child1.bound ← hitungBound(child1) if child1.bound > bestProfit: PQ.push(child1) // branch 2: tidak ambil item berikutnya child2 ← node dengan level+1, tanpa menambah weight/profit child2.bound ← hitungBound(child2) if child2.bound > bestProfit: PQ.push(child2)
Contoh — TSP

Branch and Bound untuk Traveling Salesman Problem

Travelling Salesman Problem (TSP): diberikan n kota dan biaya perjalanan antar kota, cari tour dengan biaya minimum yang mengunjungi setiap kota tepat sekali dan kembali ke kota asal. [web:94][web:100]

Branch and Bound mengeksplorasi tree dimana node merepresentasikan tour parsial (urutan kota yang sudah dikunjungi), dan bound dihitung dari biaya minimum yang mungkin untuk melengkapi tour tersebut. [web:94][web:102]

Ide Bound TSP (matriks biaya)

  • • Representasi dengan matriks biaya C[i][j]. [web:97]
  • • Lakukan row reduction dan column reduction untuk mendapatkan lower bound awal. [web:97]
  • • Setiap kali memilih edge (i→j) untuk tour, perbarui matriks dan tambahkan nilai reduksi ke bound. [web:97][web:102]
  • • Jika lower bound node ≥ biaya tour terbaik saat ini → prune. [web:94][web:97]

Intuisi

Row/column reduction memberi kita “optimistic estimate” dari biaya minimal yang diperlukan untuk menyelesaikan tour dari node tertentu. [web:97][web:102]

Dengan demikian, B&B untuk TSP dapat menghindari eksplorasi mayoritas permutasi tour (yang jumlahnya n!), meski tetap eksponensial pada worst-case. [web:94][web:100]

Analisis & Karakteristik

Kompleksitas Branch and Bound

Secara teori, Branch and Bound tetap memiliki worst-case kompleksitas eksponensial, karena dalam kasus terburuk tidak ada cabang yang dapat dipruning. [web:97][web:101]

Namun, dalam praktik, dengan bounding function yang baik, B&B dapat memangkas sangat banyak node dan menyelesaikan instance berukuran menengah jauh lebih cepat dibanding enumerasi brute force murni. [web:97][web:102]

Kelebihan

  • • Memberikan solusi optimal (bukan hanya heuristik). [web:101][web:102]
  • • Dapat berhenti lebih awal jika semua node tersisa memiliki bound lebih buruk dari solusi saat ini. [web:102]
  • • Fleksibel: bisa digabung dengan heuristik untuk memperbaiki bound dan urutan eksplorasi. [web:101]

Kekurangan

  • • Masih eksponensial worst-case, terutama untuk instance besar tanpa struktur yang bisa dimanfaatkan. [web:97][web:101]
  • • Membutuhkan desain bounding function yang baik; bound terlalu longgar → sedikit pruning. [web:102][web:99]
  • • Memori bisa tinggi jika memakai best‑first search dengan banyak node aktif. [web:97][web:99]
Ringkasan Aplikasi

Problem yang Cocok untuk Branch and Bound

🧳

0/1 Knapsack

Memaksimalkan nilai di bawah batas kapasitas, dengan kombinasi item diskrit. [web:97][web:96]

🗺️

Travelling Salesman

Menemukan tour terpendek yang mengunjungi semua kota sekali. [web:94][web:100]

📋

Assignment Problem

Mengalokasikan tugas ke agen dengan biaya minimum. [web:96][web:97]

🏗️

Integer Programming

Solusi integral untuk model linear dengan variabel diskrit. [web:101][web:102]

🧱

Job Scheduling

Menjadwalkan pekerjaan pada mesin dengan waktu/biaya optimal. [web:97]

📡

Network Design

Desain jaringan dengan cost minimal, termasuk varian Steiner tree. [web:97][web:102]

Kesimpulan

Inti Paradigma Branch and Bound

Branch and Bound adalah cara sistematis untuk mencari solusi optimal dengan menjelajahi state-space tree, namun hanya benar‑benar mengembangkan cabang yang menjanjikan. Kualitas fungsi bound menentukan seberapa banyak pruning yang bisa dilakukan.

🧠
Paradigma
Optimisasi di atas ruang solusi diskrit menggunakan tree.
✂️
Bounding
Bound yang kuat = lebih banyak cabang yang bisa dipotong.
📈
Analisis
Worst-case eksponensial, tapi praktik sering jauh lebih baik.
1 / 10