Developing Column Generation Approach to Solve the Rectangular Two-dimensional Single Knapsack Problem

Abstract

The rectangular two-dimensional Single Knapsack Problem (SKP) consists of packing a fixed rectangular space (so-called pallet) with a subset of smaller rectangular shapes (so-called pieces) of different dimensions, and without rotation. Pieces have different 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. Mathematical formulation of the proposed model is simplest than the present mathematical formulations in the state-of-the art. The computational performance indicates that it is an effective method in the view of quality of solution.