## AKSIOMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 13, No. 1 April 2022 e-ISSN 2579-7646
Perbandingan Metode Branch and Bound dan Enumerasi implisit dalam menyelesaikan masalah Knapsack
1 Fakhry Asad Agusfrianto, 2 Ramya Rachmawati
1 Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Negeri Jakarta
2 Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Bengkulu Email: fakhry_asad@yahoo.com

## Abstrak
Masalah  knapsack  merupakan  masalah  program  bilangan  bulat  yang melibatkan  satu  kendala  saja.  Masalah  knapsack  umumnya  diilustrasikan dengan  suatu  tas  dan  barang.  Masalah  yang  akan  kita  selesaikan  dalam masalah  knapsack  adalah  memaksimumkan  harga  barang  dengan  kapasitas tertentu  yang  dapat  dimuat  oleh  tas  dengan  kapasitas  tertentu  juga.  Dalam menyelesaikan masalah knapsack, umumnya dapat dikerjakan secara langsung (penerkaan), menggunakan metode branch and bound, dan enumerasi implisit. Pada paper ini, akan dilakukan perbandingan 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.
Kata kunci: masalah knapsack; metode branch and bound; enumerasi implisit

## Abstract
Knapsack  problem  is  an  integer  programming  problem  involving  only  one constrain. Usually, knapsack problem illustrated by a bag and item. A problem which  we  will  solve  on  knapsack  problem  is  maximizing  price  of  item  with particular  capacity  loadable  by  bag  with  particular  capacity  too. On  solve knapsack problem, commonly can be solve directly (guessing), using branch and bound  method,  and  implicit  enumeration.  In  this  paper,  we  will  perform comparison solution of knapsack problem using branch and bound method and implicit  enumeration.  We  will  also  see  which  method  most  effective  to  solve knapsack problem.
Keywords: knapsack problem; branch and bound method; implicit enumeration

## A. Pendahuluan
Masalah  program  bilangan  bulat ( integer  programming )  merupakan masalah  pemrograman  linear  yang  solusinya  harus  merupakan  bilangan bulat.  Penyelesaian  program  bilangan  bulat  dapat  diselesaikan  dengan berbagai  cara  yaitu  dengan  metode  grafik,  metode  simpleks,  dan  metode algoritma bidang potong (Hiller & Lieberman, 2015) dan (Basriati, 2018) . Untuk menyelesaikan  program  bilangan  bulat,  kita  harus  menentukan penyelesaian  sebelum  nilainya  disyaratkan  bulat  atau  umumnya  disebut sebagai LP relaxation (Winston, 2004). Jika LP relaxation sudah bulat, maka LP  relaxation sekaligus  merupakan  solusi  program  bilangan  bulat.  Jika

## AKSIOMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 13, No. 1 April 2022 e-ISSN 2579-7646
belum, maka harus dicari solusi bilangan bulat pada daerah penyelesaian LP relaxation . Dengan syarat,
Nilai optimal LP relaxation ≥ Nilai optimal program bilangan bulat
Beberapa  contoh  masalah  program  bilangan  bulat  adalah  masalah knapsack , masalah lockbox , dan masalah set covering (Winston, 2004). Pada paper  ini,  akan  dibahas  penyelesaian  masalah knapsack .  Istilah knapsack sendiri  berarti  karung.  Masalah knapsack merupakan  masalah  program bilangan bulat yang hanya melibatkan satu kendala saja (Winston, 2004) dan (Devita  &  Wibawa,  2020) .  Ilustrasi  masalah  dapat  dilihat  pada  Gambar  1 dibawah ini. Misalkan tas berkapasitas 20 Kg dan ada lima barang dengan bobot dan keuntungan yang berbeda-beda. Permasalahannya adalah barang manakah  yang  harus  dimasukkan  ke  dalam  tas  supaya  keuntungan maksimum  dan  kapasitas  barang  yang  dimasukkan  ke  dalam  tas  tidak melebihi kapasitas tas yang diberikan.
Gambar 1. Ilustrasi masalah knapsack
Masalah knapsack secara matematis dapat ditulis sebagai berikut.
maksimumkan 𝑧 = 𝑐 1 𝑥 1 + 𝑐 2 𝑥 2 + ⋯ + 𝑐 𝑛 𝑥 𝑛
terhadap kendala : 𝑎 1 𝑥 1 + 𝑎 2 𝑥 2 + ⋯ + 𝑎 𝑛 𝑥 𝑛 ≤  𝑑 𝑥 𝑖 = 0 atau 1 ( 𝑖 = 1,2,3, … , 𝑛)
Sebagai contoh, masalah pada Gambar 1 dapat kita tuliskan sebagai
maksimumkan 𝑧 = 𝑥 1 + 2𝑥 2 + 𝑥 3 + 3𝑥 4 + 3𝑥 5
terhadap kendala : 2𝑥 1 + 3𝑥 2 + 𝑥 3 + 5𝑥 4 + 7𝑥 3 ≤ 20 𝑥 𝑖 = 0 atau 1 (𝑖 = 1,2,3,4,5)

## AKSIOMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 13, No. 1 April 2022 e-ISSN 2579-7646
Masalah knapsack dapat diselesaikan dengan beberapa cara. Kita dapat menerapkan  algoritma  greedy  untuk  menyelesaikan  masalah knapsack (Rachmawati  dan  Candra,  2013)  dan  (Sabaruddin,  2016).  Selanjutnya, masalah knapsack juga  dapat  diselesaikan  dengan  metode branch  and bound .  Metode Branch  and  Bound dapat  juga  digunakan  untuk menyelesaikan  masalah  penjadwalan  produksi  yang  bertujuan  untuk meminimalkan  waktu  produksi  (Lesmana,  2016)  maupun  dalam  masalah penjadwalan (Mazda & Kurniawati, 2020) . Selanjutnya, masalah knapsack juga dapat  diselesaikan  dengan  algoritma  enumerasi  implisit.  Beberapa penerapan  Algoritma  enumerasi  implisit  adalah  dapat  diterapkan  dalam masalah  penjadwalan  pekerjaan-toko  ( job-shop )  (Lageweg  et  al.,  1977)  dan masalah desegregasi sekolah (Ligget, 1973). Pada paper ini, akan dilakukan perbandingan penyelesaian masalah knapsack dengan menggunakan metode branch  and  bound dan  algoritma  enumerasi  implisit.  Kita  akan  melihat metode  mana  yang  paling  efektif  untuk  menyelesaikan  suatu  masalah knapsack .

## B. Metode Penelitian
Penelitian  ini  merupakan  penelitian  kajian  literatur.  Diberikan  suatu masalah knapsack . Pertama, kita akan mengerjakan dengan metode branch and bound . Langkah mengerjakan dengan metode ini adalah kita tentukan peringkat dari item yang tersedia. Item dengan peringkat tertinggi adalah yang kita pilih pertama, item dengan peringkat kedua adalah yang kita pilih kedua, dan seterusnya. Untuk item yang dipilih, 𝑥 𝑖 = 1 dan untuk item yang tidak dipilih, 𝑥 𝑖 = 0 . Jika dalam pemilihan item, item melebihi batas kendala yang diberikan, maka bagi sisa dari item tersebut dengan koefisien dari item yang dipilih. Dalam membagi sisa item dengan koefisien item yang dipilih, kita akan peroleh bentuk 𝑥 𝑗 = 𝑎 𝑏 dimana ini merupakan bentuk pecahan dan bukan 0 atau 1. Sehingga, nilai inilah yang akan kita cabangkan sedemikian rupa sehingga diperoleh nilai 𝑥 𝑗 yaitu 0 atau 1. Sebagai ilustrasi pencabangan pada metode branch and bound, perhatikan Gambar 2 dibawah ini.
Gambar 2. Ilustrasi pencabangan metode branch and bound
Berdasarkan  ilustrasi  diatas,  karena  pada 𝑡 = 1 nilai 𝑥 3 masih  berupa pecahan, maka 𝑥 3 harus dicabangkan seperti pada Gambar 2. Ketika 𝑡 = 2 , ternyata semua nilai 𝑥 sudah merupakan bilangan bulat. Sehingga 𝑧 = 9 kita
𝑥 1 = 0, 𝑥 2 = 1, 𝑥 3 = 2 3 𝑧 = 10,25
𝑥 1 = 1, 𝑥 2 = 1, 𝑥 3 = 1 𝑧 = 9 𝑥 1 = 1 2 , 𝑥 2 = 1, 𝑥 3 = 0 𝑧 = 8,75 𝑡 = 1 𝑡 = 2 𝑡 = 3 𝑥 3 = 1 𝑥 3 = 0

## AKSIOMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 13, No. 1 April 2022 e-ISSN 2579-7646
sebut sebagai solusi kandidat . Ketika 𝑡 = 3, kita peroleh 𝑥 1 masih berupa pecahan. Namun, kita tidak perlu melakukan pencabangan lagi untuk 𝑡 = 3 karena nilai 𝑧 = 8,75 tidak lebih baik dari 𝑧 = 9 . Hal ini karena kita mencari nilai 𝑧 yang bulat dan paling maksimum. Sedangkan untuk 𝑧 = 8,75 , tidak ada lagi bilangan bulat yang dibawah 𝑧 = 8,75 yang lebih besar dari 𝑧 = 9 . Sehingga, 𝑧 = 9 merupakan  solusi  dari  masalah knapsack yang  diberikan tersebut.
Selanjutnya,  masalah knapsack juga  dapat  diselesaikan  dengan algoritma  enumerasi  implisit.  Langkah  penyelesaian  masalah knapsack dengan  algoritma  enumerasi  implisit  adalah  dengan  menentukan  terlebih dahulu variabel bebas dan variabel tetapnya. Setelah itu, kita tentukan best completion dari  masalah knapsack tersebut.  Setelah  itu,  nilai  dari best completion harus  ditinjau  apakah  layak  atau  tidak.  Jika  layak,  maka  itu adalah best  completion dari  masalah knapsack tersebut.  Jika  tidak  layak, maka  harus  ditinjau  kelayakan  dari  masalah knapsack tersebut  dengan aturan yang tertera pada tabel berikut.
Tipe Kendala Tanda dari Koefisien Variabel Bebas dalam Kendala Nilai Variabel Bebas dalam Peninjauan Kelayakan ≤ + 0 ≤ − 1 ≥ + 1 ≥ − 0

## Tabel 1. Aturan pada cek kelayakan
Jika  ternyata  solusi  layak,  maka  dilakukan  pencabangan  pada  masalah knapsack tersebut.  Jika  tidak  layak,  maka  dapat  disimpulkan  bahwa masalah knapsack tersebut tidak dapat diselesaikan. Ilustrasi pencabangan pada algoritma enumerasi implisit adalah sebagai berikut.
Gambar 3. Pencabangan pada algoritma enumerasi implisit Pencabangan  pada  Gambar  3  dilakukan  hingga  diperoleh best  completion yang layak untuk masalah knapsack yang diberikan.

## C. Hasil dan Pembahasan
Dalam  paper  ini,  kita  akan  menggunakan  masalah knapsack empat variabel. Misalkan diberikan masalah knapsack sebagai berikut
1 2 3 𝑡 = 0 𝑡 = 1 𝑡 = 2

## AKSIOMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 13, No. 1 April 2022 e-ISSN 2579-7646
maksimumkan 𝑧 = 5𝑥 1 + 8𝑥 2 + 3𝑥 3 + 7𝑥 4 terhadap kendala 3𝑥 1 + 5𝑥 2 + 2𝑥 3 + 4𝑥 4 ≤ 6 dengan 𝑥 𝑖 = 0 atau 1 ( 𝑖 = 1,2,3,4) (1)
Pertama, kita akan selesaikan masalah knapsack ini menggunakan metode Branch and Bound .

