Mapas de símbolos proporcionais e a meia integralidade da cobertura de vértices

Julho 31, 2011

O problema que ataquei no mestrado consistia em achar uma ordem de empilhamento entre símbolos em um mapa, de modo a maximizar uma dada função objetivo. Não se sabe a complexidade desse problema e por isso usei programação linear inteira.

Há uma variante desse problema, que consiste em maximizar uma outra função objetivo, para a qual existe um algoritmo polinomial.

Depois de obter as soluções para o meu problema, precisei fazer uma comparação entre as soluções desses dois problemas. Aconteceu que a diferença visual entre as duas soluções não é tão perceptível, sendo que apenas alguns discos estão em posição diferente. Para se ter uma idea, veja um dos casos


Jogo dos 7 erros ;) (clique na imagem para aumentar)

Decidi fazer um programa para destacar apenas os discos que mudaram de lugar. A minha primeira ideia foi marcar todos os discos que estavam em níveis diferentes entre as duas soluções.

Isso não funciona bem quando temos duas componentes disjuntas de discos, por exemplo na figura abaixo, com duas componentes disjuntas {A, B, C} e {D, E}. Note que as ordens {A > B > C > D > E} e {D > E > A > B > C} resultam visualmente na mesma figura, embora nenhum disco esteja exatamente na mesma posição na ordenação e portanto o programa vai marcar todos os discos.

Desenho que pode ser representado por mais de uma ordem dos discos

Uma segunda ideia foi marcar, considerando todos os pares de discos que se interceptam, apenas aqueles em que a ordem relativa do par foi invertida. Com essa estratégia, nenhum disco do exemplo acima seria destacado, o que está de acordo com nossas expectativas.

Porém, essa abordagem ainda apresenta um efeito indesejável. Se tivermos uma pilha de discos, onde todos se interceptam e um disco que está no topo em uma solução aparece na base na outra, sendo que todos os outros discos permaneceram intactos, como por exemplo {A > B > C > D} e {B > C > D > A}, ainda assim todos os discos serão destacados pois todos os pares formados com A tiveram sua ordem relativa invertida. Note que seria suficientemente informativo destacar apenas o disco A.

Assim, para todo par de discos que se intercepta, basta destacarmos um deles. Como então destacar o menor número possível para diminuir a poluição visual?

Se olharmos para o grafo de discos desse problema, existem algumas arestas que queremos destacar (cobrir), usando pelo menos um dos vértices mas tentando minimizar a quantidade desses vértices. Soa familiar?

Sim, reduzimos para o problema da cobertura de vértices (vertex cover).

Cobertura de vértices

O problema da cobertura de (arestas por) vértices é sabidamente NP-difícil. Assim, é pouco provável um algoritmo polinomial para resolvê-lo de maneira ótima. No meu trabalho, usei uma heurística simples: percorra os vértices começando por aqueles de maior grau. Se todas as arestas incidentes a esse vértice já foram cobertas por algum vértice da cobertura, ignore-o. Caso contrário adicione-o à cobertura.

Aplicando esse algoritmo nas figuras do começo do post, ficamos com o seguinte resultado:

Ficou mais fácil encontrar as diferenças entre as soluções (clique na imagem para aumentar)

Esse método ainda tem um problema que é quando um par de discos tem sua ordem relativa trocada, mas a parte que foi visualmente modificada está encoberta por um outro disco. Um exemplo disso pode ser visto no canto inferior direito da figura acima. Para consertar esse problema teríamos que fazer um pré-processamento e só considerar vértices cujos discos têm alguma parte do seu borda diferente entre uma solução e outra.

Modelo de programação linear

Como não poderia deixar de ser, apresento aqui o modelo de programação linear inteira da versão mais geral desse problema, na qual os vértices têm um custo associado. Dado um grafo G = (V, E) com uma função de custo c : V \rightarrow \mathbb{R}^+, definimos a variável binária x_v para cada v \in V, que vale 1 se o vértice v está na cobertura e 0 caso contrário. O modelo então fica:

Sujeito a

(1) Para todo (u, v) \in E,

(2) Para todo v \in V,

Meia integralidade

O modelo apresentado tem uma propriedade interessante chamada de meia-integralidade. Isso quer dizer que, dada a relaxação linear desse modelo, existe uma solução ótima onde os valores das variáveis x_v são 0, 1/2 ou 1. A prova é relativamente curta e está descrita na Seção 14.3 de [1].

Assim, dada uma solução fracionária do modelo, podemos usar a técnica de arredondamento, criando uma solução x'_v com x'_v = 1 sempre que x_v \ge 1/2. É possível mostrar que essa solução é uma cobertura de vértices válida e que seu custo não é maior do que 2 vezes o valor da solução ótima, resultando em um algoritmo 2-aproximado.

Referências

[1] Approximation Algorithms – Vijay V. Vazirani (2003)

Anúncios

