Two-stage one-dimensional cutting stock problem with flexible item sizes in steel industry

The classical cutting stock problem (CSP) consists of efficiently producing items with different sizes and demands using the minimum number of bins (stock materials), ensuring that the total size of the items assigned to each bin does not exceed its capacity. Various CSP variants have emerged to address specific constraints and objectives across different applications. This paper focuses on a new two-stage one-dimensional CSP with flexible item sizes (TS-1DCSP), which arises in the steel industry. In TS-1DCSP, each order is associated with a length range and a total length demand. For the TS-1DCSP, we develop compact, arc-flow-based, and pattern-based mathematical formulations, and enhance the latter by adding cuts to improve its linear programming relaxation. A novel label-setting-based pricing algorithm is designed for the pattern-based formulation. This pattern-based model forms the basis for an exact algorithm within a branch-and-price (BP) framework, using a two-level branching rule to achieve integrality. The exact algorithm also includes a primal heuristic that uses a depth-first search in the BP tree. We validate the method’s performance through extensive computational experiments on benchmark instances from literature and real-world scenarios, confirming its effectiveness in solving TS-1DCSP instances with up to 150 orders.