Algoritmos para o problema do subgrafo acíclico máximo sob restrições disjuntivas
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Tese de doutorado
Título alternativo
Primeiro orientador
Membros da banca
Celso da Cruz Carneiro Ribeiro
Geraldo Robson Mateus
Olga Nikolaevna Goussevskaia
Rosiane de Freitas Rodrigues
Geraldo Robson Mateus
Olga Nikolaevna Goussevskaia
Rosiane de Freitas Rodrigues
Resumo
Neste trabalho são abordados os problemas do Subgrafo Acíclico Máximo sob Restri ções Disjuntivas Negativas (SAMRDN) e Subgrafo Acíclico Máximo sob Restrições Disjuntivas Positivas (SAMRDP), ambos pertencentes à classe NPDifícil. Dado um certo par de entidades, para as restrições disjuntivas negativas, no máximo uma delas poderá compor uma solução viável. Já para as restrições disjuntivas positivas, dado um par de entidades, pelo menos uma delas deverá compor uma solução viável. Os problemas SAMRDN e SAMRDP possuem como instância um grafo direcionado G = (V;A) e um grafo não direcionado G = (A;E), que representa as restrições disjuntivas, positivas ou negativas, sob pares de arcos do grafo G. SAMRDN consiste em determinar um subconjunto máximo A0 A para o qual o subgrafo G0 = (V;A0) seja acíclico e A0 seja um conjunto de vértices em G tal que não existam arestas entre dois de seus vértices, ou seja, um conjunto independente em G. SAMRDP consiste em determinar um subconjunto máximo A0 A para o qual o subgrafo G0 = (V;A0) seja acíclico e A0 seja um conjunto de vértices em G tal que toda aresta em E seja incidente em algum vértice de A0, ou seja, uma cobertura por vértices em G. É provado que o problema de decisão sobre a viabilidade de SAMRDP é NP Completo, por uma redução a partir do problema clássico de Cobertura por Vértices. Para SAMRDN, são apresentados seis algoritmos com fator de aproximação constante igual a 1=2 para classes especiais de grafos de restrições, tal que o cálculo de um conjunto independente máximo em G seja polinomial. Dentre os seis algoritmos, três deles seguindo a abordagem denominada late geram soluções com no mínimo a mesma cardinalidade das obtidas com os algoritmos equivalentes, segundo a abordagem early. É proposto um pré-processamento de instâncias para SAMRDN e SAMRDP. Testes experimentais sobre modelos de programação linear inteira dos problemas sugerem que, ao se realizar o pré-processamento, soluções melhores são obtidas, no mesmo tempo de execução. É também apresentado um procedimento de melhoria sobre uma solução inicial de SAMRDN, obtida heuristicamente, que é então vinculado a uma metaheur ística como um método de busca local. Resultados computacionais evidenciam que, para instâncias em que jV j > 200, a heurística é preferível à resolução do modelo de programação inteira por um software comercial.
Abstract
In this work we tackle the Maximum Acyclic Subgraph problem under Negative Disjunctive Constraints (MASNDC) and the Maximum Acyclic Subgraph problem under Positive Disjunctive Constraints (MASPDC), both belonging to the NPHard class. Disjunctive constraints can be negative, in which a certain pair of entities cannot be contained simultaneously in a feasible solution; or positive in that, given a pair of entities, at least one of them must compose a feasible solution. Instances of MASNDC and MASPDC are composed by a directed graph G = (V;A) and a undirected graph G = (A;E), which encodes the disjunctive positive or negative constraints over pairs of arcs of graph G. MASNDC consists in determining a maximum subset A0 A for which the subgraph G0 = (V;A0) is cycle free and A0 is a set of vertices in G such that there are no edges between two of its vertices, namely an independent set at G. MASPDC consists in determining a maximum subset A0 A for which the subgraph G0 = (V;A0) is cycle free and A0 is a set of vertices in G such that every edge in E is incident on some vertex in A0, namely a vertex cover in G. It is proved that the feasibility decision version of MASPDC is NPComplete by a reduction from the classic Vertex Cover problem. For MASNDC we propose six approximation algorithms with constant factor equal to 1=2 for special classes of graph G in which the maximum independent set is polynomial. Among the six algorithms, three of them following the so-called late approach generate solutions with at least the same cardinality of the ones obtained by equivalent algorithms, according to the early approach. We propose a preprocessing of MASPDC and MASNDC instances. Computational experiments on integer linear programming models of both problems suggest that, when performing the preprocessing, solutions of larger cardinalities are obtained, in the same run time. We also proposed an improvement procedure on an heuristically obtained initial solution of MASNDC, which is then linked to a metaheuristic as a local search method. Computational results show that for instances with jV j > 200, the heuristic is preferable to solving the integer programming model by using a commercial software.
Assunto
Algoritmos, Análise combinatória, Computação
Palavras-chave
Algoritmos, Restrições disjuntivas, Análise combinatória, Subgrafo acíclico máximo