The Two-Dimensional Strip Packing Pro
blem: A Numerical Experiment with Waste-Free Instances Using Algorithms
with Block Structure
G. Belov, Chiglintsev A.V., Filippova A.S., Mukhacheva E.A., G. Scheithauer, Shirgazin R.R.
Preprint MATH-NM-01-2005 TU Dresden, January 2005
The collection of instances from E.~Hopper has two waste-free classes, namely C and N. The absence of waste in the optimum means that the optimal solution value is known. The number of items in the instances varies from 16 to 197. We applied several single-pass algorithms as well as local search methods and metaheuristics, both new and known from the literature. For the single-pass algorithms, we retained the optimal order of items in the list in order to test their ``correctness''. With this ordering, optimal solutions could be obtained by some of the single-pass algorithms including some of the proposed new ones. Among the other algorithms, without knowing the optimal order, only the ``sequential value correction'' method has found optima for all the instances.