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.

Integer Programming

Integer  Programming   
(Pemrograman  Bulat) 
 
Pemrograman  bulat  dibutuhkan  ketika  keputusan  harus  dilakukan  dalam  bentuk bilangan bulat (bukan  pecahan  yang  sering  terjadi  bila  kita  gunakan  metode simpleks). Model matematis  dari  pemrograman  bulat  sebenarnya  sama  dengan model  linear programming, dengan tambahan  batasan  bahwa  variabelnya  harus bilangan  bulat.  
  Terdapat   3  macam  permasalahan  dalam  pemrograman  bulat, yaitu: 
1. Pemrograman  bulat  murni, yaitu  kasus  dimana  semua  variabel  keputusan  
harus  berupa bilangan  bulat. 
2. Pemrograman  bulat  campuran, yaitu  kasus  dimana  beberapa, tapi  tidak  
semua, variabel keputusan  harus  berupa  bilangan  bulat  
3. Pemrograman  bulat  biner, kasus  dengan  permasalahan  khusus  dimana  semua  
variabel keputusan  harus  bernilai  0  dan  1  
   Banyak  aplikasi  kegunaan  dari  integer  programming, misalnya  dalam penghitungan produksi  sebuah  perusahaan  manufaktur, dimana  hasil  dari perhitungannya  haruslah bilangan bulat, karena  perusahaan  tidak  dapat memproduksi  produknya  dalam  bentuk  setengah jadi. Misal perusahaan  perkitan mobil  tidak  bisa  merakit  5,3  mobil  A  dan  2,5  mobil  B perhari, tetapi haruslah bilangan  bulat, dengan  metode  pembulatan, bisa  kita  hasilkan misalnya 5  mobil  A  dan  2  mobil  B per  hari, tetapi  apakah  metode  pembulatan  ini efisien? Kita  lihat  pada  penjelasan  selanjutnya. Model  pemrograman  bulat dapat  juga digunakan  untuk  memecahkan  masalah  dengan jawaban  ya  atau  tidak. Model  ini  seringkali disebut  sebagai  model  pemrograman  bulat  biner