Discrete Optimization Model in Constructing Optimal Decision Tree


  • Nurul Azri Azwar Universitas Sumatera Utara
  • Parapat Gultom University of Sumatera Utara, Medan, Indonesia
  • Sawaluddin University of Sumatera Utara, Medan, Indonesia




Decision trees have been well studied and widely used in knowledge discovery and decision support systems. One of the applications of binary integer programming to form decision trees or decision making is the knapsack problem. The knapsack problem is an integer programming problem that involves only one constraint. The knapsack problem is generally illustrated with a bag and an item. The problem to be solved is to maximize the price of goods with a certain capacity that can be loaded by a bag with a certain capacity too. In solving the knapsack problem, it can generally be done directly. In this paper we are interested to show how the implicit enumeration method solves the knapsack problem to form an optimal decision tree

GS Cited Analysis


Download data is not yet available.


Cha, Sung-Hyuk, and Charles Tappert. 2008. Constructing Binary Decision Trees using Genetic Algorithms . Proceedings of the 2008 International Conference on Genetic and Evolutionary Methods, GEM 2008, July 14-17, 2008, Las Vegas, Nevada, USA.

Devita, R. N., & Wibawa, A. P. 2020. Teknik Teknik Optimasi Knapsack Problem. Sains, Aplikasi, Komputasi Dan Teknologi Informasi, 2(1), 35–40.

Lageweg, B. J., Lenstra, J. K., & Rinnooy Kan, H. G. 1977. Job-Shop Scheduling by Implicit Enumeration. Management Science, 24(4), 441–450.

Ligget, R. S. (1973). The Application of An Implicit Enumeration Algorithm To The School Desegregation Problem. Management Science, 20(2), 159–168.

Mitchell, T. 1997. Machine Learning. Macgraw Hill.

Rachmawati, Dian & Candra, Ade. 2013. Implementasi Algoritma Greedy Untuk Menyelesaikan Masalah Knapsack Problem. Jurnal SAINTIKOM, 12(3). 185 – 192.

Siang, Jong Jek. 2014. Riset Operasi dalam Pendekatan Algoritmis edisi 2. Penerbit Andi. Yogyakarta.

Winston, W.L. (2004). Operation Research: Application and Algorithms. Belmont, USA: BROOCKS/COLE.


Crossmark Updates

How to Cite

Azwar, N. A., Gultom, P. ., & Sawaluddin, S. (2022). Discrete Optimization Model in Constructing Optimal Decision Tree. Sinkron : Jurnal Dan Penelitian Teknik Informatika, 7(3), 2108-2115. https://doi.org/10.33395/sinkron.v7i3.11592