Algoritma Branch and Bound

 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.

Diasumsikan ada 5 titik yang harus dilalui semuanya, yaitu A,B,C,D,E
semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja
setiap jalur juga memiliki biaya sendiri-sendiri.

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.

Prinsip Pencarian Solusi pada Algoritma B&B

·       Skema BFS = skema FIFO (First In First Out).

·       Tinjau kembali persoalan 4-ratu yang diselesaikan dengan skema BFS (murni).

Gambar 7.1 Pohon ruang status yang terbentuk untuk persoalan 4-Ratu dengan metode BFS

·       Solusi pertama dicapai pada simpul 30, yaitu X = (2, 4, 1, 3). Dengan skema BFS murni / FIFO, kita harus memperluas dulu simpul 12, simpul 15, dan simpul 16 sebelum memperluas simpul 22 yang melahirkan simpul solusi, yaitu simpul 30.

·       Pada algoritma B&B, pencarian ke simpul solusi dapat dipercepat dengan memilih simpul hidup berdasarkan nilai ongkos (cost).

·       Setiap simpul hidup diasosiasikan dengan sebuah ongkos yang menyatakan nilai batas (bound).

·       Simpul hidup yang menjadi simpul-E ialah simpul yang mempunyai nilai batas terkecil (strategi  pencarian berdasarkan biaya terkecil (least cost search).

·       Untuk setiap simpul X, nilai batas ini dapat berupa [HOR78]:

(a)       jumlah simpul dalam upapohon X yang perlu  dibangkitkan sebelum simpul solusi ditemukan, atau

(b)     panjang lintasan dari simpul X ke simpul solusi terdekat (dalam upapohon X ybs)

Misal digunakan ukuran (b):

·       Pemberian nilai batas seperti pada persoalan N-Ratu di atas adalah nilai batas yang ideal, karena letak simpul solusi diketahui.

·       Pada umumnya, untuk kebanyakan persoalan, letak simpul solusi tidak diketahui, karena itu, dalam prakteknya, nilai batas untuk setiap simpul umumnya berupa taksiran atau perkiraan.

·       Fungsi heuristik untuk menghitung taksiran cost:

        = ongkos untuk simpul i

            = ongkos mencapai simpul i dari akar

       = ongkos mencapai simpul tujuan dari simpul i.

·   Simpul berikutnya yang dipilih untuk diekspansi adalah simpul yang memiliki minimum.

Algoritma B&B:

1.   Masukkan simpul akar ke dalam antrian Q. Jika simpul akar adalah simpul solusi (goal node),  maka solusi telah ditemukan.  Stop.

2.   Jika Q kosong, tidak ada solusi. Stop.

3.  Jika Q tidak kosong, pilih dari antrian Q simpul i yang mempunyaipaling kecil. Jika terdapat beberapa simpul i  yang memenuhi, pilih satu secara sembarang.

4.   Jika simpul i adalah simpul solusi, berarti solusi sudah ditemukan, stop. Jika simpul i bukan simpul solusi, maka bangkitkan semua  anak-anaknya.  Jika i tidak mempunyai anak, kembali ke langkah 2.

5.   Untuk setiap anak j dari simpul i, hitung, dan masukkan semua anak-anak tersebut ke dalam Q.

6.   Kembali ke langkah 2. 

Nama        : Aulia Nuraini

NPM         : 19312163

Kelas         : IF 19 D

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

Fakultas Teknik dan Ilmu Komputer    : http://ftik.teknokrat.ac.id/