Symmetry-breaking constraints for packing identical rectangles within polyhedra

Autor(es)

Andrade, R. ^[1] ; Birgin, E. G. ^[1]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Dept Comp Sci, Inst Math & Stat, BR-05508090 Sao Paulo - Brazil

• Tipo de documento: Artigo Científico
• Fonte: Optimization Letters; v. 7, n. 2, p. 375-405, FEB 2013.
• Citações Web of Science: 4

Resumo

Two problems related to packing identical rectangles within a polyhedron are tackled in the present work. Rectangles are allowed to differ only by horizontal or vertical translations and possibly 90A degrees rotations. The first considered problem consists in packing as many identical rectangles as possible within a given polyhedron, while the second problem consists in finding the smallest polyhedron of a given type that accommodates a fixed number of identical rectangles. Both problems are modeled as mixed integer programming problems. Symmetry-breaking constraints that facilitate the solution of the MIP models are introduced. Numerical results are presented. (AU)

• 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
• Processo FAPESP: 06/53768-0 - Métodos computacionais de otimização
• Beneficiário: José Mário Martinez Perez
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 09/10241-0 - Teoria e software em métodos computacionais de otimização
• Beneficiário: Ernesto Julián Goldberg Birgin
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 06/03496-3 - Teoria e prática dos problemas de corte e empacotamento
• Beneficiário: Marcos Nereu Arenales
• Modalidade de apoio: Auxílio à Pesquisa - Temático