Value considerations in three-dimensional packing – a heuristic procedure using the fractional knapsack problem

Not much work has been done on the three-dimensional bin packing problem because of the larger number of complexities occurring as compared with packing problems in lower dimensions. Almost all solution procedures developed for bin packing are heuristic in nature. An heuristic algorithm has been presented here for packing a given set of regular sized boxes of different values into a given set of regular containers. The objective is to maximize the total value of the boxes packed into the given containers. The heuristic is based on an Integer Programming formulation that uses the fractional knapsack problem as a column generation subproblem.