Orientador: Marcus Vinicius Soledade Poggi de Aragão / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-20T17:26:15Z (GMT). No. of bitstreams: 1
Parreira_AndersonDelcio_M.pdf: 2926539 bytes, checksum: 1988c6c0a1469a2fe4ef22acd76a154d (MD5)
Previous issue date: 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 / 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 / Mestrado / Mestre em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unicamp.br:REPOSIP/276104 |
| Date | 10 August 1995 |
| Creators | Parreira, Anderson Delcio |
| Contributors | UNIVERSIDADE ESTADUAL DE CAMPINAS, Aragão, Marcus Vinicius Soledade Poggi de, 1959- |
| Publisher | [s.n.], Universidade Estadual de Campinas. Instituto de Matemática, Estatística e Ciência da Computação, Programa de Pós-Graduação em Ciência da Computação |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | 108f. : il., application/octet-stream |
| Source | reponame:Repositório Institucional da Unicamp, instname:Universidade Estadual de Campinas, instacron:UNICAMP |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0026 seconds