Mathematical models for the irregular packing problem

Author(s)

Marcos Okamura Rodrigues

• Document type: Master's Dissertation
• Press: São Carlos.
• Institution: Universidade de São Paulo (USP). Instituto de Ciências Matemáticas e de Computação (ICMC/SB)
• Defense date: 2015-02-11

Examining board members

Franklina Maria Bragion de Toledo; Marina Andretta; Guilherme Pimentel Telles

• Advisor: Franklina Maria Bragion de Toledo

Abstract

The irregular strip packing problem consists of cutting a set of two-dimensional pieces from an object of fixed width using the smallest possible length. Despite its economic importance for many industrial sectors, few exact studies have been made on this problem due to its difficulty of resolution. Recently, Toledo et al. (2013) proposed a mixed-integer model to this problem in which the pieces are placed on a grid. This model has worked successfully proving the optimality for instances up to 21 pieces. However, the model has a large number of non-overlapping constraints, which grows quickly in accordance with the discretization resolution and number of distinct pieces. In this work, we propose new mathematical formulations based on this model in order to reduce the number of constraints. In the first approach, we present two reduced models that have shown to be effective for instances with few repetitions of pieces. In the second approach, it was proposed a clique covering model for the problem. This model achieved a greater or equal performance than the literature for all instances, getting an optimal solution for instances up to 28 pieces. (AU)

• FAPESP's process: 13/14147-3 - Mathematical models for the irregular strip packing problem
• Grantee: Marcos Okamura Rodrigues
• Support Opportunities: Scholarships in Brazil - Master