Solving mixed integer programming production planning problems with setups by shadow price information

Algorithms developed to solve linear programming (LP) problems and advances in computer speed have made large-scale LP problems solvable in time for implementation. Solving an LP problem is relatively easier than solving a mixed integer programming (MIP) problem for modern production planning problems. In this study, we propose a heuristic iterative algorithm between LP solution phases and setup decision computations for solving these difficult MIP production planning problems. By utilizing the shadow price information provided by the LP solution of the previous iteration, the setup decision computation converts an MIP problem into an LP problem, which can be efficiently solved in the current iteration. Extensive experiments show that the proposed heuristic algorithm performs well.