Enhanced solution for the irregular strip packing problem: valid inequalities and branching priorities

Vol 53, 2021 - 139354
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

The irregular strip packing problem consists of packing a set of regular and irregular pieces on a board with fixed width and infinite length. All pieces are packed in such a way that they do not overlap while minimizing the used length of the board. Despite a few mathematical models having been proposed in the literature, solving the problem to optimality is still a challenge, and for only very few small instances, it is possible to find an optimal solution. In this paper, we apply a different branching strategy in the branch-and-bound method and add valid inequalities in a mathematical model of the literature. The usage of branching strategies and valid inequalities improve the performance of the commercial solver used to solve the mixed-integer programming model and provide the optimal solution for up to ten instances not proved in the previous paper.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Estadual de Londrina
  • 2 USP - São Carlos
Eixo Temático
  • 15 - PM – Programação Matemática
Palavras-chave
Cutting and packing problems
irregular pieces
mixed-integer programming