## Metode
Branch and Bound
Tahap pertama, kita bentuk tabel sebagai berikut
Item ke- 𝒊 𝒄 𝒊 𝒂 𝒊 ⁄ Peringkat 1 5
3 = 1,67
2 2 8
5 = 1,6 3 3 3
2 = 1,5
4 4
7 4 = 1,75 1
Kita  akan  menyelesaikan  masalah knapsack tersebut  dengan  langkah sebagai berikut.
Submasalah 1 :
Pilih peringkat tertinggi. Pada kasus ini, 𝑥 4 yang dipilih pertama. Karena 𝑥 4 dipilih,  maka 𝑥 4 = 1 .  Sehingga  item  yang  tersisa  adalah 6 − 4 = 2 . Selanjutnya,  pilih  item  1.  Perhatikan  bahwa,  koefisien 𝑥 1 pada  kendala bernilai  3,  sehingga  haruslah 𝑥 1 = 𝑠𝑖𝑠𝑎 𝑘𝑜𝑒𝑓𝑖𝑠𝑖𝑒𝑛 𝑥 1 = 2 3 .  Dengan  demikian,  item yang tersisa adalah 0. Item 2 dan 3 tidak dipilih, sehingga 𝑥 2 = 𝑥 3 = 0 . Nilai 𝑧 untuk submasalah  1  adalah 𝑧 = 5 ( 2 3 ) + 8(0) + 3(0) + 7(1) = 31 3 . Karena 𝑥 1 masih bukan berupa bilangan bulat, maka kita akan cabangkan 𝑥 1 .
Gambar 3. Pencabangan submasalah 1
𝑥 1 = 2 3 , 𝑥 2 = 0, 𝑥 3 = 0, 𝑥 4 = 1
𝑧 = 31 3 = 10,33
𝑥 1 = 1 , 𝑥 2 = 0, 𝑥 3 = 0 , 𝑥 4 = 3 4 𝑧 = 10,25 𝑥 1 = 1 𝑥 1 = 0 𝑡 = 1 𝑡 = 2 𝑡 = 7

## AKSIOMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 13, No. 1 April 2022 e-ISSN 2579-7646
Submasalah 2 : 𝑥 1 = 1 Karena 𝑥 1 tetap, maka 𝑥 1 = 1 kita pilih terlebih dahulu. Maka item tersisa adalah 6 − 3 = 3 . Selanjutnya, pilih item 4. Karena koefisien 𝑥 4 lebih dari 3, maka 𝑥 4 = 3 4 . Sehingga diperoleh nilai 𝑧 = 41 4 = 10,25 . Karena nilai 𝑥 4 masih belum merupakan bilangan bulat, maka kita cabangkan nilai 𝑥 4 .
Gambar 4. Pencabangan submasalah 2
Submasalah 3 : 𝑥 1 = 1, 𝑥 4 = 1 Karena 𝑥 1 dan 𝑥 4 tetap, maka kita pilih item 4 terlebih dahulu (berdasarkan peringkat).  Jika  item  4  dipilih,  maka 𝑥 4 = 1 dan  tersisa 6 − 4 = 2 item. Selanjutnya,  pilih  item  1  maka  haruslah 𝑥 1 = 1 .  Karena  item  tersisa  2, sedangkan koefisien kendala dari 𝑥 1 adalah 3, maka untuk 𝑡 = 2 diperoleh solusi yang tidak layak.
Submasalah 4 : 𝑥 1 = 1, 𝑥 4 = 0 Karena 𝑥 1 dan 𝑥 4 tetap, maka kita pilih item 4 terlebih dahulu (berdasarkan peringkat).  Tetapi,  karena 𝑥 4 = 0 maka  kita  katakan  “ 𝑥 4 tidak  dipilih”. Sehingga  masih  tersisa  6.  Selanjutnya,  pilih 𝑥 1 = 1 maka  tersisa 6 − 3 = 3 item.  Selanjutnya,  pilih  item  2  maka 𝑥 2 = 3 5 .  Maka  diperoleh  nilai 𝑧 = 9,8 . Karena  nilai 𝑥 2 masih  belum  merupakan  bilangan  bulat,  maka  kita cabangkan 𝑥 2 .
Gambar 5. Pencabangan submasalah 4
𝑥 1 = 1 , 𝑥 2 = 0, 𝑥 3 = 0 , 𝑥 4 = 3 4 𝑧 = 10,25

