Metodos algebrico-enumerativos para o problema de maxima satisfatibilidade ponderada

AUTOR(ES)
DATA DE PUBLICAÇÃO

1995

RESUMO

Este trabalho tem como tema central a proposta de um método de resolução eficiente do Problema de Máxima Satisfatibilidade Ponderada. Esta proposta tem sua motivação em uma classe de instâncias deste problema que pode ser resolvida em tempo polinomial. A classe de interesse neste trabalho é a das instâncias cujo grafo de co-ocorrência associado é uma k-árvore. O algoritmo capaz de resolve-lo em tempo linear é um método algébrico conhecido como Algoritmo Fundamental de Hammer, Rosenberg e Rudeanu em sua versão modificada proposta por Crama, Hansen e laumard. A abordagem deste trabalho está na utilização de métodos enumerativos, branch &bound como são mais frequentemente citados, de modo a transformar instâncias gerais em instâncias pertencentes à classe de interesse. Deste modo, tanto a enumeração como a resolução algébrica podem ter suas tarefas simplificadas. Três estratégias para esta combinação algébrico-enumerativa foram propostas e implementadas. Os algoritmos resultantes foram extensivamente testados em diferentes conjuntos de instâncias, sendo seus resultados comparados com implementações dos algoritmos puramente algébrico e puramente enumerativo. Esse trabalho apresenta também uma generalização dos limites superiores propostos por Hansen para programação não-linear 0-1 para o caso em que variáveis complementadas são incorporadas aos termos. Esses limites além de integrados ao método proposto, foram implementados e testados individualmente

ASSUNTO(S)

programação não-linear otimização combinatoria

ACESSO AO ARTIGO

Documentos Relacionados