Integer Linear Programming In Production Profit Optimization Problems Using Branch And Bound Methods & Gomory Cutting Plane

Nurweni putri; Maya Sari  Syahrul; Rosi  Ramayanti

doi:10.20956/j.v20i3.32888

Authors

Nurweni putri Universitas Dharma Andalas
Maya Sari Syahrul Universitas Dharma Andalas
Rosi Ramayanti Universitas Dharma Andalas

DOI:

https://doi.org/10.20956/j.v20i3.32888

Keywords:

Linear Programming, Integer Programming, Branch and Bound, Gomory Cutting Plane

Abstract

Integer Linear Programming is a mathematical model that allows the results of solving cases in linear programming in the form of integers. Methods to solve Integer Programming problems include the Branch and Bound Method and the Gomory Cutting Plane Method. Both of these methods have certain rules for adding new constraint functions until an optimal solution to an integer is obtained. The purpose of this study is to optimize the profits of the production of UMKM Capal Classic Shoes Kab. Agam by using the Branch and Bound method and the Gomory Cutting Plane method and analyzing the comparison of optimal results resulting from the two methods. The data used in the study are data on raw materials for making classic sandals and profit data. The results obtained by these two methods produce the same maximum profit, namely RP. 664,000 with each producing 15 pairs of men's sandals and 13 pairs of women's sandals. But in its completion, the Branch and Bound method requires many iterations and a longer time compared to the Gumory Cutting plane method.

References

. Akyuz, M.et. al., 2012. Location and Allocation Based Branch And Bound Algorithms For The Capacitated Multifacility Weber Problem. Springer Vol.222, No.59: 45- 71.

. Alpha C. Chiang dan Kevin Wainwright, 2006. Dasar-Dasar Matematika Ekonomi. Jakarta: Penerbit Erlangga.

. Azzahrha, Fatimah Khilaliyah et al., 2021. Optimalisasi Produksi Tahu Menggunakan Metode Branch and Bound dan Cutting Plane. STRING, Vol. 6 No. 2 : 175-184

. Basriati S, 2018.Integer Linear Programming Dengan Pendekatan Metode Cutting Plane dan Branch and Bound Untuk Optimasi Produksi Tahu. Jurnal Sains Matematika dan Statistika, Vol. 4, No. 2: 95 – 104

. Bronson, Richard, 1982. Theory and Problems of Operations Research.McGraw-Hill, USA

. Chadziqatun Najilatil Mazda and Dwi Agustina Kurniawati, 2020 IOP Conf. Ser.: Mater. Sci. Eng. 1003 012129

. Devi, Sari Purba dan Faiz Ahyaningsih, 2020. Integer Programming Dengan Metode Branch and Bound Dalam Optimasi Jumlah Produksi Setiap Jenis Roti Pada PT. Arma Anugerah Abadi. Karismatika, Vol. 6 No. 3: 20-29

. Dhuriattun, 2015. Penerapan Metode Cutting Plane dalam Menyelesaikan Optimalisasi Perencanaan Produksi pada Kelompok Wanita Tani (KWT) Seruni Berbah. Tugas Akhir Mahasiswa Universitas Islam Negeri Sunan Kalijaga Yogyakarta.

. Huang, Lingying, et al., 2021. Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends. Department of Electronic Engineering, HKUST

. M Fausi, 2022. Penerapan Metode Cutting Plane untuk Optimasi Biaya Pemupukan pada Tanaman Cabai. Jurnal Kajian dan Terapan Matematika,Vol. 8, Edisi 2: 85- 94

. Marzukoh, Ainul, 2017.Optimasi Keuntungan Dalam Produksi Dengan Menggunakan Linear Programming Metode. Undergraduate Thesis, UIN Raden Intan Lampung.

. Mulyono, S., 2002. Riset Operasi. Jakarta: Fakultas Ekonomi Universitas Indonesia

. Muslich, M. 2009. Metode Penganmbilan Keputusan Kuantitatif. Jakarta: Bumi Aksara

. Oberdieck, R., dan Psitikopoulos, E. N., 2014. A Branch And Bound Method For The Solution Of Multiparametric Mixed Integer Linear Programming Problems. J Glob Optim Vol. 22, No.59: 527–543.

. Roflin Eddy et al., 2014. Substituting Gomory Cutting Plane Method Towards Balas Algorithm For Solving Binary Linear Programming. Bulletin of Mathematics Vol. 06, No. 01 : 1–13.

. Rosyidah, Mita, 2021. Optimasi Jumlah Produksi Roti Manis pada Bintang Bakery dengan Metode Cutting Plane. Fakultas Sains dan Teknologi UNJA.

. Tri Rahmayani & Devni Prima Sari, 2022. Perbandingan Metode Branch and Bound dan Metode Cutting Plane dalam Optimasi Jumlah Produksi di BSL Store. Journal Of Mathematics UNP Vol. 7, No. 2, 38-43.

. Wang, S. dan Liu, M., 2015. A Branch And Bound Algorithm For Single-Machine Production Scheduling Integrated With Preventive Maintenance Planning. International Journal of Production Research,Vol.51,No.3:491–506.

. Winston, W.L., 2003. Operations Research Aplications and Algorithm. Duxbury Press, USA

. Muslich, M., 2009. Metode Pengambilan Keputusan Kuantitatif. Jakarta: Bumi Aksara

. Oberdieck, R., dan Psitikopoulos, E. N., 2014. A Branch And Bound Method For The Solution Of Multiparametric Mixed Integer Linear Programming Problems. J Glob Optim Vol. 22, No.59: 527–543.

. Rahmayani, Tri dan Devni Prima Sari, 2022. Perbandingan Metode Branch and Bound dan Metode Cutting Plane dalam Optimasi Jumlah Produksi di BSL Store. Journal of Mathematics UNP Vol. 7 No. 2 : 38-43

. Roflin Eddy et al., 2014. Substituting Gomory Cutting Plane Method Towards Balas Algorithm For Solving Binary Linear Programming. Bulletin of Mathematics Vol. 06, No. 01 : 1–13.

. Siswanto, 2007. Operation Reasearch, Jilid I. Jakarta: Penerbit Erlangga

. Taha, H.A., 2007. Operation Research An Introduction. Ed. 8. United States : Pearson Education, Inc.

. Thie, Paul R dan Keough Gerard E., 2008. An Introduction To Linier Programming And Game Theory Third Edition. Canada: Wiley.

. Wahyudin Nur and Nurul M Abdal, 2016. Penggunaan Metode Branch and Bound dan Gomory Cut dalam Menentukan Solusi Integer Linear Programming. Jurnal Saintifik, Vol.II, No. 1: 9-15

. Wang, S. dan Liu, M., 2015. A Branch And Bound Algorithm For Single-Machine Production Scheduling Integrated With Preventive Maintenance Planning. International Journal of Production Research. Vol.51,No.3:491–506.

. Winston, W.L., 2003. Operations Research Aplications and Algorithm. Duxbury Press, USA .