## SOLUSI TIDAK LAYAK
(INFEASIBLE)
𝑥 1 = 1 , 𝑥 2 = 3 5 , 𝑥 3 = 0 , 𝑥 4 = 0
𝑧 = 9,8 𝑥 4 = 1 𝑥 4 = 0 𝑡 = 3 𝑡 = 4 𝑥 1 = 1 , 𝑥 2 = 3 5 , 𝑥 3 = 0 , 𝑥 4 = 0 𝑧 = 9,8

## SOLUSI TIDAK LAYAK
(INFEASIBLE) 𝑡 = 5
𝑥 1 = 1 , 𝑥 2 = 0, 𝑥 3 = 1 , 𝑥 4 = 0 𝑧 = 8
SOLUSI KANDIDAT 1
𝑡 = 6 𝑥 2 = 1 𝑥 2 = 0

## AKSIOMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 13, No. 1 April 2022 e-ISSN 2579-7646
Submasalah 5 : 𝑥 1 = 1, 𝑥 2 = 1, 𝑥 4 = 0 . Karena 𝑥 1 , 𝑥 2 dan 𝑥 4 tetap, maka terlebih dahulu kita pilih 𝑥 4 . Karena 𝑥 4 = 0 , maka 𝑥 4 tidak dipilih. Sehingga masih tersisa 6 item. Selanjutnya, pilih item 1. Maka 𝑥 1 = 1 dan tersisa 6 − 3 = 3 item. Selanjutnya, pilih item 2. Maka haruslah 𝑥 2 = 1 .  Namun,  karena  item  tersisa  3  sedangkan  koefisien 𝑥 2 bernilai 5, maka submasalah 5 memiliki solusi yang tidak layak.
Submasalah 6 : 𝑥 1 = 1, 𝑥 2 = 0, 𝑥 4 = 0 . Karena 𝑥 1 , 𝑥 2 dan 𝑥 4 tetap, maka terlebih dahulu kita pilih 𝑥 4 . Karena 𝑥 4 = 0 , maka 𝑥 4 tidak dipilih. Sehingga masih tersisa 6 item. Selanjutnya, pilih item 1. Maka 𝑥 1 = 1 dan tersisa 6 − 3 = 3 item. Selanjutnya, item 2 tidak dipilih. Maka 𝑥 2 = 0 dan masih tersisa 3 item. Selanjutnya pilih item 3 , maka tersisa 1 item. Maka diperoleh nilai 𝑧 = 8. Karena nilai 𝑥 1 , 𝑥 2 , 𝑥 3 , dan 𝑥 4 sudah 0 atau 1, maka 𝑧 = 8 adalah solusi kandidat 1 .
Sekarang,  perhatikan  kembali  Gambar  3.  Kotak  yang  belum  dikerjakan tersebut kita kerjakan untuk melihat apakah ada nilai 𝑧 yang lebih baik.
Submasalah 7 : 𝑥 1 = 0 . Karena 𝑥 1 = 0 , maka item yang tersisa 6. Selanjutnya, pilih item 4 yaitu 𝑥 4 = 1 maka tersisa 6 − 4 = 2 item. Selanjutnya, pilih item 2 yaitu 𝑥 2 = 2 5 . Sehingga diperoleh nilai 𝑧 = 10,2 . Karena nilai 𝑧 = 10,2 lebih baik dari solusi kandidat 1, maka kita harus mencabangkan lagi 𝑥 2 .
Gambar 6. Pencabangan submasalah 7
Submasalah 8 : 𝑥 1 = 0, 𝑥 2 = 0 .
Dengan  cara  yang  sama  seperti  menyelesaikan  submasalah  sebelumnya, maka diperoleh 𝑥 1 = 0, 𝑥 2 = 0, 𝑥 3 = 1, dan 𝑥 4 = 1 dan nilai 𝑧 = 10 . Maka, nilai 𝑧 = 10 merupakan solusi kandidat 2.
𝑥 1 = 0, 𝑥 2 = 2 5 , 𝑥 3 = 0, 𝑥 4 = 1 𝑧 = 10,2 𝑡 = 7 𝑥 1 = 0, 𝑥 2 = 2 5 , 𝑥 3 = 0, 𝑥 4 = 1 𝑧 = 10,2
𝑥 1 = 0, 𝑥 2 = 1, 𝑥 3 = 1, 𝑥 4 = 1 4 𝑧 = 9,75 𝑥 1 = 0, 𝑥 2 = 0, 𝑥 3 = 1, 𝑥 4 = 1 𝑧 = 10 SOLUSI KANDIDAT 2 𝑡 = 9 𝑡 = 8 𝑥 2 = 1 𝑥 2 = 0

## AKSIOMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 13, No. 1 April 2022 e-ISSN 2579-7646
Submasalah 9 : 𝑥 1 = 0, 𝑥 2 = 1 . Diperoleh 𝑥 1 = 0, 𝑥 2 = 1, 𝑥 3 = 1, 𝑥 4 = 1 dan nilai 𝑧 = 9,75 . Karena 𝑧 = 9,75 tidak lebih baik dari 𝑧 = 10 , maka proses kita hentikan.
Jika  dibandingkan  solusi  kandidat  1  dan  solusi  kandidat  2,  maka  nilai optimal pada solusi kandidat 2 lebih baik daripada nilai optimal pada solusi kandidat  1.  Hal  ini  karena  pada  kasus  ini  merupakan  kasus  maksimasi sehingga  haruslah  dipilih  nilai 𝑧 yang  paling  besar  dan 𝑥 𝑖 (𝑖 = 1,2,3,4) bilangan  bulat  (Winston,  2004).  Dengan  demikian,  solusi  untuk  masalah knapsack tersebut  adalah 𝑥 1 = 0, 𝑥 2 = 0, 𝑥 3 = 1 dan 𝑥 4 = 1 dengan  nilai 𝑧 = 10 .
Pembaca dapat mencoba dengan cara yang sama yaitu mengerjakan ketika 𝑥 1 = 0 terlebih dahulu. Selanjutnya,  kita  akan  selesaikan  masalah knapsack ini  menggunakan algoritma enumerasi implisit.

## Algoritma Enumerasi Implisit
Pada  bagian  ini,  kita  akan  menyelesaikan  masalah knapsack (1) dengan  menggunakan  algoritma  enumerasi  implisit.  Langkah  pada enumerasi implisit kita beri istilah “node”.

## Node 1
Variabel bebas
: 𝑥 1 , 𝑥 2 , 𝑥 3 , 𝑥 4 Variabel tetap : -
Best completion
𝑥 1 = 𝑥 2 = 𝑥 3 = 𝑥 4 = 1
Masukkan    nilai  diatas  pada  kendala  (1),  diperoleh 14 ≤ 6 .  Sehingga best completion tersebut tidak layak karena melanggar kendala yang diberikan.
Sekarang, kita akan cek kelayakan sistem tersebut. Karena tipe kendala ≤ dan tanda di tiap koefisien pada kendala (1) seluruhnya positif, maka nilai 𝑥 1 = 𝑥 2 = 𝑥 3 = 𝑥 4 = 0 . Sehingga, jika nilai tersebut dimasukkan pada kendala (1), diperoleh 0 ≤ 6. Maka node 1 punya solusi layak. Maka, cabangkan pada variabel bebasnya. Misalkan, kita cabangkan 𝑥 1 . 1 2 3 𝑡 = 1 𝑡 = 2 𝑥 1 = 1
𝑥 1 = 0

## AKSIOMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 13, No. 1 April 2022 e-ISSN 2579-7646

