Implementation of Branch and Bound Algorithm and Variable Reduction Algorithm in Production Profit Optimization

Linear Programming (LP) cannot answer production problems that require decision variables to be integers. For this reason, Integer Linear Programming (ILP) exists as a special case of LP where the decision variables are integers. This research is intended to determine the difference in output values and the number of iterations used in the Branch and Bound Algorithm and Variable Reduction to solve the problem of maximizing production profits. The Branch and Bound algorithm divides the problem into sub-problems that lead to a solution by forming a search tree structure and applying restrictions to achieve an optimal solution. Meanwhile, the Variable Reduction Algorithm involves moving the decision variables from the left side to the right side of the constraint function. This study uses data from the Rembang Dairy Industry, with the problem of wanting to maximize production profits. Using Maple's assistance, the settlement using the Branch and Bound Algorithm and Variable Reduction yields the same profit, which is IDR 14,786,548. However, the calculation process using the Variable Reduction Algorithm requires more iterations than the Branch and Bound Algorithm.