Metode Branch And Bound Pada Integer Programming

Metode Branch And Bound diusulakan pertama kali oleh A.H.Land dan A.G.Doig pada tahun 1960. Sebenarnya metode ini dibuat untuk pemrograman linier (linier programming [5]), Namun kenyataanya metode ini mampu menyelesaikan permasalahan seperti TSP dan beberapa masalah lain. Metode ini menggunakan pohon pencarian (Search Tree), setiap simpul di pohon merupakan representasi dari sejumlah kemungkinan solusi dari TSP. Metode ini hanya dapat digunakan untuk masalah optimasi saja (optimazion problem).

Algoritma dimulai dengan pengisian sebuah nilai ke akar dari pohon pencarian tersebut. Pencabangan dilakukan dengan memasang sebuah pending node ke pending node lain yang lebih rendah levelnya. Bobot juga dihitung pada setiap proses dan ditulis di simpul pohon. Jika sebuah simpul diketahui merupakan solusi yang tidak mungkin bagi persoalan yang dihadapai, simpul tersebut diisi dengan nilai tak terbatas
(infinity). Algoritma berhenti ketika sudah tidak mungkin lagi untuk membentuk simpul baru di pohon atau hasil terakhir yang ditemukan merupakan hasil yang lebih rendah (minimum) dari isi simpul yang telah ada pada level yang lebih rendah.

Metode Branch And Bound sebenarnya bukan merupakan metode yang mutlak untuk penyelesaian TSP, metode ini merupakan kumpulan dari berbagai cara penyelesaian masalah (class of solving problem), hanya saja persamaan karakteristik cara – cara tersebut yang membuat mereka disebut Branch And Bound. Saya menyajikan salah satu metode dari sekian banyak metode yang digunakan didalam Branch And Bound.