Minimizing cutting costs in 1D rod cutting

Abstract

We study a one‐dimensional rod‐cutting problem arising from an industrial setting where cutting itself carries cost . Each order specifies a length interval, and the task is to assign orders to warehouse rods so that all orders are satisfied while the number of cuts is minimized. This objective, which corresponds to maximizing the number of exact fits, is practically important yet has received comparatively little explicit attention. We show that both the feasibility problem and, when feasible, the problem of minimizing the number of cuts are NP‐complete. We then introduce two practical solution methods: a dynamic programming approach combined with maximum clique search, and a compact 0–1 linear programming formulation. Computational experiments demonstrate that the integer programming model is substantially more effective and scalable than the dynamic programming–based method.