Analisis Efektivitas Metode Branch And Bound Dalam Penyelesaian Masalah Knapsack

Abstract

Integer Linear Programming adalah sebuah model matematis yang 
memungkinkan hasil penyelesaian kasus pada Pemrograman Linier berupa bilangan bulat. 
Masalah integer linear programming termasuk salah satu bagian riset operasi yang sangat 
penting karena dalam kehidupan sehari-hari, ada banyak permasalah pemrograman linear 
yang mengharuskan solusinya integer. Ada beberapa metode untuk menyelesaikan 
persoalan Integer programming, tapi yang akan dibahas pada penelitian ini adalah Metode 
Branch and Bound dan Metode Gomory Cut. Tujuan dari penelitian ini adalah untuk 
menentukan solusi masalah Integer Linear Programming dan membandingkan hasil yang 
diperoleh dari Metode Branch and Bound dengan Metode Gomory Cut. Penelitian ini 
adalah penelitian kepustakaan yang menggunakan berbagai literatur-literatur yang 
berkaitan dengan topik yang akan diteliti. Pencarian solusi untuk model ini dilakukan 
dengan algoritma Branch and Bound. Berdasarkan hasil perhitungan menggunakan 
software QM for Windows, diketahui bahwa penentuan jumlah produksi dengan 
menggunakan algoritma branch and bound memberikan penyelesaian masalah knapsack 
dengan metode branch and bound dan enumerasi implisit. Kita juga akan dapat melihat 
metode mana yang paling efektif untuk menyelesaikan suatu masalah knapsack.