ALGORITMA BRANCH AND BOUND

ALGORITMA BRANCH AND BOUND

Algoritma Branch and Bound adalah metode algoritma umum untuk mencari solusi optimal dari dari berbagai permasalahan optimasi, terutama untuk optimasi diskrit dan kombinatorial. Sebagaimana pada algoritma runut-balik, algoritma Branch and Bound juga merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang solusi diorganisasikan ke dalam pohon ruang status. Yang membedakan keduanya adalah bila pada algoritma runut-balik, ruang solusi dibangun secara dinamis berdasarkan skema DFS (Depth First Search), maka pada algoritma Branch and Bound ruang solusi dibangun dengan skema BFS (Breadth First Search). Pada algoritma ini, permasalahan dibagi bagi menjadi subregion subregion yang mungkin mengarah ke solusi. Inilah yang disebut dengan branching, mengingat prosedur ini akan dilakukan berulang ulang secara rekursif untuk setiap subregion dan setiap subregion yang dihasilkan akan membentuk sebuah struktur pohon yang disebut sebagai pohon pencarian atau pohon branch-and- bound di mana simpul simpulnya membangun subregion subregion. Selain branching, lgoritma ini juga melakukan apa yang disebut dengan bounding yang merupakan cara cepat untuk mencari batas atas dan bawah untuk solusi optimal pada subregion yang mengarah ke solusi. Algoritma Branch and Bound banyak digunakan untuk memecahkan berbagai macam permasalahan antara lain : persoalan Knapsack 0/1, Travelling Salesman Problem (TSP), The N-Queens Problem (Persoalan N-Ratu), Graph Colouring (Pewarnaan Graf), Sirkuit Hamilton, Integer Programming, Nonlinear Programming, Quadratic Assignment Problem (QAP), Maximum Satisfiability Problem (MAX-SAT), dan lain sebagainya.

Algoritma B&B (Branch and Bound) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik dengan biaya terendah. Algoritma ini memiliki 2 prinsip, yaitu:

· Algoritma ini akan melakukan perhitungan secara rekursif, akan memecah masalah kedalam masalah-masalah kecil, sambil tetap menghitung nilai terendah / terbaik. Proses ini dinamakan branching

· Jika branching diterapkan secara sendirian, maka hasilnya akan tetap mencari setiap kemungkinan yang ada. Untuk meningkatkan performa, algoritma ini akan melakukan pencatatan biaya minimum sebagai bound dalam setiap perhitungan, sehingga untuk calon hasil jawaban yang diperkirakan akan melebihi bound akan dibuang karena tidak mungkin akan mencapai nilai terbaik

APLIKASI ALGORITMA BRANCH AND BOUND DALAM PENYELESAIAN INTEGER PROGRAMMING

Telah dijelaskan sebelumnya bahwa algoritma Branch and Bound dapat digunakan untuk menyelesaikan Integer Programming. Gambar 1 adalah flowchart aplikasi algoritma Branch and Bound dalam menyelesaikan Integer Programming dengan optimasi minimum. Gambar 2 adalah flowchart aplikasi algoritma Branch and Bound dalam menyelesaikan Integer Programming dengan optimasi maksimum. Berikut ini adalah contoh aplikasi algoritma Branch and Bound untuk menyelesaikan Integer Programming :

Persoalan :

Maksimum Z = 9x1 + 5x2 + 6x3 + 4x4

Dengan batasan :

1. 6x1 + 3x2 + 5x3 + 2x4 <= 10

2. x3 + x4 <= 1

3. x1 + x3 <= 0

4. x2 + x4 <= 0

5. xi <= 1, xi >= 0, xi integer

Langkah 1 : Inisialisasi Pohon

Solusi terbaik sampai saat ini : {}

Nilai Z maksimum :

Pohon :

Langkah 2 :

Solusi terbaik sampai saat ini : {}

Nilai Z maksimum :

Pohon :

Langkah 3 :

Solusi terbaik sampai saat ini : {}

Nilai Z maksimum : ~

Keterangan : Iterasi anak kiri aras 1

Pohon :