Orientador: Marcus Vinicius Soledade Poggi de Aragão

Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação

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 é...

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

Abstract: The proposal of an efficient resolution on method for the Maximum Satisfiability Problem is the object of this work. The motivation for this proposal relies on a special class of instances that can be solved by a linear time algorithm. This class is the one for which the co-occurrence...

Abstract: The proposal of an efficient resolution on method for the Maximum Satisfiability Problem is the object of this work. The motivation for this proposal relies on a special class of instances that can be solved by a linear time algorithm. This class is the one for which the co-occurrence graph associated to the instance is a partial k-tree. It was shown by Crama, Hansen and Jaumard how the Basic Algorithm of Hammer, Rosenberg and Rudeanu, an algebraic method, an solve these instances in linear time. The approach here proposed consists in applying an enumerative method to derive from any general instance several linear time instances that constitute a partition of the solution space. This allows the enumerative and the algebraic approaches to have their tasks simplified. Three strategies of this algebraic-enumerative combination where proposed and implemented. The resulting algorithm where tested on several different data sets. The results where compared with both algebraic and enumerative pure approaches. This work also generalizes Hansen's upper bounds and penalties for non-linear 0-1 programming to the case where complemented and uncomplement variables appear in the product terms. These where also implemented, tested and incorporated to the combined codes