## Node 3
Variabel bebas : 𝑥 2 , 𝑥 3 , 𝑥 4 Variabel tetap : 𝑥 1 Best completion 𝑥 1 = 0 , 𝑥 2 = 1, 𝑥 3 = 1, 𝑥 4 = 1 . Masukkan  nilai  diatas  pada  kendala  (1),  diperoleh 11 ≤ 6 .  Sehingga best completion tersebut tidak layak karena melanggar kendala yang diberikan.
Sekarang, kita akan cek kelayakan sistem tersebut. Karena tipe kendala ≤ dan tanda di tiap koefisien pada kendala (1) seluruhnya positif dan 𝑥 1 tetap, maka nilai 𝑥 1 = 0, 𝑥 2 = 𝑥 3 = 𝑥 4 = 0 . Sehingga, jika nilai tersebut dimasukkan pada  kendala  (1),  diperoleh 0 ≤ 6. Maka node  1  punya  solusi  layak. Maka, cabangkan pada variabel bebasnya. Misalkan, kita cabangkan 𝑥 2 .
Node 5 Variabel bebas : 𝑥 3 , 𝑥 4 Variabel tetap : 𝑥 1 , 𝑥 2 Best completion 𝑥 1 = 0 , 𝑥 2 = 0, 𝑥 3 = 1, 𝑥 4 = 1 . Masukkan  nilai  diatas  pada  kendala  (1),  diperoleh 6 ≤ 6 .  Sehingga best completion tersebut layak .  Diperoleh  solusi  kandidat  1 𝑥 1 = 0 , 𝑥 2 = 0, 𝑥 3 = 1, 𝑥 4 = 1 dengan nilai 𝑧 = 10 .
Walaupun solusi sudah layak, tapi kita masih memiliki beberapa node yang belum  dikerjakan.  Untuk  itu,  kita  harus  mengerjakan  node  tersebut  guna meninjau apakah ada solusi yang lebih baik dari solusi kandidat 1.

## Node 4
Variabel bebas : 𝑥 3 , 𝑥 4 Variabel tetap : 𝑥 1 , 𝑥 2 Best completion 𝑥 1 = 0 , 𝑥 2 = 1, 𝑥 3 = 1, 𝑥 4 = 1 . Masukkan  nilai  diatas  pada  kendala  (1),  diperoleh 11 ≤ 6 .  Sehingga best completion tersebut  tidak  layak.  Sebelum  dilanjutkan,  nilai 𝑧 dari  node  4 adalah 𝑧 = 18 yang menandakan bahwa node 4 lebih baik dari node 5. Setelah dicek  kelayakan,  yaitu  di  titik 𝑥 1 = 0, 𝑥 2 = 1, 𝑥 3 = 0, 𝑥 4 = 0 ,  maka  diperoleh
3 4 5 𝑡 = 3 𝑥 2 = 1 𝑥 2 = 0 𝑡 = 4

## AKSIOMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 13, No. 1 April 2022 e-ISSN 2579-7646
5 ≤ 6 yang  menandakan  bahwa  node  4  memiliki  solusi  layak.  Maka  kita cabangkan variabel bebas dari node 4. Misalkan 𝑥 3 .
Node 6 Variabel bebas : 𝑥 4
Variabel tetap
: 𝑥 1 , 𝑥 2 , 𝑥 3 Best completion 𝑥 1 = 0, 𝑥 2 = 1, 𝑥 3 = 1, 𝑥 4 = 1 Dapat dicek bahwa best completion adalah solusi yang tidak layak. Selanjutnya,  setelah  dicek  kelayakan  diperoleh 7 ≤ 6 yang  menandakan bahwa node 6 memiliki solusi tidak layak .
Node 7 Variabel bebas : 𝑥 4 Variabel tetap : 𝑥 1 , 𝑥 2 , 𝑥 3 Best completion 𝑥 1 = 0, 𝑥 2 = 1, 𝑥 3 = 0, 𝑥 4 = 1 Dapat dicek bahwa best completion adalah solusi yang tidak layak. Sebelum dilanjut cek kelayakan, nilai 𝑧 dari node 7 adalah 𝑧 = 15 yang lebih baik dari solusi kandidat pada Node 5 . Selanjutnya, setelah dicek kelayakan diperoleh 5 ≤ 6 yang menandakan bahwa node 7 memiliki solusi layak.
Begitu pula seterusnya untuk node-node lainnya. Pada akhirnya, diperoleh node 5 merupakan solusi yang paling baik karena kasus ini merupakan kasus maksimasi, sehingga haruslah dipilih nilai 𝑧 terbesar (Winston, 2004). Nilai 𝑧 terbesar  dengan  nilai 𝑥 𝑖 (𝑖 = 1,2,3,4) merupakan  bilangan  bulat  terjadi  di node  5.  Sehingga,  solusi  untuk  masalah knapsack ini  adalah 𝑥 1 = 0, 𝑥 2 = 0, 𝑥 3 = 1 , dan 𝑥 4 = 1 dengan nilai 𝑧 = 10 .

