Please use this identifier to cite or link to this item: http://ri.ufs.br/jspui/handle/riufs/1654
Document Type: Dissertação
Title: Estudo poliedral do problema do máximo subgrafo induzido comum
Other Titles: Polyhedral study of the maximum common induced subgraph problem
Authors: Piva, Breno
Issue Date: Nov-2009
Abstract: O problema do Máximo Subgrafo Induzido Comum (MSIC) pertence a classe NP-difícil e possui aplicações em diversas áreas. Apesar de sua complexidade, ainda é importante conhecer soluções exatas para instâncias deste problema. Os algoritmos exatos encontrados na literatura buscam resolvê-lo através de técnicas de backtracking ou através de sua redução para o problema da Clique Máxima. Neste trabalho procuramos dar uma solução exata para o MSIC, tratando-o diretamente através da utilização de modelos de Programação Linear Inteira (PLI) e técnicas de combinatória poliédrica. Assim, realizamos um estudo teórico do poliedro do MSIC e fomos capazes de encontrar algumas desigualdades válidas fortes, inclusive com provas de que algumas delas representam facetas daquele poliedro. Adicionalmente, provamos que existe uma equivalâencia entre o modelo PLI aqui apresentado para o MSIC e uma formulação bem conhecida para o problema da Clique Máxima. Posteriormente, foram implementados algoritmos de Branch-and-Bound (B&B) e Branch-and-Cut (B&C) utilizando as desigualdades encontradas e algumas técnicas para tentar tornar os algoritmos mais eficientes. Experimentos foram executados com os algoritmos implementados neste trabalho e, também, com um algoritmo já existente para resolver o problema da Clique, chamado Cliquer. Os resultados foram comparados e, dentre os algoritmos de PLI, constatamos que o mais eficiente foi aquele que utilizou uma formulação para o MSIC que chamamos de Clique-IS, utilizando B&B e técnicas mais básicas que outros algoritmos. Este algoritmo mostrou-se mais eficiente, inclusive, que um algoritmo PLI com um modelo baseado no problema da Clique Máaxima. Este fato sugere que para uma abordagem baseada em PLI, vale a pena utilizar uma formulação do MSIC diretamente, ao invés de uma que se apóie na redução deste para o problema da Clique Máxima. Ja a comparaçao do melhor algoritmo desenvolvido neste trabalho com o Cliquer, mostrou que este último é mais eficiente. Para que um algoritmo baseado em PLI (utilizando uma formulação com as mesmas variáveis usadas por nós) tivesse alguma chance de vencer um algoritmo combinatório como o Cliquer, seria necessário conhecer mais desigualdades que estivessem ativas na solução ótima do problema._________________________________________________________________________________________ ABSTRACT: The Maximum Common Subgraph problem (MSIC) is in MV-hard and has applications in several fields. Despite its complexity, it is still important to know exact solutions for instances of this problem. The exact algorithms found in literature try to solve it through backtracking techniques or through its reduction to the Maximum Clique problem. In this work we try to give an exact solution to MSIC by addressing it directly, using Linear Integer Programming (PLI) and polyhedral combinatorics techniques. So, we performed a study of the MSIC polyhedron and we were able to find some strong valid inequalities, including some that were proven to define facets of that polyhedron. Additionally, we proved that an equivalence between the PLI model presented here for MSIC and a well known formulation for the Maximum Clique problem exists. Later, Branch-and-Bound (B&B) and Branch-and-Cut (B&C) algorithms were implemented using the inequalities found and some techniques to try to render the algorithms more efficient. Experiments were performed with the algorithms implemented in this work and, also, with an already existing algorithm to solve the Maximum Clique problem, called Cliquer. The results were compared and, among the PLI algorithms, we found that the most efficient was the one that used the formulation which we called Clique-IS, using B&B and more basic techniques than other algorithms. This algorithm was even more efficient than a PLI algorithm with a Clique-based model. This fact suggests that for a PLI approach it is worth to use a formulation based on the MSIC polyhedron instead of one based on its reduction to the Maximum Clique problem. The comparison of the best algorithm developed in this work with Cliquer, though, showed that the latest is more efficient. In order to some PLI-based algorithm (using a formulation with the same variables used by us) to have any chance of outperforming a combinatorial algorithm like Cliquer, it would be necessary to know more inequalities that are active in the problem's optimal solution.
Keywords: Máximo subgrafo comum
Combinatória poliédrica
Programação linear inteira
Algoritmo Branch and Bound
Algoritmo Branch and Cut
Maximum common subgraph
Polyhedral combinatorics
Integer programming
Branch and Bound algorithm
Branch and Cut algorithm
Citation: RIBEIRO, B. P. Estudo poliedral do problema do máximo subgrafo induzido comum. 2009. 111 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Estadual de Campinas, Campinas, 2009. Disponível em: <http://www.bibliotecadigital.unicamp.br/document/?code=000477497&fd=y>. Acesso em: 22 fev. 2016.
License: Direitos autorais pertencentes ao(s) autor(es)
URI: https://ri.ufs.br/handle/riufs/1654
Appears in Collections:DCOMP - Departamento de Computação - Teses e Dissertações defendidas em outras instituições

Files in This Item:
File Description SizeFormat 
MaximoSubgrafoInduzido.pdf1,22 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.