Greedy Column Generation: A Novel Constructive Heuristic for 2D Knapsack and Strip Packing

This paper addresses two-dimensional Cutting and Packing Problems, with a focus on the Knapsack Problem (KP) and Strip Packing Problem (SPP), both of which are essential for optimizing material utilization. We propose a constructive heuristic called Greedy Column Generation (GCG), designed to efficiently place irregular polygons. GCG constructs compact, adjacent columns using the Bottom-Left (BL) placement rule, guided by a convex hull (CH) metric for polygon selection and orientation. To assess its effectiveness, we compared GCG with five established heuristics on fifteen ESICUP benchmark instances, evaluating both packing efficiency and execution time. In the KP, GCG consistently outperformed the alternatives, particularly in more complex instances. For the SPP, it also delivered competitive results, although with a smaller performance margin. We further applied the Simulated Annealing (SA) metaheuristic to all methods, and GCG-SA maintained strong performance across both problems, suggesting that GCG provides stable and reliable results.