Um novo limite inferior
baseado num modelo de programação por restrições para o problema de minimização
de padrões
Cláudio Alves, Rita Macedo, José Valério de Carvalho
Investigação Operacional, vol. 28, pp. 163-174, 2008
ABSTRACT
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.
BIBTEX ENTRY
@article{AlvesMacedoCarvalhoIO08,
author = {Cl{\'a}udio Alves and Rita Macedo and Jos{\'e} Val{\'e}rio de Carvalho},
title = {Um novo limite inferior
baseado num modelo de programa\c{c}{\~a}o por restri\c{c}{\~o}es para o problema de minimiza\c{c}{\~a}o
de padr{\~o}es},
journal = {Investiga\c{c}{\~a}o Operacional},
volume = {28},
year = {2008},
pages = {163-174} }