Testing of several overlapping optimization methods for bin-packing problem

In this paper several optimization methods for NP-hard bin-packing optimization problem are considered. Bin-packing problem consists of a number of items that need to be packed into a limited number of containers while satisfying the following constraints: items need to lie entirely within a container without overlapping. Bin-packing methods are also used in textile industry to optimize the material usage while cutting regular and irregular items from a fixed-width material strip. Giving a brief overview of the problem, several computational methods are described in this paper such as items and container data representation, overlapping detection and avoidance methods (constraints graphs, no-fit polygons) and optimization methods: direct search, genetic algorithm and nonlinear programming. Experiments with different number of rectangles, circles, triangles, ellipses and hexagons were performed using three methods - direct search, genetic algorithm and nonlinear programming to compare the overlapping area, total cover area and total overlapping area with nonlinear programming giving the best results.