A clique covering MIP model for the irregular strip packing problem

Citation data:

Computers & Operations Research, ISSN: 0305-0548, Vol: 87, Page: 221-234

Publication Year:
Usage 142
Abstract Views 142
Captures 15
Readers 15
Social Media 106
Shares, Likes & Comments 106
Citations 2
Citation Indexes 2
Marcos Okamura Rodrigues; Franklina M.B. Toledo
Elsevier BV
Computer Science; Mathematics; Decision Sciences
article description
The irregular strip packing problem consists in the cutting of a set of two-dimensional pieces from an object of fixed width using the minimum possible length. Despite its economic importance for many industries, few exact studies have addressed this problem. Recently, a mixed integer programming model in which pieces are placed on a grid has been proposed. Although the model has proved the optimality for some large instances, it has a large number of non-overlap constraints, which grows quickly according to the discretization resolution and number of distinct pieces. This paper proposes a clique covering model to reduce the number of constraints and improve the linear relaxation. The model has outperformed the previous model in most evaluated instances and obtained an optimal solution for instances with up to 25 pieces (22 distinct pieces) subject to grid discretization.