Cláudio Alves
Centro de Investigação Algoritmi, Universidade do Minho

Rita Macedo
Centro de Investigação Algoritmi, Universidade do Minho

José Manuel Valério de Carvalho
Dep. Produção e Sistemas - Universidade do Minho

Abstract: The Pattern Minimization Problem is a combinatorial optimization problem that consists in finding the cutting plan with the minimum number of different patterns. The problem has been mainly solved using heuristics. There are very few exact resolution approaches described in the literature. In this paper, we present results for a new and fast lower bound based on a Constraint Programming model that allows to handle efficiently the most complex constraints of the problem. The preliminary results obtained from a set of instances from the literature show that the computational times necessary to obtain the lower bound are very small. In some cases, our lower bound is even stronger than the continuous bound obtained through the best column generation model described so far.

Resumo: O Problema de Minimização de Padrões é um problema de optimização combinatória que consiste em determinar o plano de corte com o menor número de padrões diferentes. Esse problema tem sido essencialmente abordado através de procedimentos heurísticos, sendo muito poucas as contribuições descritas na literatura relativas a abordagens de resolução exacta. Neste artigo, apresentamos resultados preliminares para um novo limite inferior que é calculado em tempos computacionais que superam outras abordagens ao nível do estado-da-arte. Para calcular o limite, usamos um modelo de Programação por Restrições que incorpora de forma eficiente as restrições mais complexas do Problema de Minimização de Padrões. Os resultados que obtivemos em instâncias da literatura mostram que o limite inferior é obtido em tempos computacionais muito reduzidos. Em alguns casos, é mesmo mais forte que o limite contínuo obtido através do melhor modelo de geração de colunas descrito até agora.

Keywords: problema de minimização de padrões, programação inteira, programação por restrições, limites inferiores.