Formulações do TSP

Março 4, 2011

O problema do caixeiro viajante (do inglês Traveling Salesman Problem, abreviado como TSP) é o problema mais conhecido e estudado em otimização combinatória. Creio que alguns dos motivos para isso seja sua definição simples, sua dificuldade e sua aplicabilidade prática.

A definição é de fato simples. Imagine que você tem n cidades e entre cada par de cidades existe uma rodovia com uma dada distância. Você deseja partir de uma das cidades, percorrer as outras exatamente uma vez e então retornar para a cidade de origem de forma a minimizar a distância percorrida. Em termos de teoria de grafos, dado um grafo completo de n vértices e custo nas arestas, encontrar um ciclo com exatamente n vértices de menor custo.

O TSP é conhecidamente NP-difícil. Porém, entre os problemas NP-difíceis, há ainda uma diferença na dificuldade entre eles. Algoritmos de aproximação podem dar uma noção dessa diferença. Alguns problemas admitem algoritmos com fatores de aproximação arbitrariamente próximos de 1, enquanto outros não admitem sequer fator de aproximação constante.

O problema da mochila por exemplo, é um dos problemas NP-difíceis mais “tratáveis”. Ele pertence à classe dos PTAS (Polynomial Time Approximation Scheme), o que significa que ele pode ser aproximado por um fator tão próximo de 1 quanto se queira, embora o tempo de execução aumente em função dessa proximidade. Por outro lado, a versão geral do TSP não pode ser aproximada por um fator constante a menos que P = NP. Por isso, o algoritmo do TSP é um dos problemas mais difíceis da computação, embora afirma-se que abelhas saibam resolvê-lo.

Formulações

Há pelo menos três formulações de programação linear inteira para esse problema. Uma delas foi publicada em 1960, por Miller, Tucker e Zemlin e que denominaremos MTZ, é baseada em fluxos em redes. Considere um grafo direcionado completo D(V, A) de n nós e custo nas arestas. Seja uma variável binária que vale 1 se a aresta (i,j) está na solução, e 0 caso contrário. Denotando o custo de uma aresta (i,j) por , a função objetivo é simplesmente

Como queremos encontrar um ciclo que passe por todos os vértices, cada vértice deve ter exatamente uma aresta entrando e outra saindo, o que é gatantido com as seguintes restrições

(1) Para todo

(2) Para todo

Somente com essas restrições, as soluções serão coberturas de vértices por ciclos, ou seja, teremos um ou mais ciclos de forma que cada vértice estará contido em exatamente um ciclo. A ideia dos autores de [1] é introduzir variáveis representando potenciais de um vértice v. Sempre que uma aresta (i,j) é usada, o potencial do vértice j tem que ser maior do que i. Isso criará um impedimento na criação de ciclos, da mesma maneira do modelo para o caminho mais longo, conforme esse post anterior.

Porém, isso também impedirá a formação do ciclo que estamos procurando. O truque é não usar essa restrição sobre um dos vértices, por exemplo o vértice 1. Dessa forma as desigualdades impedirão quaisquer soluções que contenham subciclos que não incluam o vértice 1. As únicas soluções que satisfarão isso, além de (1) e (2), são os ciclos de tamanho n. A desigualdade fica,

(3) Para todo

Onde M é uma constante suficientemente grande. Se , a desigualdade fica redundante. Se , forçamos .

A segunda que vamos apresentar é devido a Dantzig, Fulkerson e Johnson, ou DFJ. O modelo possui as variáveis e as restrições (1) e (2). A diferença fica por conta da eliminação de subciclos.

(4) Para todo

É possível mostrar que se, para um subconjunto não-próprio S de V, existem |S| ou mais arestas, então existe pelo menos um ciclo. O problema é que o número de desigualdades (4) é exponencial e para isso um algoritmo de planos de corte, como o Branch and Cut, deve ser usado. Uma maneira de reduzir o número dessas desigualdades é observar que se uma solução satisfaz (1) e (2) e existe um subciclo de tamanho maior do que |S|/2, então existe um subciclo de tamanho menor do que |S|/2, de forma que podemos considerar as desigualdades (4) apenas para

Uma outra maneira de se eliminar subciclos é através das desigualdade chamadas cut set constraints, dadas por

(5) Para todo

A ideia aqui é que dada uma cobertura por ciclos contendo subciclos, existe uma maneira de separar o conjunto de vértices em 2, de forma que cada subciclo fique exatamente de um dos lados, ou seja, nenhum aresta “cruza” essa partição. Note que o número de desigualdades (5) também é exponencial.

Conclusão

Embora o modelo MTZ tenha sido desenvolvido depois do DFJ, e tenha um número polinomial de desigualdades, na prática o DFJ é bem mais eficiente. A explicação pode ser dada pela combinatória poliédrica, já que é possível mostrar que o modelo DFJ está contido no MTZ. Em um post futuro, pretendo apresentar um esboço dessa prova.

