A polynomial mixed-integer linear programming model for two-dimensional guillotine strip packing problem

A two-dimensional strip packing problem is the process of packing a set of rectangular items of given dimensions into a strip of bounded width and infinite height so that the used height of the strip is minimized. In the case that only guillotine packing is permitted, the problem is called the guillotine strip packing problem (GSPP). Guillotine packing commonly arises in different industries such as glass, steel, paper and wood. Nevertheless, there is a lack of explicit mathematical models for GSPP that can globally solve the problem. In this paper, a new mixed-integer programming model inspired by a so-called sequence sub-tour elimination technique for the traveling salesman problem (TSP) is presented as a relaxation of (non-staged) GSPP with orthogonal rotation. The proposed model is able to find good solutions (good upper bounds) for the optimal objective value and more importantly, it is a polynomial model of order O(n^۲), i.e. the number of decision variables (and constraints, as well) is a polynomial of order O(n^۲) in the number of the rectangular items (n). Numerical results show that the solutions obtained from the proposed model are superior to several existing heuristic algorithms in the literature.

کلیدواژه ها:

Packing ، cutting ، guillotine cut ، polynomial model ، mixed-integer programming