Column Generation with Soft Fixing Constraints Applied to the One-Dimensional Cutting Stock Problem

The Cutting Stock Problem (CSP) is a classic combinatorial optimization problem, characterized by high complexity due to the large number of variables involved. This work proposed the application of the Column Generation algorithm with the incorporation of Soft Fixing constraints to make the CSP resolution more efficient. The methodology was tested on 1600 artificially generated instances, using the Kantorovich formulation as a reference for performance comparison. With the application of the constraints, an improvement of 44\% of the instances initially without an optimal solution was obtained and the optimal solution was obtained in 3\% of these. Furthermore, the method proved to be efficient both in terms of absolute amount of improvements and in execution time, presenting a lower computational cost than the classical formulation. The results indicate that the proposed strategy is promising for improving solutions in problems of greater complexity.