An exact algorithm for general, orthogonal, two-dimensional knapsack problems

An exact algorithm for general, orthogonal, two-dimensional knapsack problems

0.00 Avg rating0 Votes
Article ID: iaor19981411
Country: Netherlands
Volume: 83
Issue: 1
Start Page Number: 39
End Page Number: 56
Publication Date: May 1995
Journal: European Journal of Operational Research
Authors: ,
Keywords: knapsack problem
Abstract:

We present a new exact tree-search procedure for solving two-dimensional knapsack problems in which a number of small rectangular pieces, each of a given size and value, are required to be cut from a large rectangular stock plate. The objective is to maximise the value of pieces cut or minimise the wastage. We consider the case where there is a maximum number of times that a piece may be used in a cutting pattern. The algorithm limits the size of the tree search by using a bound derived from a Lagrangean relaxation of a 0–1 integer programming formulation of the problem. Subgradient optimisation is used to optimise this bound. Reduction tests derived from both the original problem and the Lagrangean relaxation produce substantial computational gains. The computational performance of the algorithm indicates that it is an effective procedure capable of solving optimally practical two-dimensional cutting problems of medium size.

Reviews

Required fields are marked *. Your email address will not be published.