## D. Simpulan
Berdasarkan  pemaparan  diatas,  dapat  dilihat  bahwa  kita  memperoleh hasil  yang  sama  baik  menggunakan  metode branch  and  bound maupun menggunakan  metode  enumerasi  implisit.  Berdasarkan  proses  yang  kita lakukan, kita dapat melihat bahwa metode branch and bound adalah metode
4 6 7 𝑥 3 = 1 𝑥 3 = 0 𝑡 = 5

## AKSIOMA: Jurnal Matematika dan Pendidikan Matematika
Vol. 13, No. 1 April 2022 e-ISSN 2579-7646
yang lebih efektif daripada metode enumerasi implisit. Pada metode branch and  bound ,  kita  tidak  memerlukan  Tabel  1  untuk  mencari  solusi  dari masalah knapsack .  Sedangkan,  untuk  metode  enumerasi  implisit,  kita memerlukan  Tabel  1  untuk  mengecek  kelayakannya  dan  sangat  mungkin terjadi  kesalahan.  Saran  untuk  penelitian  selanjutnya,  peneliti  dapat menggunakan  metode  lain  seperti  algoritma  greedy  untuk  dilakukan perbandingan manakah metode yang paling efektif.

## E. Daftar Pustaka
Basriati,  S.  (2018).  Integer  Linear  Programming  Dengan  Pendekatan  Metode  Cutting Plane  Dan  Branch  And  Bound  Untuk  Optimasi  Produk  Tahu. Jurnal  Sains Matematika Dan Statistika , 4 (2), 95–104.
Devita,  R.  N.,    Wibawa,  A.  P.  (2020).  Teknik  Teknik  Optimasi  Knapsack  Problem.
Sains, Aplikasi, Komputasi Dan Teknologi Informasi , 2 (1), 35–40. Hiller,  F.  S.,    Lieberman,  G.  J.  (2015). Introduction  to  Operation  Research:  Tenth Edition . Mc Graw Hill Education.
Lageweg, B. J., Lenstra, J. K.,  Rinnooy Kan, H. G. (1977). Job-Shop Scheduling by Implicit Enumeration. Management Science , 24 (4), 441–450.
Lesmana,  N.  I.  (2016).  Penjadwalan  Produksi  Untuk  Meminimalkan  Waktu  Produksi Dengan  Menggunakan  Metode  Branch  and  Bound. Jurnal  Teknik  Industri , 17 (1), 42–50.
Ligget,  R.  S.  (1973).  The  Application  of  An  Implicit  Enumeration  Algorithm  To  The School Desegregation Problem. Management Science , 20 (2), 159–168.
Mazda,  C.  N.,    Kurniawati,  D.  A.  (2020).  Branch  and  Bound  Method  to  Overcome Delay Delivery Order in Flow Shop Scheduling Problem. International Conference on Industrial and Manufacturing Engineering .
Rachmawati,  Dian    Candra,  Ade.  (2013).  Implementasi  Algoritma  Greedy  Untuk Menyelesaikan Masalah Knapsack Problem. Jurnal SAINTIKOM, 12 (3). 185 – 192. Sabaruddin,  Raja.  (2016).  Solusi  Optimum  Minmax  0/1  Knapsack  Menggunakan Algoritma Greedy. Jurnal Evolusi, 4 (2). 76 – 82.
Winston, W.L. (2004). Operation Research: Application and Algorithms. Belmont, USA: BROOCKS/COLE.