Developing column generation approach to solve the rectangular two-dimensional single knapsack problem

The rectangular two-dimensional Single Knapsack Problem (SKP) consists of packing a xed rectangular space (so-called pallet) with a subset of smaller rectangular shapes (so-called pieces) of dierent dimensions and without rotation. Pieces have dierent values. The objective is to maximize the sum of the values of the pieces packed. This paper proposes a new method for solving rectangular two-dimensional SKP based on the column generation approach. The mathematical formulation of the proposed model is the simplest of all present mathematical formulations in the the state-of-the art. The computational performance indicates that it is an eective method based on quality of solution.