International Transactions in Operational Research · 1998 · 12 citations · 27 references
ComputingComputer ScienceAlgorithmsComputational GeometryOptimizationApproximation AlgorithmsBranch And BoundCombinatorial OptimizationGeometric OptimizationHeuristic OptimizationInteger ProgrammingHeuristic ApproachPacking Problems
In this paper we discuss the problem of packing a set of small rectangles (pieces) in an enclosing final rectangle. We present first a best‐first branch‐and‐bound exact algorithm and second a heuristic approach in order to solve exactly and approximately this problem. The performances of the proposed approaches are evaluated on several randomly generated problem instances. Computational results show that the proposed exact algorithm is able to solve small and medium problem instances within reasonable execution time. The derived heuristic performs very well in the sense that it produces high‐quality solutions within small computational time.
27
Orthogonal Packings in Two Dimensions
Brenda S. Baker, E. G. Coffman, Ronald L. Rivest · SIAM Journal on Computing · 1980 · 695 citations