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 :

                          


Langkah 4 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Iterasi anak kanan aras 1

Pohon :


Langkah 5 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan: Iterasi anak kanan aras 1 dan anak kiri aras 2

Pohon :


Langkah 6 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Iterasi anak kiri aras 2 dengan solusi terbaik

Pohon :

 

Langkah 7 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Perluasan anak kiri aras 2

Pohon :


Langkah 8 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Iterasi anak kiri aras 3

Pohon :


               

Langkah 9 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Bunuh anak kiri aras 3 karena tidak mungkin mengarah ke solusi (melanggar batasan ke 2 dan 4

Pohon :


Langkah 10 :

Solusi terbaik sampai saat ini : {0,1,0,1}

Nilai Z maksimum : 9

Keterangan : Iterasi anak kanan aras 3

Pohon :


Langkah 11 :

Solusi terbaik sampai saat ini : {1,1,0,0}

Nilai Z maksimum : 14

Keterangan : Perluasan anak kanan aras 3 dan iterasi anak kiri aras 4

Pohon :


Langkah 12 :

Solusi terbaik sampai saat ini : {1,1,0,0}

Nilai Z maksimum : 14

Keterangan : Bunuh anak kanan aras 4 karena tidak mungkin mengarah ke solusi (melanggar batasan ke 1)

Pohon :


Langkah 13 :

Solusi terbaik sampai saat ini : {1,1,0,0}

Nilai Z maksimum : 14

Keterangan : Bunuh anak kanan aras 2 karena jika anak kanan aras 4 dibunuh, aras 2 tidak mungkin mengarah ke solusi

Pohon :


Setelah menjalani berbagai langkah, diperoleh solusi optimal dari permasalahan di atas.

Solusi : {1,1,0,0}

Nilai Z maksimum : 14


Refrensi :

https://piptools.net/algoritma-bb-branch-and-bound/

 

Nama            : Irham Iswanda Duhair

NPM             : 19316018

Kelas             : TK 19 C

Fakultas         : http://ftik.teknokrat.ac.id/

Universitas    : https://teknokrat.ac.id/

Komentar

Posting Komentar

Postingan populer dari blog ini

Extreme Programming (XP)

-
Gambar
                                                                                         Extreme Programming (XP) Sejarah Extreme Programming Proyek Pemrograman Extreme pertama dimulai 6 Maret 1996. Extreme Programming adalah salah satu dari beberapa Proses Agile populer. Sudah terbukti sangat sukses di banyak perusahaan dari berbagai ukuran dan industri di seluruh dunia. XP dikembangkan oleh Kent Beck, yang menulis buku yang berjudul “eXtreme Programming eXplained”. Dua buku yang barunya akan dipasarkan pada bulan Oktober ini. Proses instalasi Extreme Programming dilakukan oleh Ron Jeffries, Ann Anderson, dan Chet Hendrickson. Sedangkan Planning Extreme Programming dilakukan oleh Kent Beck dan Martin Fowler. Extreme Pro...
Baca selengkapnya

Tugas Pertemuan 13 Bahasa Indonesia

-
Gambar
                                                                             SISTEM KEAMANAN SEPEDA MOTOR MENGGUNAKAN E-KTP     PROPOSAL SKRIPSI Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Sarjana Komputer dari Fakultas Teknik dan Ilmu Komputer Universitas Teknokrat Indonesia     Disusun oleh : IRHAM ISWANDA DUHAIR 19316018         PROGRAM STUDI S1 TEKNIK KOMPUTER FAKULTAS TEKNIK DAN ILMU KOMPUTER UNIVERSITAS TEKNOKRAT INDONESIA 2021 BAB I PENDAHULUAN 1.1 Latar Belakang      Pada era globalisasi keamanan informasi merupakan hal yang sangat penting. Sebuah sistem keamanan informasi harus memperhatikan tiga hal yai...
Baca selengkapnya

Tugas Enkapsulasi

-
Gambar
                                                                                                                          ENCAPSULATION Assigment 1  Jawaban : Class Mahasiswa :  //Irham Iswanda Duhair //19316018 public class mahasiswa {     //membuat atribut class    private String NPM;    private String NAMA;    private String Alamat;    private String NoHP;    private String Email;    private String Instagram;        public String getNPM(){       return NPM;     }   ...
Baca selengkapnya