Uma questão que surgiu ao estudar as formulações é a relação entre os modelos com a desigualdade (4) e (5). Serão eles equivalentes? Um está contido no outro? Essa é outra pergunta que pretendo pesquisar.

Referências

[1] Miller, Tucker and Zemlin — Integer Programming Formulation of Traveling Salesman Problems
[2] Dantzig, Fulkerson and Johnson — Solution of a Large-Scale Traveling-Salesman Problem


Disk Graphs

Outubro 1, 2010

Semana passada teve início a série de seminários em teoria de computação dos membros do Laboratório de Otimização e Combinatória. Essas palestras ocorrerão intercaladas com os seminários do DTC (Departamento de Teoria de Computação), ocorrendo, a priori, às Sextas-feitas, 10h. Acabei estreando essa série com uma palestra intitulada “Disk Graphs”. A ideia central era definir a classe de grafos chamada disk graphs e mostrar dois problemas clássicos de teoria dos grafos sobre essa classe: o problema da clique máxima e da coloração. Neste post, vou apresentar um pequeno resumo da apresentação (disponível aqui).

Dado um conjunto de discos no plano, definimos um grafo com vértices correspondendo aos centros dos discos. Dois vértices são conectados por uma aresta se seus discos correspondentes se interceptam com área não nula. Denominamos tal grafo Disk Graph (DG).

Exemplo de Disk Graph

Um Disk Graph onde todos os discos têm mesmo tamanho é chamado de Unit Disk Graph.

Exemplo de Unit Disk Graph

No caso particular em que os discos não podem se sobrepor, apenas se tangenciar, chamamos o DG de Coin Graph (CG).

Exemplo de um Coin Graph

Em seguida falei sobre a relação entre diferentes classes de grafos. A mais interessante é devido ao Teorema de Koebe (também conhecido como circle packing theorem) que diz basicamente que grafos planares e coin graphs são equivalentes. Eu desconfiava que todo grafo planar é também um disk graph. O prof. Stolfi, que estava presente, provou com um argumento bem simples: dado um coin graph, a menor distância entre bordos de discos que não se tangenciam é positiva, enquanto a de discos que se tangenciam é exatamente 0. Assim, existe um valor suficientemente pequeno do qual podemos aumentar o raio dos discos de forma que os círculos tangentes passem a ter interseção não nula e os não tangentes assim continuem.

Problemas

Um aspecto importante ao enunciar um problema para essa classe de grafos é especificar se a entrada é dada na forma de discos ou na forma de grafo. Observe que se for dada na primeira forma, conseguimos obter a segunda. Porém, mesmo para unit disk graphs, se a entrada estiver na forma de grafo, foi provado que é NP-difícil encontrar um conjunto de discos que formem tal grafo [1]. (Para coin graphs existe um algoritmo que constrói o conjunto de discos a partir de um grafo planar [2]). Para os problemas apresentados, vamos assumir que a entrada é dada na forma de discos.

Primeiramente apresentei o problema da clique máxima para unit disk graphs. Embora seja NP-difícil encontrar a clique máxima em um grafo geral, para unit disk graphs, existe um algoritmo polinomial . Não se sabe, porém, se o problema da clique máxima para disk graphs está em P ou NP.

Depois apresentei o problema da coloração, que continua NP-difícil, mesmo para unit disk graphs e a entrada sendo dada na forma de discos. Foram desenvolvidos algoritmos aproximados e algoritmos online para unit disk graphs e disk graphs. Para unit disk graphs o melhor algoritmo aproximado até agora tem fator de aproximação 3 (limite superior), sendo que não existe algoritmo aproximado com melhor fator de aproximação menor do que 4/3 (limite inferior) a não ser que P=NP. O melhor algoritmo online tem fator de competitividade 5 (limite superior) e não existe algoritmo com fator de competitividade menor do que 2 (limite inferior) a menos que P=NP. Para disk graphs, o algoritmo aproximado tem limites inferior e superior iguais a 4/3 e 5, respectivamente, e o algoritmo online tem ambos limites inferior e superior iguais a log n, ou seja, o algoritmo online para unit disk graphs é o melhor que se pode conseguir.

Sumário com os limites dos fatores de aproximação e competitividade.

Aplicações

Na palestra acabei não falando das aplicações práticas dos disks graphs. Porém, eles são muito utilizados para projetar topologias de rede wireless. Podemos pensar que cada disco representa uma antena wireless posicionada no centro do disco, com alcance equivalente ao raio do mesmo. Assim, o problema da coloração pode ser usado para encontrar uma atribuição de frequências às antenas, considerando que há interferência entre os sinais de antenas cujos círculos se interceptam.

Referências

[1] Breu, H. and Kirkpatrick, D. G. – Unit Disk graph recognition is NP-Hard
[2] Collins, C. R. and K, Stephenson – A Circle packing algorithm