Alternative approaches for one-dimensional slitting problems

Dynamic programming has been used to find the optimal solution for one-dimensional slitting problems in which the value of a piece is nonlinearly dependent on both the width of the piece and the number of defects on it. In this paper, linear programming is proposed to solve this problem. Additionally, it is shown that this problem can be converted to be a shortest path problem and can be solved easily by an acyclic algorithm. Either a linear programming approach or a shortest path approach are both simpler and faster than the use of dynamic programming.