MIP models for the irregular strip packing problem: new symmetry breaking constraints

Autor(es)

Rodrigues, Marcos Okamura ; Cherri, Luiz Henrique ; Mundim, Leandro Resende ; Hochreiter, R

• Tipo de documento: Artigo Científico
• Fonte: 12TH INTERNATIONAL CONFERENCE APPLIED MATHEMATICAL PROGRAMMING AND MODELLING-APMOD 2016; v. 14, p. 7-pg., 2017-01-01.

Resumo

The irregular strip packing problem consists in minimizing the length used to cut a set of pieces from a board with fixed width. Recently, a mixed integer programming model was proposed for the problem, but it may allow a large number of symmetric solutions. In this paper, new symmetry breaking constraints are proposed to improve the model. Computational experiments were performed for instances with convex pieces. The results show the proposed formulation is better than the previous one for most instances, since it improves lower bounds and reduces run-time and number of nodes explored to prove optimality. (AU)

• Processo FAPESP: 12/18653-8 - O problema de corte de peças irregulares
• Beneficiário: Luiz Henrique Cherri
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 14/23900-0 - Problemas de corte e empacotamento de itens irregulares e quasi-poliominós
• Beneficiário: Marcos Okamura Rodrigues
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 15/24987-4 - Corte de peças irregulares: métodos e aplicações
• Beneficiário: Luiz Henrique Cherri
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 10/10133-0 - Problemas de corte, empacotamento, dimensionamento de lotes e programação da produção, e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático