Implementation of Mixed Integer Programming Using The Branch and Bound Algorithm in Optimizing The Proft of a Chips Enterprise

Abstract

Keripik Cinta Mas Hendro is a micro, small, and medium enterprise (MSME) operating in the snack industry, specializing in the production of various types of chips. This MSME struggles to determine the optimal production quantity due to limited resources, inconsistent raw material supply, and fluctuating market demand. This study aims to optimize the production quantity for each product variant using the Mixed Integer Programming approach with the Branch and Bound method. The Branch and Bound method were specifically chosen as it effectively handles decision variables that must be integers, which was critical in real-world production settings where fractional outputs are not feasible. The results showed that after optimization, production becomes more efficient, with allocations including: 2,100 packages of 500g Balado chips, 836 of 500g Sweet Corn, 4,500 of 500g Sweet and Spicy, 350 of 500g Seaweed, 8,527 of 1000g Original, 158 of 1000g Balado, 125 of 1000g Sweet Corn, 215 of 1000g Sweet and Spicy, 150 of 1000g Seaweed, along with 185 kg of Balado chips and 176.38 kg of Sweet and Spicy. As a result, the optimization increases profit from IDR 249,840,000 to IDR 360,791,500, reflecting a gain of IDR 110,951,500 or approximately 44.42%.