Analisis Metode Branch and Cut dan Branch and Bound untuk Menyelesaikan Masalah Mixed Integer Linier Programming

Abstract

Mixed integer linear programming is a combinatorial optimization problem that is difficult to solve efficiently. One method that can be used to solve mixed integer linear programming problems is the branch and bound and branch and cut methods. The Branch and Bound method is a working procedure that takes a long time to find the optimal solution that is achieved. This method uses the results of the simplex method which does not have an integer value so that branching and limitations are carried out on the variable with the largest fractional value. The branch and cut method is a combination of the branch and bound method and the cutting plane method. The basic concept of the Branch and cut method is to break the problem into two smaller subproblems (branching) and an additional constraint will be created that (cuts) the feasible solution area of the integer or mixed integer problem, so as to eliminate non integer solutions. This paper shows how a mixed integer linear programming problem is solved using the branch and cut and branch and bound methods. The Branch and Cut method and the Branch and Bound method have different results.