Modelos e algoritmos para o problema de minimização de padrões

Abstract

Nesta dissertação, estudamos um problema de optimização combinatória designado por Problema de Minimização de Padrões. O problema é um problema de corte no qual se consideram custos de setup. Existe um número muito reduzido de métodos para a resolução exacta do Problema de Minimização de Padrões. Aqueles que são descritos na literatura apenas permitem resolver algumas instâncias de pequena dimensão. Com esta dissertação, pretendemos contribuir para a resolução exacta do problema explorando um modelo que foi proposto recentemente na literatura. Os modelos de Programação Inteira propostos na literatura são descritos na primeira parte do texto. Descrevemos também os algoritmos exactos que foram definidos com base nesses modelos e apresentamos algumas das melhores heurísticas de resolução que foram desenvolvidas para este problema. Na segunda parte da dissertação, analisamos em detalhe um modelo proposto recentemente na literatura para o Problema de Minimização de Padrões. Esse modelo é um modelo de Programação Inteira, obtido com base numa nova decomposição de um modelo não-linear. Exploramos formas de reforçar esse modelo, e analisamos algoritmos que permitam obter soluções óptimas inteiras a partir do método de partição e avaliação e do método de geração de colunas. A diferença entre os algoritmos reside nas regras de partição que foram usadas. É sabido que combinar o método de partição e avaliação com o método de geração de colunas não é trivial. A partição feita com base nas variáveis do modelo de geração de colunas provoca a regeneração das colunas presentes no problema mestre. A forma de evitar esse problema passa por aumentar a complexidade do subproblema. Nesta dissertação, as regras de partição são baseadas em variáveis originais, e como tal não alteram significativamente a dificuldade dos subproblemas de geração de colunas. Foram conduzidos experiências computacionais para avaliar a qualidade dos esquemas de partição propostos. Essas experiências foram realizadas usando instâncias da literatura, e sem recorrer a qualquer heurística. Os resultados das experiências são apresentados no final da dissertação.

In this dissertation, we study a combinatorial optimization problem called the Pattern Minimization Problem. The problem is a cutting stock problem in which setup costs are considered. The number of exact algorithms that were proposed in the literature for this problem is very small. Those that were proposed can only solve a limited number of small and medium instances. With this dissertation, our aim is to contribute to the exact resolution of this problem by exploring a model that was proposed recently in the literature. The Integer Programming models proposed in the literature are described in the first part of this text. We also describe the exact algorithms that were defined based on these models and we present the best heuristics that were developed to solve this problem. In the second part of this dissertation, we analyse in detail a model proposed recently in the literature for the Pattern Minimization Problem. This model is an Integer Programming model that is obtained by applying a new decomposition to a non-linear model. We explore ways of strengthening the model, and we analyse algorithms for computing integer solution using the branch-and-bound method and the column generation method. The difference among our algorithms is in the branching scheme that is used. It is well known that combinig branch-and-bound with column generation is not trivial. When the partition is done on the variables of the column generation model, regeneration occurs. To avoid this regeneration, we have to increase the complexity of the pricing subproblem. In this dissertation, the branching rules are based on original variables and hence the complexity of the subproblem is almost unchanged. Computational experiments were conducted to evaluate the quality of the branching schemes proposed. These experiences were conducted on instances from the literature, and without using any heuristic. The results of these experiments are presented at the end of this dissertation.