Mixed integer quadratically-constrained programming model to solve the irregular strip packing problem with continuous rotations

Luiz H. Cherri (), Adriana C. Cherri and Edilaine M. Soler
Additional contact information
Luiz H. Cherri: University of São Paulo
Adriana C. Cherri: Universidade Estadual Paulista
Edilaine M. Soler: Universidade Estadual Paulista

Journal of Global Optimization, 2018, vol. 72, issue 1, No 6, 89-107

Abstract: Abstract The irregular strip packing problem consists of cutting a set of convex and non-convex two-dimensional polygonal pieces from a board with a fixed height and infinite length. Owing to the importance of this problem, a large number of mathematical models and solution methods have been proposed. However, only few papers consider that the pieces can be rotated at any angle in order to reduce the board length used. Furthermore, the solution methods proposed in the literature are mostly heuristic. This paper proposes a novel mixed integer quadratically-constrained programming model for the irregular strip packing problem considering continuous rotations for the pieces. In the model, the pieces are allocated on the board using a reference point and its allocation is given by the translation and rotation of the pieces. To reduce the number of symmetric solutions for the model, sets of symmetry-breaking constraints are proposed. Computational experiments were performed on the model with and without symmetry-breaking constraints, showing that symmetry elimination improves the quality of solutions found by the solution methods. Tests were performed with instances from the literature. For two instances, it was possible to compare the solutions with a previous model from the literature and show that the proposed model is able to obtain numerically accurate solutions in competitive computational times.

Keywords: Mixed integer non-linear programming; Nesting problems; Irregular pieces; Continuous rotations (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-018-0638-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:72:y:2018:i:1:d:10.1007_s10898-018-0638-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-018-0638-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().