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

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.