info.info-ds
Resumo N e ste trabalho, apresentamos três algoritmos enumerativos para o problema da clique máxima ponderada. Todos eles dependem de uma ordenação inicial dos vértices do grafos. Duas ordens são consideradas, em função dos pesos dos vértices ou dos pesos de seus vizinhos no grafo, levando a duas versões de cada algoritmo. O primeiro algoritmo, denominado BITCLIQUE, é um Branch & Bound combinatório. Ele combina de forma efetiva adaptações de várias ideias já empregadas com sucesso para resolver o problema, como a ação de uma heurística de coloração ponderada inteira, para definir limites superiores assim como regras de poda e ramificação, e o uso de vetores de bits, como estrutura de dados para simplificar operações sobre o grafo.O algoritmo proposto supera os algoritmos de Branch & Bound do estado da arte na maior parte das instâncias analisadas tanto na quantidade de subproblemas enumerados quanto no tempo de computação demandado.

O segundo é um algoritmo de Bonecas Russas, denominado BITRDS, que incorpora ao método uma estratégia de poda e ramificação baseada em coloração ponderada. Testes computacionais demonstram que BITRDS reduz a quantidade o número de subproblemas quando o tempo de execução quando comparado com o melhor algoritmo de Bonecas Russas para o problema em instâncias aleatórias com densidade superior 50%. Essa diferença cresce à medida que a densidade do grado aumenta. Além disso, BITRDS mostra-se competitivo com BITCLIQUE, obtendo melhor desempenho em instâncias aleatórias com densidade entre 50% e 80%.

Por último, apresentamos uma cooperação entre o método de Bonecas Russas e o método de Busca por Resolução. O algoritmo proposto, denominado BITBR, utiliza tanto a coloração ponderada quanto o limite superior dado pelas bonecas para encontrar um nogood. O algoritmo híbrido reduz o número de chamadas à heurística de coloração, chegando até 1 ordem de magnitude, quando comparamos com BITRDS. Porém, essa redução diminui o tempo de execução apenas em poucas instâncias.

Diversos experimentos computacionais são realizados com os algoritmos propostos e os principais algoritmos do estado da arte. Resultados computacionais são apresentados para cada algoritmo utilizando as principais instâncias disponíveis na literatura. Finalmente, futuras direções de pesquisas são discutidas.

Résumé

D

ans ce travail, nous présentons trois nouveaux algorithmes pour le problème de la clique de poids maximum. Les trois algorithmes dépendent d'un ordre initial des sommets. Deux ordres sont considérés, l'un en fonction de la pondération des sommets et l'autre en fonction de la taille voisinage des sommets. Le premier algorithme, que nous avons appelé BITCLIQUE, est une algorithme de séparation et évaluation. Il réunit efficacement plusieurs idées déjà utilisées avec succès pour résoudre le problème, comme l'utilisation d'une heuristique de coloration pondérée en nombres entiers pour l'évaluation ; et l'utilisation de vecteurs de bits pour simplifier les opérations sur le graphe. L'algorithme proposé surpasse les algorithmes par séparation et évaluation de l'état de l'art sur la plupart des instances considérées en terme de nombre de sous-problèmes énumérés ainsi que en terme de temps d'exécution.

La seconde version est un algorithme des poupées russes, BITRDS, qui intègre une stratégie d'évaluation et de ramification de noeuds basée sur la coloration pondérée. Les simulations montrent que BITRDS réduit à la fois le nombre de sous-problèmes traités et le temps d'exécution par rapport à l'algorithme de l'état de l'art basée sur les poupées russes sur les graphes aléatoires avec une densité supérieure à 50

Enfin, nous présentons une coopération entre la méthode poupées russes et la méthode de "Resolution Search". L'algorithme proposé, appelé BITBR, utilise au même temps la coloration pondérée et les limites supérieures donnés par les poupées pour trouver un "nogood". L'algorithme hybride réduit le nombre d'appels aux heuristiques de coloration pondérée, atteignant jusqu'à 1 ordre de grandeur par rapport à BITRDS.

Plusieurs simulations sont réalisées avec la algorithmes proposés et les algorithmes de l'état de l'art. Les résultats des simulations sont rapportés pour chaque algorithme en utilisant les principaux instances disponibles dans la littérature. Enfin, les orientations futures de la recherche sont discutées.

Abstract

I

n this work, we present three new exact algorithms for the maximum weight clique problem. The three algorithms depend on an initial ordering of the vertices. Two ordering are considered, as a function of the weights of the vertices or the weights of the neighborhoods of the vertices. This leads to two versions of each algorithm.

The first onde, called BITCLIQUE, is a combinatorial Branch & Bound algorithm.

It effectively combines adaptations of several ideas already successfully employed to solve the problem, such as the use of a weighted integer coloring heuristic for pruning and branching, and the use of bitmap for simplifying the operations on the graph.

The proposed algorithm outperforms state-of-the-art Branch & Bound algorithms in most instances of the considered in terms of the number of enumerated subproblems as well in terms of computational time

The second one is a Russian Dolls, called BITRDS, which incorporates the pruning and branching strategies based on weighted coloring. Computational tests show that BITRDS reduces both the number of enumerated subproblems and execution time when compared to the previous state-of-art Russian Dolls algorithm for the problem in random graph instances with density above 50%. As graph density increases, this difference increases. Besides, BITRDS is competitive with BITCLIQUE with better performance in random graph instances with density between 50% and 80%.

Finally, we present a cooperation between the Russian Dolls method and the Resolution Search method. The proposed algorithm, called BITBR, uses both the weighted coloring and upper bounds given by the dolls to find a nogood. The hybrid algorithm reduces the number of coloring heuristic calls, reaching up to 1 order of magnitude when compared with BITRDS. However, this reduction decreases the execution time only in a few instances.

Several computational experiments are carried out with the proposed and state-of-the-art algorithms. Computational results are reported for each algorithm using the main instances available in the literature. Finally, future directions of research are discussed. 

Sumário

Capítulo 1 Introdução

O problema da clique ponderada máxima (CLIQUE PONDERADA) pode ser apresentado da seguinte maneira: dado um grafo G com peso w(v) associado a cada vértice v ∈ V (G), encontre uma clique C (ou seja, um subconjunto de vértices adjacentes entre si) tal que a soma dos pesos dos vértices em C seja a maior possível.

Este problema é N P-difícil, mesmo quando todos os pesos são iguais [Karp 1972].

Quando isso acontece, ele é referenciado simplesmente como o problema da clique máxima (CLIQUE).

O problema CLIQUE é um dos mais estudados em otimização combinatória.

Além de ser equivalente a outros problemas centrais em teoria dos grafos, como conjunto independente máximo (Ver Capítulo 2), ele aparece frequentemente como subestrutura em vários problemas importantes de otimização combinatória.

Em termos práticos, CLIQUE tem um extenso número de aplicações em diversas áreas. A restrição de adjacência que aparece em CLIQUE pode representar, por exemplo, a escolha de elementos não-conflitantes de um conjunto (faixas de frequência, horários escolares) ou ainda de elementos que compartilhem um recurso (atividades de um mesmo operador, atores de uma certa comissão). Dentre as aplicações citadas na literatura, encontramos: Seleção de projetos [Christofides 1975].

Economia [START_REF] Boginski | Mining market data: A network approach[END_REF]. Teoria de Códigos [Brouwer et al. 1990, Sloane 1989].

Bioinformática e Computação biológica [START_REF] Tomita | [END_REF], Butenko e Wilhelm 2005].

Visão Computacional [START_REF] Hotta | A view-invariant human face detection method based on maximum cliques[END_REF].

Robótica [Segundo et al. 2010].

Determinação de vencedores em leilões combinatórios [START_REF] Wu E Hao ; Wu | Solving the winner determination problem via a weighted maximum clique heuristic[END_REF].

Redes Sociais [McClosky e Hicks 2012, Trukhanov et al. 2013, Gschwind et al. 2015].

Devido a sua grande importância, existem três levantamentos bibliográficos sobre o problema [START_REF] Pardalos E Xue | [END_REF], Bomze et al. 1999[START_REF] Wu E Hao ; Wu | A review on algorithms for maximum clique problems[END_REF].

Mais ainda, a versão ponderada de CLIQUE ocorre naturalmente em um grande número de problemas reais. Nesta tese, estamos especificamente interessados em resolver o caso ponderado. Do ponto de vista algorítmico, vários procedimentos, para resolver CLIQUE PONDERADA de forma exata, já foram desenvolvidos usando técnicas de programação matemática [Nemhauser e Trotter 1975, Nemhauser e Sigismondi 1992, Rossi e Smriglio 2001, Rebennack et al. 2011, Warrier et al. 2005] ou métodos combinatórios [Carraghan e Pardalos 1990,Balas e Xue 1991[START_REF] Babel | A fast algorithm for the maximum weight clique problem[END_REF],Balas e Xue 1996, Östergård 1999[START_REF] Warren E Hicks | [END_REF], Yamaguchi e Masuda 2008, Kumlander 2008, Shimizu et al. 2012[START_REF] Held | Maximum-weight stable sets and safe lower bounds for graph coloring[END_REF].

Em programação matemática, o estudo do politopo do conjunto independente (clique em G) foi iniciado em [Padberg 1973]. Diversas desigualdades válidas e facetas são conhecidas para este polítopo. Em [Rebennack et al. 2011], encontramos uma lista de desigualdades válidas e algoritmos especializados para a separação delas.

Essas desigualdades válidas e suas rotinas de separação levam ao desenvolvimento de vários algoritmos de Branch & Cut. Todavia, o tempo exigido para realizar a rotina de separação e a resolução das relaxações lineares nem sempre justifica a melhoria dos limites superiores proporcionada pela inclusão dos cortes (exceto para grafos com densidade mais alta). Dessa maneira, a maior parte dos algoritmos de Branch & Cut são superados por algoritmos de Branch & Bound combinatórios.

O algoritmo Branch & Bound combinatório mais utilizado para CLIQUE PONDERADA é CLIQUER [ Östergård 2002]. Ele utiliza um método de busca, que mais tarde ficou conhecido como método das Bonecas Russas [START_REF] Verfaillie | Russian Doll Search for Solving Constraint Optimization Problems[END_REF]. Um uso interessante dele acontece na resolução de subproblemas de geração de colunas para um modelo de coloração de grafos [START_REF] Gualandi E Malucelli | [END_REF]. Neste caso, ele pode ser usado tanto como heurística para encontrar uma clique ponderada com peso acima de um certo valor ou como método exato para encontrar uma clique ponderada máxima. Porém, sua utilização fica comprometida devido a seu desempenho abaixo do esperado em grafos mais densos (com pelo menos 50% das arestas de um grafo completo).

O algoritmo proposto por Yamaguchi e Masuda, denominado aqui por YM [Yamaguchi e Masuda 2008], veio para sanar esse problema. Ele utiliza um procedimento de limite superior baseado no caminho mais pesado, no grafo direcionado obtido a partir de uma ordem ρ dos vértices. Testes computacionais, realizados em grafos aleatórios, comprovaram que ele é mais eficiente que CLIQUER para grafos com densidade superior a 50%. Sua superioridade cresce à medida que a densidade do grafo aumenta. Além disso, ele também é mais eficiente que o algoritmo proposto em [Kumlander 2008], denotado por DK.

O algoritmo DK é um algoritmo de Boneca Russas que incorpora um limite superior baseado no que nós chamamos de coloração ponderada particionada (Ver Capítulo 3). Yamaguchi e Masuda mostraram que seu procedimento de limite superior (caminho mais pesado) é melhor teoricamente que o utilizado por Kumlander (coloração ponderada particionada).

Em 2012, Held, Cook e Sewell [START_REF] Held | Maximum-weight stable sets and safe lower bounds for graph coloring[END_REF]] desenvolveram um algoritmo de Branch & Bound, que identificamos por HCS, adotando as ideias presentes em [Balas e Xue 1991[START_REF] Babel | A fast algorithm for the maximum weight clique problem[END_REF], Warren e Hicks 2006, Sewell 1998].

O algoritmo foi utilizado para resolver o subproblema de pricing do problema de coloração de grafos. Nesse trabalho, os autores geraram um conjunto de instâncias do problema do conjunto independente ponderado máximo, oriundas do subproblema de pricing(algumas delas ocorreram depois de centenas de iterações do algoritmo de geração de colunas). Elas são denominadas instâncias EXACTCOLOR.

O algoritmo HCS foi comparado com o algoritmo CLIQUER e outros dois algoritmos de Branch & Cut dos resolvedores GUROBI 3.0.0 e CPLEX 12.2.

A performance de HCS foi observada no conjunto de 25 instâncias difíceis de EXACTCOLOR. CLIQUER foi o mais eficiente para as instâncias com densidade inferior a 50%. Para densidade maior ou igual 97%, os algoritmos de Branch & Cut foram os mais eficientes. Porém, os dois falham nas situações contrárias, ou seja, CLIQUER falha em densidades maior ou igual 97% enquanto os algoritmos de

Branch & Cut tem um desempenho pobre em grafos esparsos. Diferentemente deles, HCS mostrou-se competitivo em instâncias de todas densidades, obtendo melhor desempenho que os concorrentes nas faixas intermediárias de densidade.

Por outro lado, o algoritmo HCS não foi comparado nem teórica e nem computacionalmente com outros algoritmos de Branch & Bound da literatura, como YM. Mesmo com vários algoritmos disponíveis na literatura, com comprovada eficiência, ainda há espaço para a proposição de outros procedimentos que possa apresentar desempenho ainda melhor. Essa demanda justifica-se pela importância do problema e sua recorrência, assim como a necessidade freqüente de resolução consecutiva de várias instâncias do mesmo, como ocorre no processo de geração de colunas para coloração de grafos [Mehrotra e Trick 1996 [START_REF] Babel | A fast algorithm for the maximum weight clique problem[END_REF][START_REF] Warren E Hicks | [END_REF], Sewell 1998] e ainda idéias mais recentes apresentadas em [Tomita et al. 2010, Segundo et al. 2010, Segundo, Rodriguez-Losada e Jiménez 2011, Corrêa et al. 2014], denominado BITCLIQUE.

Embora a maior parte dos ingredientes usados em nosso algoritmo já estejam disponíveis na literatura, a forma como combinamos foram capazes de produzir melhor desempenho computacional.

Antes da apresentação de BITCLIQUE, que usa coloração ponderada inteira como limite superior empregado na poda durante o processo enumerativo, procuramos justificar no Capítulo 3 nossa escolha por esse limite em lugar de outros já propostos na literatura. Assim, mostramos teoricamente que o limite superior baseado em uma heurística de coloração ponderada inteira é em potencial equivalente àquele produzido pelo caminho de maior peso, como utilizado em YM. Capítulo 2

Definições Básicas

Neste capítulo, revisamos os principais conceitos de grafos e apresentamos a notação utilizada ao longo do texto. Além disso, exibimos as principais formulações para o problema da clique máxima ponderada e alguns tipos de colorações ponderadas. Um limite superior para ω(G) pode ser obtido através de uma partição do conjunto de vértices em conjuntos independentes. Uma partição de um conjunto A é qualquer coleção A 1 , A 2 , . . . , A n de subconjuntos não vazios de A tal que

Grafos

∪ n i=1 A i = A e A i ∩ A j = ∅ para todo 1 ≤ i < j ≤ n. Uma k-coloração de um grafo G é uma partição do conjunto de vértices V em conjunto independentes S 1 , . . . , S k . O menor valor k para o qual existe uma k-coloração é chamado de número cromático de G denotado por χ(G). O número cromático de G é um conhecido limite superior para ω(G), ou seja, ω(G) ≤ χ(G)
Determinar χ(G) é um problema N P-difícil, porém encontrar uma coloração, que fornece um limite superior para χ(G) e, conseqüentemente para ω(G), pode ser feita por diversos procedimentos polinomiais, comumente chamados heurísticas de coloração. 

y(S) ≥ w(v) ∀v ∈ V (G). (2.1)
Em particular, se a imagem da função y é Z (Q) chamamos a coloração ponderada de inteira (respectivamente, fracionária).

O peso y(S) da coloração ponderada (S, y) é dado pelo somatório dos pesos dos conjuntos independentes, ou seja,

y(S) = S∈S y(S) (2.2)
O número cromático ponderado inteiro (fracionário), denotado por χ(G, w)

(χ f (G, w)), é o peso de uma coloração ponderada inteira (fracionário) mínima. O número cromático ponderado inteiro (fracionário) é um conhecido limite superior para ω(G, w). Mais precisamente, temos

ω(G, w) ≤ χ f (G, w) ≤ χ(G, w) (2.3)

Grafos Direcionados

Um grafo direcionado -→ G é um par ordenado (V, A), composto por um conjunto finito V , cujos elementos são denominados vértices, e por um conjunto A ⊆ {(u, v) : grafo direcionado acíclico induzido por ρ, denotado -→ G ρ , é obtido trocando cada aresta {ρ i , ρ j } ∈ E(i < j) em G por um arco de ρ i para ρ j . Logo,

u, v ∈ V, u = v},
A = {(ρ i , ρ j ) : {ρ i , ρ j } ∈ E, i < j}
A Figura 2.3 ilustra a obtenção do grafo direcionado acíclico induzido por uma sequência de vértices ρ.

1 3 2 3 6 1 3 2 5 2 4 2 1 3 2 3 6 1 3 2 5 2 4 2
Figura 2.3: O grafo da esquerda é um grafo ponderado utilizado para obter o grafo direcionado acíclico induzido pela seqüencia (1,2,3,4,5,6) (grafo da direita).

Dado um grafo direcionado acíclico

- → G e uma vértice v ∈ V , o peso do caminho com peso máximo terminado em v é denotado por ( - → G , v). O peso do caminho com peso máximo de - → G ,denotado ( - → G ), e portanto max v∈V ( - → G , v).
Em [Yamaguchi e Masuda 2008], o seguinte teorema é apresentado, relacionando o caminho com peso máximo em -→ G ρ , dada uma sequência ρ dos vértices, e o peso da clique ponderada máxima em G .

Teorema 1 [Yamaguchi e Masuda 2008] Para um grafo ponderado G = (V, A, w)

e uma seqüencia ρ, ω(G, w) ≤ ( - → G ρ ) Prova Seja K uma clique máxima em G. Para qualquer sequência ρ, - → G ρ tem um caminho que contém todos os vértices em K. Logo, ω(G) = w(K) ≤ ( - → G ρ ).
Dado um grafo ponderado e uma sequência ρ dos vértices, o Algoritmo 2.1 calcula

(v, - → G ρ ) para todo vértice v.
Algoritmo 2.1 O algoritmo CaminhoMaisPesado recebe um grafo G e uma seqüencia ρ, e devolve o caminho mais pesado no grafo

- → G ρ terminando em cada vértice função CaminhoMaisPesado(G, w, ρ, ) Para v ∈ V faça (v) ← w(v) Para i ← 1 até n faça Para j ← i + 1 até n faça Se (ρ i , ρ j ) ∈ E( - → G ρ ) então (ρ j ) ← max{ (ρ j ), (ρ i ) + w(ρ j )}

Formulações

A formulação mais simples para o problema da clique máxima ponderada é a formulação por aresta. Nesta formulação, uma variável x i ∈ {0, 1} é associada a cada vértice i. Se

x i = 1 então o vértice i está na clique; caso contrário, o vértice i não está. maximize n i=1 w i x i (2.4) s.a. x i + x j ≤ 1, ∀{i, j} ∈ E (2.5) x i ∈ {0, 1} i ∈ V (2.6)
A restrição (2.5) garante que no máximo um vértice pode ser escolhido em cada não aresta. A restrição (2.6) garante que todas as variáveis são binárias.

Um estudo desta formulação foi conduzido por Nemhauser e Trotter [Nemhauser e Trotter 1975].Eles mostraram que, se x = (x 1 , x 2 , . . . , x n ) é um ponto extremo da região viável da relaxação linear de (2.4), (2.5) e (2.6), então cada x i ∈ {0, 1, 1 2 }. Além disso, se uma variável x i = 1 na solução ótima da relaxação linear da formulação, então x i = 1 em pelo menos uma solução ótima da formulação inteira.

Note que esta propriedade pode ser aproveitada em um algoritmo enumerativo.

Contudo, na maior parte dos casos, poucas variáveis assumem um valor 1 na solução ótima da relaxação linear, e a diferença entre o valor ótimo do problema inteiro e de sua relaxação linear é bastante grande. Isso representa uma séria restrição da utilização dessa formulação em um algoritmo de Branch & Bound.

Uma formulação alternativa considera uma restrição para cada conjunto independente maximal de G. A variável x i é definida como anteriormente.

maximize n i=1 w i x i (2.7) subject to {S:i∈S} x i ≤ 1, ∀S ∈ S (2.8) x i ∈ {0, 1} i ∈ V (2.9)
onde S é o conjunto de todos os conjuntos independentes maximais de G.

A restrição (2.8) garante que podemos escolher no máximo um vértice em cada conjunto independente de G. 

y S ≥ 0 S ∈ S (2.12)
onde y S é o peso do conjunto independente S.

Note que as desigualdades do problema dual são exatamente aquelas que definem uma coloração ponderada. Logo, este problema determina uma coloração ponderada mínima, que fornece um limite superior para ω(G, w). Na verdade, a coloração ponderada do grafo G também gera limites superiores para as cliques ponderadas de cada subgrafo, como segue:

Proposição 1 Seja (S, y) uma coloração ponderada para um grafo ponderado

(G, w). Dado V ⊆ V . Seja S[V ] = {S ∈ S : S ∩ V = ∅}. Então, y(S[V ]) ≥ ω(G[V ], w|V )
onde w|V é a função w restrita ao conjunto V . Esse limite superior pode ser obtido através de heurísticas de coloração ponderada. Na próxima seção, apresentaremos alguns tipos de colorações ponderada. Coloração Ponderada Inteira.

Colorações Ponderadas

Coloração Ponderada Trivial

Uma coloração ponderada trivial de G é uma coleção de conjuntos independentes S = {S 1 , . . . , S k } com uma função de peso y : S → Z + tal que a cardinalidade de cada conjunto independente é 1 e o seu peso é igual ao peso do vértice que o define.

A Figura 2.4 ilustra uma coloração ponderada trivial.

Uma coloração ponderada trivial pode ser obtida através do seguinte algoritmo:

Algoritmo 2.2 Heurística de Coloração Ponderada Trivial função ColoraçãoTrivial(G, w, ρ) i ← 1 U ← V Enquanto U = ∅ faça Seja v o primeiro vértice em U seguindo a ordem ρ S i ← {v} y(S i ) ← w(v) U ← U \ {v} i ← i + 1 Retorne i-1 k=1 y(S i )
Observe que o peso da coloração ponderada trivial obtida pela heurística não depende da ordem em que os vértices são escolhidos durante a sua execução.

O custo computacional para obter essa coloração pode ser considerado insignificante, porém a qualidade do limite superior é baixa. Apesar disso, essa coloração foi utilizada nos algoritmos Branch & Bound para CLIQUE PONDERADA proposto em [Carraghan e Pardalos 1990, Östergård 1999] obtendo bons resultados em grafos esparsos.

Coloração Ponderada Particionada

Uma coloração ponderada particionada de G é composta por uma partição S = {S 1 , . . . , S k } dos vértice V e uma função de peso y : S → Z + . O peso de cada conjunto independente é dado pelo maior peso dos vértices que ele contém.

A Figura 2.5 ilustra uma coloração ponderada particionada obtida seguindo a ordem (6,5,4,3,2,1).

1 3 2 3 3 2 4 2 5 2 6 1 S y 6,2 3 5,3 2 4,1 3 
Figura 2.5: A coloração ponderada particionada de G mostrada na figura tem peso 8 e a clique máxima ponderada de G é 6.

Uma coloração ponderada particionada pode ser obtida através do seguinte algoritmo: Em [Fang et al. 2014], uma coloração ponderada particionada é utilizada para codificar o problema da clique máxima ponderada em um problema de satisfabilidade máxima (MaxSat) ponderada. Técnicas de resolvedores de MaxSat são utilizadas para encontrar um limite superior mais apertado.

Algoritmo 2.3 Heurística de Coloração Ponderada Particionada função ColoraçãoParticionada(G, w, ρ) i ← 1 U ← V Enquanto U = ∅ faça Encontre um conjunto independente maximal S i em G[U ] seguindo a ordem ρ. y(S i ) ← max v∈S i w(v) U ← U \ {S i } i ← i + 1 [Avenali
Em geral, os algoritmos que utilizam esse tipo de coloração ponderada conseguem obter bons resultados para grafos mais densos.

Coloração Ponderada Inteira

Uma coloração ponderada inteira de G é um conjunto de conjuntos independentes S = {S 1 , . . . , S k } juntamente com seus pesos inteiros positivos tais que

S∈S:v∈S y S = w(v), para todo v ∈ V (G)
. O peso da coloração ponderada inteira é dado pela soma dos pesos dos conjuntos independentes.

Uma coloração ponderada inteira pode ser obtida pelo seguinte processo iterativo:

Para cada vértice v, uma variável res(v) representa o peso residual de v, ou seja, a diferença entre w(v) e soma dos conjuntos independentes que contém v escolhido até agora(Veja equação (2.13)). Assim, O peso residual de um vértice v é inicializado com o valor de w(v).

res(v) = w(v) - S:v∈S y(S) (2.13)
Em cada iteração, encontra-se uma conjunto independente maximal S usando vértices ainda não totalmente coloridos, ou seja, com o peso residual maior que zero. O peso do conjunto independente S será dado pelo menor peso residual de seus vértices. O peso residual de S é, então, decrementado do peso de S. O processo de coloração continua enquanto existirem vértices com peso residual maior que de zero. Os passos anteriores podem ser vistos no Algoritmo 2.4:

Algoritmo 2.4 Heurística de Coloração Ponderada Inteira função ColoraçãoInteira(G, w, ρ) Para v ∈ V faça res(v) ← w(v) i ← 0 U ← V Enquanto U = ∅ faça i ← i + 1 Seja u o primeiro vértice de U seguindo ρ Encontre um conjunto independente maximal S i em G[U ] contendo o vértice u seguindo a ordem π y(S i ) ← min{res(v)|v ∈ S i } Para v ∈ S i faça res(v) ← res(v) -y(S i ) Se res(v) = 0 então U ← U \ {v}
A heurística de coloração ponderada inteira é utilizada como limite superior nos seguintes algoritmos [Balas e Xue 1991], [START_REF] Babel | A fast algorithm for the maximum weight clique problem[END_REF]], [Balas e Xue 1996], [START_REF] Warren E Hicks | [END_REF], [START_REF] Held | Maximum-weight stable sets and safe lower bounds for graph coloring[END_REF] e [Tavares et al. 2015].

A Figura 2.6 ilustra uma coloração ponderada inteira. Figura 2.6: O peso da coloração ponderada inteira de G é 8. A clique máxima ponderada para G é 6.

Importância da ordem inicial

Neste momento, espera-se que o leitor entenda que o peso da coloração ponderada inteira é bastante influenciado pela ordem dos vértices ρ utilizada. Ela determina que conjuntos independentes são gerados. Conseqüentemente, a escolha da ordem inicial ρ afeta o desempenho do algoritmo que usa a coloração ponderada para definir o procedimento de poda. Mais recentemente, em [Tomita et al. 2010], os autores reportaram resultados melhores que os anteriores com a adoção de uma ordem fixa dos vértices para a heurística de coloração para CLIQUE. Em [Segundo et al. 2010],

esse resultado é ainda mais potencializado pela utilização dos vetores de bits para CLIQUE.

Uma segunda ordem que merece destaque é aquela em que os vértices são completamente coloridos, que chamamos de ordem de coloração, denotada por π.

Se S 1 , . . . , S k é a seqüencia de conjuntos independentes gerados, a ordem π é tal que 

π(u) < π(v) sempre que max{k|u ∈ S k } < max{k|v ∈ S k };
y(S) = v∈P w(v) ≤ ( - → G ρ ). (3.1)
Os exemplos 1 e 2 ilustram o lema 1.

Exemplo 1 Considere o seguinte DAG obtido pela seqüência ρ = (1, 2, 3, 4, 5, 6): , 2, 3, 4, 5, 6) O Algoritmo 2.4 devolve a seguinte coloração ponderada inteira (S, y), onde y(S) = 7: ,2,3,4,5,6) e seu peso é 13. Logo,

1 3 2 3 6 1 3 2 5 2 4 2 Figura 3.1: Grafo ponderado direcionado - → G ρ , onde ρ = (1
S 1 = {1, 3},y(S 1 ) = 2 S 2 = {1, 4},y(S 2 ) = 1 S 3 = {2, 4},y(S 3 ) = 1 S 4 = {2,
7 = y(S) ≤ v∈P w(v) = 7 ≤ ( - → G ρ ) = 13
Exemplo 2 Considere o seguinte DAG obtido pela sequência ρ = (6, 2, 5, 3, 4, 1):

1 3 2 3 6 1 3 2 5 2 4 2 Figura 3.2: Grafo ponderado direcionado - → G ρ , onde ρ = (6, 2, 5, 3, 4, 1)
O algoritmo 2.4 devolve a seguinte coloração ponderada inteira (S, y), onde y(S) = 7: 

S 1 = {6, 2},y(S 1 ) = 1 S 2 = {2, 5},y(S 2 ) = 2 S 3 = {3, 1},y(S 3 ) = 2 S 4 = {4, 1},y(S 4 ) = 1 S 5 = {4},
7 = y(S) ≤ v∈P w(v) = 7 = ( - → G ρ )
No lema seguinte, mostramos que dada uma coloração ponderada inteira (S, y), podemos encontrar uma ordem dos vértices ρ tal que o peso máximo de um caminho direcionado em -→ G ρ seja menor que o peso da coloração ponderada inteira (S, y).

Lema 2 Seja (G, w) um grafo ponderado. Dada uma coloração ponderada inteira (S, y) de (G, w), existe uma sequência dos vértices ρ tal que

( - → G ρ ) ≤ y(S) (3.2)
Prova Como i S i = V , podemos construir uma partição do conjunto dos vértices {S 1 , S 2 , . . . , S k } tal que Por outro lado, na coloração ponderada inteira temos que

S 1 = S 1 S i+1 = S i+1 \ ∪ i l=1 S l , para i ≥ 1 (3.3) Defina ρ seguindo S 1 ,
i:v∈S i y(S i ) = w(v) Logo, ( - → G ρ ) = v∈P w(v) ≤ i y(S i )
Os exemplos 3 e 4 ilustram o lema 2.

Exemplo 3 Considere o seguinte grafo ponderado:

1 3 2 3 6 1 3 2 5 2 4 2
Considere a seguinte coloração ponderada inteira (S, y), onde y(S) = 7:

S 1 = {1, 3},y(S 1 ) = 2 S 2 = {1, 4},y(S 2 ) = 1 S 3 = {2, 4},y(S 3 ) = 1 S 4 = {2, 5},y(S 4 ) = 2 S 5 = {6},y(S 5 ) = 1
Defina a seguinte partição de V:

S 1 = {1, 3} S 2 = {4} S 3 = {2} S 4 = {5} S 5 = {6}
A partir da partição, podemos definir a seguinte seqüência ρ = (1,3,4,2,5,6). O grafo direcionado induzido por ρ é: , 3, 4, 2, 5, 6) O caminho mais pesado no grafo direcionado induzido por ρ é (3,4,5,6), cujo peso é 7.

1 3 2 3 6 1 3 2 5 2 4 2 Figura 3.3: Grafo ponderado direcionado - → G ρ , onde ρ = (1
Exemplo 4 Considere o grafo ponderado do exemplo 3. Considere a seguinte coloração ponderada inteira (S, y):

S 1 = {6, 2},y(S 1 ) = 1 S 2 = {2, 5},y(S 2 ) = 2 S 3 = {3, 1},y(S 3 ) = 2 S 4 = {4, 1},y(S 4 ) = 1 S 5 = {4},y(S 5 ) = 1
Defina a seguinte partição de V:

S 1 = {2, 6} S 2 = {5} S 3 = {1, 3} S 4 = {4} S 5 = {}
A partir da partição, podemos definir a seguinte sequencia ρ = (2, 6, 5, 1, 3, 4). O grafo direcionado induzido por ρ é: , 6, 5, 1, 3, 4) O caminho mais pesado no grafo direcionado induzido por ρ é (2,3,4), cujo peso é 7.

1 3 2 3 6 1 3 2 5 2 4 2 Figura 3.4: Grafo ponderado direcionado - → G ρ , onde ρ = (2

Heurística de Yamaguchi e Masuda

Em Para v ∈ V faça 3:

(v) ← w(v) 4: S ← V 5: i ← 1 6:
Enquanto S = ∅ faça 7:

Encontre o vértice v de S com o menor valor de ().

8:

S ← S \ {v} 9:

π(i) ← v 10: Para u ∈ N (v) ∩ S faça 11: Se (v) + w(u) > (u) então 12:
(u) ← (v) + w(u)

13: i ← i + 1
Exemplo 5 Considere o seguinte grafo. Os seguintes passos são realizados pelo Algoritmo 3.1. (3) = 3 (4) = 3 (5) = 3

(3,3,3,3,3,1) vértice 5

(1) = 6 (4) = 5

(6,3,3,5,3,1) vértice 2

(3) = 5 (6,3,5,5,3,1) vértice 3 (4) = 7

(6,3,5,7,3,1) vértice 1 (6,3,5,7,3,1) vértice 4

A ordem devolvida pelo algoritmo é [6,5,2,3,1,4] 

Para v ∈ V faça 3: res(v) ← w(v) 4: i ← 1 5: tamanho ← 1 6: U ← V 7: U B ← 0 8: Enquanto U = ∅ faça 9:
Encontre um conjunto independente maximal S i em U seguindo a ordem crescente dos pesos residuais. 10:

y(S i ) ← min{res(v) : v ∈ S i } 11: U B ← U B + y(S i ) 12:
Para u ∈ S i faça 13: res(v) ← res(v) -y(S i )

14:

Se res(v) = 0 então 15:

U ← U \ {v} 16: π[tamanho] = v. 17: color[v] ← U B 18: tamanho ← tamanho + 1 19: i ← i + 1
Exemplo 6 A execução da coloração ponderada inteira proposta em [START_REF] Held | Maximum-weight stable sets and safe lower bounds for graph coloring[END_REF]] aplicada ao grafo da Figura 3.5 está descrita na Tabela 6. A ordem de coloração devolvida pela heurística é [6,5,3,4,2,1]. O peso da coloração ponderada é 8. Note que, diferentemente das heurísticas apresentadas no Capítulo 2, onde uma ordem inicial é dada como entrada, na Heurística de Held, Cook e Sewell, a ordem usada para selecionar os vértices é determinada durante o processo, escolhendo o vértice com o menor peso residual.

Peso Residual

Ordem dos vértices seguindo o peso residual

Lista dos Conjuntos Independentes

(3,3,2,2,2,1) 6,5,4,2,3,1

S 1 = {6, 2}, y(S 1 ) = 1 (3,2,2,2,2,0) 5,4,3,2,1 S 1 = {6, 2}, y(S 1 ) = 1 S 2 = {5, 3}, y(S 2 ) = 2
(3,2,0,2,0,0) 4,2,1

S 1 = {6, 2}, y(S 1 ) = 1 S 2 = {5, 3}, y(S 2 ) = 2 S 3 = {4, 2}, y(S 3 ) = 2
(3,0,0,0,0,0) 1

S 1 = {6, 2}, y(S 1 ) = 1 S 2 = {5, 3}, y(S 2 ) = 2 S 3 = {4, 2}, y(S 3 ) = 2 S 4 = {1}, y(S 4 ) = 3
Tabela 3.1: Execução do Algoritmo 3.2.

A partir da Proposição 1, temos que:

Proposição 3 [START_REF] Held | Maximum-weight stable sets and safe lower bounds for graph coloring[END_REF] Sejam π e color devolvidos pelo Algoritmo 3.2. Para todo i = 1, . . . , n, .

ω(G[π 1 , . . . , π i ], w) ≤ color(π i )

Heurística BITCOLOR

Uma heurística de coloração ponderada inteira com paralelismo de bits foi apresentada em [Tavares et al. 2015]. Em cada iteração, um conjunto independente maximal é obtido seguindo uma ordem inicial pré-estabelecida dos vértices ρ. A ordem ρ é utilizada para organizar os bits nos vetores de bits utilizados e é passada implicitamente juntamente com os vetores de bits. O peso do conjunto independente S é igual ao menor peso residual dos vértices de S. O peso residual dos vértices de A heurística de coloração ponderada inteira proposta em [Tavares et al. 2015] está definida no Algoritmo 3.3:

Um passo importante neste Algoritmo é a sequência que é seguida para determinar a escolha dos vértices a entrarem no conjunto independente S i , realizada Algoritmo 3.3 Heurística Coloração Ponderada Inteira [Tavares et al. 2015] 1: função Bitcolor(V , ρ, π, color, tamanho)

2: Para v ∈ V faça 3: res(v) ← w(v) 4: i ← 1 5: tamanho ← 1 6: U ← V 7: U B ← 0 8: Enquanto U = ∅ faça 9:
Encontre um conjunto independente maximal S i em G[U ] selecionando vértices seguindo a ordem ρ. Se res(v) = 0 então 16:

U ← U \ {v} 17: Π[tamanho] = v 18: color[v] ← U B 19: tamanho ← tamanho + 1 20: i ← i + 1
na Linha 9. Para o caso não ponderado, as duas estratégias de ordenação iniciais mais utilizadas em algoritmos de coloração seqüencial são:

Maior grau primeiro (largest-first ordering) [Welsh e Powell 1967]. Uma ordem

(v 1 , . . . , v n ) dos vértices de G é dita maior grau primeiro se d(v 1 ) ≥ d(v 2 ) ≥ . . . ≥ d(v 1 ).
Menor grau último (smallest-last ordering) [Matula e Beck 1983]. Uma ordem

(v 1 , . . . , v n ) dos vértices de G é dita menor grau último se v i é o vértice com o menor grau no grafo G[V \ {v i+1 , . . . , v n }], para todo i ∈ {1, . . . , n}.
No caso ponderado, consideramos duas possíveis estratégias de ordenação inicial dos vértices:

A ordem de menor peso primeiro dos vértices de G é uma ordem (v 1 , . . . , v n ) tal que v i é o vértice com o menor peso em G[V \ {v 1 , . . . , v i-1 }]. Em caso de empate, o vértice v i é o vértice com a maior soma dos pesos dos adjacentes em G[V \ {v 1 , . . . , v i-1 }]. A ordenação inicial dos vértices baseada na ordem crescente dos pesos é utilizada em [Carraghan e Pardalos 1990] e com um critério de desempate em [ Östergård 1999]. Em [Tavares et al. 2015 Os resultados computacionais das diferentes estratégias de ordenação inicial dos vértices serão apresentados na seção seguinte. 

Testes Computacionais

G[{v n } ∪ N (v n )] G[{v n-1 } ∪ (N (v n-1 ) \ {v n }] G[{v n-2 } ∪ (N (v n-2 ) \ {v n-1 , v n })] . . . G[{v 1 } ∪ (N (v 1 ) \ {v 2 , . . . , v n-1 , v n })]
A Figura 3.10 ilustra o esquema de ramificação de Balas e Yu. Dessa maneira, a estratégia de ramificação fica responsável por definir uma ordem dos vértices em V , que será utilizada para gerar os subgrafos a serem analisados.

Figura 3.10: Esquema de ramificação de Balas-Yu

A corretude do esquema de ramificação está garantida pelo seguinte teorema:

Teorema 2 [Balas e Xue 1991] Seja K 0 uma clique máxima de G[U ] ou um limite superior para ela e seja (v 1 , . . . , v n ) uma ordem arbitrária dos vértices de

V \ U . Se G tem uma clique K 1 tal que w(K 1 ) > w(K 0 )m então K 1 está contida em uns dos seguintes m conjuntos V i = {v i } ∪ (N (v i ) \ {v i , . . . , v n }), i = m, . . . , 1 
Facilmente, podemos modificar o procedimento de limite superior para encontrar

um subgrafo G[U ] tal que ω(G[U ], w) ≤ LB, onde LB é um limite inferior conhecido para o problema.
Em [Yamaguchi e Masuda 2008], o conjunto de ramificação é definido pelos vértices v tal que o maior caminho no grafo direcionado até v seja maior que um limite inferior conhecido LB, ou seja:

V = {v : (v) > LB} (3.5)
Em [START_REF] Held | Maximum-weight stable sets and safe lower bounds for graph coloring[END_REF] ii. Procedimento de limite superior.

iii. Estratégia de ramificação. iv. Estrutura de dados para representação do grafo. Em [Balas e Xue 1996], o limite inferior é calculado no nó raiz, a partir de um subgrafo cordal maximal. Nos outros nós, uma heurística gulosa é utilizada.

Em [START_REF] Babel | A fast algorithm for the maximum weight clique problem[END_REF]], uma heurística de coloração ponderada, inspirada no DSATUR [Brélaz 1979], é responsável por gerar um limite superior, e também um limite inferior em cada subproblema.

Em [START_REF] Warren E Hicks | [END_REF], um limite inferior é obtido a partir de uma heurística gulosa do tipo best-in.

Em [Held, O segundo ponto chave w(C) + U B(P ) ≤ LB está relacionado com a poda de nós, ou seja, a enumeração implícita de cliques com o peso menor que o limite inferior corrente. Esta poda depende fortemente do procedimento de limite superior utilizado. A maior parte dos algoritmos utiliza heurísticas de coloração ponderada para obter limites superiores para a clique ponderada máxima em cada subproblema.

Em [Balas e Xue 1991], utiliza-se uma heurística de coloração ponderada inteira, onde uma família de conjuntos independentes é construída iterativamente seguindo a ordem decrescente dos pesos.

Em [START_REF] Babel | A fast algorithm for the maximum weight clique problem[END_REF]], o limite superior é dado por uma heurística de coloração ponderada inteira, baseada no DSATUR, que fornece também um limite inferior.

Em [Balas e Xue 1996], uma heurística de coloração fracionária, que potencialmente gera um limite superior melhor, é incorporada ao algoritmo de

Branch & Bound.
Em [START_REF] Warren E Hicks | [END_REF], uma versão otimizada da heurística de coloração ponderada proposta por Babel [START_REF] Babel | A fast algorithm for the maximum weight clique problem[END_REF]] é utilizada nos níveis iniciais da árvore de busca. Nos outros níveis, usa-se uma variação da heurística de coloração ponderada inteira de [Balas e Xue 1991].

Em [Kumlander 2008], uma heurística de coloração ponderada particionada é aplicada no nó raiz. A coloração obtida é reaproveitada em todos os nós da árvore para tentar reduzir o custo computacional do processo. Em [Carraghan e Pardalos 1990], os vértices de P em cada subproblema, são ramificados em ordem decrescente de pesos. De maneira geral, essa estratégia de ramificação reduz a quantidade de vértices que precisam ser ramificados. Nesse algoritmo, o conjunto de ramificação é definido durante o processo de ramificação.

Em [START_REF] Babel | A fast algorithm for the maximum weight clique problem[END_REF]], uma ordem total dos vértices de P é definida (π 1 , π 2 , . . . , π p ) Em [Yamaguchi e Masuda 2008], uma ordem total para os vértices de P

tal que color[π 1 ] ≤ color[π 2 ] ≤ color[π 3 ] ≤ . . . ≤ color[π p ], onde color[π i ] representa o peso da coloração ponderada de G[π 1 , π 2 , . . . , π i-1 , π i ].
é definida [v 1 , v 2 , . . . , v p ], tal que (v 1 ) ≤ (v 2 ) ≤ (v 3 ) ≤ . . . ≤ (v p ), onde (v i ) representa o tamanho do maior caminho no subgrafo - → G π [v 1 , v 2 , . . . , v i-1 , v i ].
Os vértices são ramificados em ordem decrescente do tamanho do maior caminho no grafo -→ G π enquanto for possível superar a melhor clique conhecida.

Em [START_REF] Held | Maximum-weight stable sets and safe lower bounds for graph coloring[END_REF], três regras são utilizados para definir três conjuntos de ramificações. O algoritmo efetivamente utiliza aquela de menor cardinalidade com um critério de desempate. Os vértices do menor conjunto de ramificação são ramificados em ordem crescente de grau.

Em [Tavares et al. 2015], uma ordem total dos vértices [π 1 , π 2 , . . . , π p ] de P é O algoritmo usa duas regras de poda e três estratégias de ramificação.

definida tal que color[π 1 ] ≤ color[π 2 ] ≤ color[π 3 ] ≤ . . . ≤ color[π p ], onde color[π i ] representa o peso da coloração ponderada de G[π 1 , π 2 , . . . , π i-1 , π i ].
← 0 Y M (∅, V, LB) função YM(C, P, LB) Se w(C) > LB então LB ← w(C) CaminhoM aisP esado(G[P ], w, π, ) Para i ← |P | até 1 faça v ← π(i) Se w(C) + (v) ≤ LB então retorne Y M (C ∪ {v}, P ∩ N (v), LB) P ← P \ {v}
A primeira regra de poda utiliza o conjunto X e pode ser estabelecida da seguinte maneira: Se existe um vértice x ∈ X tal que

w(x) ≥ w((C ∪ P ) ∩ N (x))
então o subproblema atual não deriva uma clique ponderada que supere LB e pode ser podado.

Lema 3 Dado um subproblema (C, P, X, LB), se existe um x ∈ X tal que w(x) ≥ w((C ∪ P ) ∩ N (x)) então toda clique C ⊆ (C ∪ P ) tem w(C ) ≤ LB. Prova Considere uma clique C ⊆ (C ∪ P ). Então, C = {x} ∪ (C \ N (x)) é uma clique contendo x ∈ X, de modo que w(C ) ≤ LB.
Logo, as seguintes relações são válidas:

w(C ) = w({x} ∪ C \ N (x)) = w(x) + w(C \ N (x)) = w(x) + w(C ) -w(C ∩ N (x)), como C ⊆ C ∪ P e ∀v w(v) ≥ 0 ≥ w(x) + w(C ) -w((C ∪ P ) ∩ N (x)), como w(x) -w((C ∪ P ) ∩ N (x)) ≥ 0 ≥ w(C ) Logo, w(C ) ≤ w(C ) ≤ LB.
A segunda regra de poda usa uma coloração ponderada inteira. Dado um subproblema (C, P, X, LB), se o peso da coloração ponderada de P for inferior ou igual a LB -w(C), então este subproblema não pode gerar uma clique ponderada com peso superior a LB. Logo, todas as suas cliques estão implicitamente enumeradas.

A primeira regra de ramificação é uma extensão, para o caso ponderado, LB ← 0 3:

w(C ) = w({v} ∪ (C \ N (v)) = w(v) + w(C \ N (v)) = w(v) + w(C ) -w(C ∩ N (v)), como C ⊆ P ≥ w(v) + w(C ) -w(P ∩ N (v)), como w(v) -w(F ∩ N (v)) ≥ 0 ≥ w(C ) Portanto,
Para i ← 1 até 3 faça 4: C ← HeurísticaGulosa(G, i) 5: C ← BuscaLocal(G, S) 6:
Se w(C ) > LB então Escolha o menor conjunto de ramificação F = {f 1 , f 2 , . . . , f p } ⊂ P usando as três regras de ramificação 

(P i ← (P ∩ N (f i )) \ {f i+1 , . . . , f p } 22: HCS(C ∪ {f i }, P i , X) 23: X ← X ∪ {f i }

Algoritmo BITCLIQUE

Nesta seção, apresentamos o nosso algoritmo de Branch & Bound, que chamaremos de BITCLIQUE. Ele combina de forma efetiva vários elementos que já foram utilizados em outros algoritmos de Branch & Bound. Mais precisamente, usamos:

Uma metaheurística para a obtenção de um limite inferior inicial.

Uma ordenação inicial fixa dos vértices. Essa ordenação inicial dos vértices cumpre dois papeis importantes: evitar a reordenação dos vértices toda vez que a heurística de coloração ponderada for executada e prover um critério simples para a escolha dos vértices durante a coloração.

Uma heurística de coloração ponderada inteira, utilizando vetores de bits. Os vetores de bits são utilizados aqui para acelerar as operações realizadas pela Uma Estratégia de ramificação inspirada em [START_REF] Babel | A fast algorithm for the maximum weight clique problem[END_REF], Tomita et al. 2010] com base na coloração ponderada obtida.

Nas próximas seções, detalhamos melhor nossas escolhas e implementações para cada um dos quatro pontos chaves apontados acima. Além das restrições impostas pela busca tabu, a metaheurística implementa uma estratégia de reinicialização aleatória. 

Iter ← 0 C * ← ∅ Enquanto Iter < Iter max faça C ← CliqueMaximalAleatória() Inicialize lista tabu N I ← 0 C local = C Enquanto N I < L faça Construa a vizinhança N 1 , N 2 e N 3 de C Escolha o melhor vizinho permitido C ∈ N 1 ∪ N 2 ∪ N 3 C ← C N I ← N I + 1 Iter ← Iter + 1 Atualize a lista tabu Se W (C) > W (C local ) então N I ← 0 C local ← C Se W (C local ) > W (C * ) então C * ← C local Retorne C * 4.
, ou seja, Q ← Q \ N (v); Q ← Q \ {v}. O processo continua enquanto ainda existir um vértice v ∈ Q. Quando Q torna-se
vazio, um conjunto independente maximal S i é obtido. O peso do conjunto independente S i é dado pelo menor peso residual dos vértices de S i . O peso residual de cada vértice v de S i é atualizado, decrementando-o do peso da classe de cor S i .Os vértices com peso residual iguais a zero podem ser removidos de U . A heurística de coloração ponderada termina quando U torna-se vazio. As instruções em caixas são aquelas substituídas por instruções específicas que manipulam diretamente o vetores de bits.

Vetores de bits

Vetores de bits são uma estrutura de dados discreta, apropriada para modelar uma sequência de bits que pode ser manipuladas eficientemente por computadores, utilizando poucas instrução. Particularmente, vetores de bits podem ser utilizados para armazenar a matriz de adjacência de um grafo ou um subconjunto de um conjunto ordenado. Por exemplo, em um grafo com 6 vértices {v 1 , . . . , v 6 }, uma clique formada pelos vértices v 1 , v 3 , v 5 , v 6 pode ser representada pelo vetor de bits {101011}, onde cada bit está associado a um vértice do grafo e cada bit igual a 1 indica um vértice que está na clique.

O paralelismo de bits é uma forma de paralelismo alcançada quando representamos os dados em vetores de bits de tamanho w, onde w é o tamanho da palavra do computador (por exemplo, 32 ou 64 bits). Operações específicas podem ser utilizadas para processar um vetor de bits de tamanho w em uma única instrução do processador. Paralelismo de bits tem sido utilizado com bastante sucesso em muitos algoritmos, particularmente para casamento de cadeia de caracteres Algoritmo 4.5 Heurística de Coloração Ponderada função BITCOLOR(U, ρ, π, color, tamanho) Neste trabalho, o paralelismo de bits foi usado na heurística de coloração ponderada sequencial e na atualização do conjunto de vértices candidatos. Além disso, o uso de vetores de bits diminui os requisitos de memória para a representação de matriz da adjacência e dos subconjuntos de vértices manipulados durante o algoritmo.

∀v ∈ V, res(v) ← w(v) i ← 1 tamanho ← 1 U B ← 0 Enquanto U = ∅ faça S i ← ∅ ; Q ← U Enquanto Q = ∅ faça v ← Selecione o primeiro elemento de Q seguindo a ordem ρ. Q ← Q \ N (v) ; Q ← Q \ {v} ; S i ← S i ∪ {v} min res ← min{res(v)|v ∈ S i } y(S i ) ← min res U B ← U B + y(S i ) Para v ∈ S i faça res(v) ← res(v) -y(S i ) Se res(v) = 0 então U ← U \ {v} π[tamanho] ← v color[v] ← U B tamanho ← tamanho + 1 i ← i + 1 [Baeza-

Estratégia de Ramificação

Dado um subproblema (C, P, LB), a heurística de coloração ponderada devolve uma ordem total dos vértices π 1 , π 2 , . . . , π n tal que color

[π 1 ] ≤ color[π 2 ] ≤ . . . ≤ color[π n ], onde color[π i ] é um limite superior para ω(G[π 1 , . . . , π i ], w). O vértice π i é escolhido para ser ramificado enquanto w(C) + color[π i ] > LB, para todo i = n, . . . , 1.
Considere o seguinte exemplo:

1 3 2 3 3 2 4 2 5 2 6 1
Seja (6, 5, 4, 3, 2, 1) a ordem inicial dos vértices. A coloração ponderada obtida pela heurística de coloração será:

i. S 1 = {6, 2}, y(S 1 ) = 1 ii. S 2 = {5, 3}, y(S 2 ) = 2 iii. S 3 = {4, 2}, y(S 3 ) = 2 iv. S 4 = {1}, y(S 4 ) = 3
Na próxima tabela, veremos a ordem π devolvida pela heurística de coloração e o valor de color: π 6 5 3 4 2 1 color 1 3 3 5 5 

Para i ← cont até 1 faça v ← ordem[i] Se w(C) + color[v] ≤ LB então retorne newP ← P ∩ N (v) P ← P \ {v} ; BITCLIQUE(C ∪ {v}, newP , LB)

Resultados Computacionais

χ(G) = min S∈S x S (4.3)
s.a.

{S∈S:v∈S}

x S ≤ 1 ∀v ∈ V (4.4)

x S ∈ {0, 1} ∀S ∈ S (4.5)
Em [Mehrotra e Trick 1996], este problema é resolvido por um algoritmo de Branch & Price. O problema relaxado resolvido em cada nó da árvore é:

χ f (G, S ) = min S∈S x S (4.6)
s.a.

{S∈S :v∈S}

x S ≤ 1 ∀v ∈ V (4.7)

x S ≥ 0 ∀S ∈ S (4.8) onde S ⊆ S. χ f (G) = χ f (G, S) é o número cromático fracionário de G.
Seja (x, π) uma solução primal-dual ótima para (4.6)-(4.8), onde o vetor dual A estrutura geral do método de Busca das Bonecas Russas pode ser separada em duas partes:

π = (π v ) v∈V ∈ [0, 1] |V | .
Estratégia de enumeração das bonecas.

Estratégia de solução das bonecas.

Para o problema da clique (ponderada) máxima [ Östergård 1999, Östergård 2002] , Östergård propõe a seguinte implementação dessas estratégias. A enumeração das bonecas baseia-se em uma ordem inicial dos vértices. Uma boneca corresponde ao problema da clique ponderada máxima no subgrafo que inclui um vértice a mais seguindo essa ordem. Cada boneca é resolvida por um algoritmo de Branch & Bound, fortalecido por uma estratégia de poda obtida pela relação entre os subproblemas.

Em [Trukhanov et al. 2013 O processo de enumeração de bonecas é alterado para que um número significativo de bonecas deixem de ser resolvidas devido à adoção de uma regra de eliminação.

Cada boneca é resolvida por um algoritmo de enumeração recursivo, baseado nos princípios do método das Bonecas Russas. Mais precisamente, os subproblemas associados às bonecas também são resolvidos por chamadas ao método de Bonecas Russas.

Estrutura Geral para CLIQUE PONDERADA

Nesta seção, apresentamos a estrutura geral do método das Bonecas Russas através do algoritmo proposto em [ Östergård 1999] e [ Östergård 2002] (Ver Algoritmo 5.1). Inicialmente, uma ordem dos vértices ρ é definida. Vamos usar a seguinte notação ρ = (ρ 1 , ρ 2 , . . . , ρ n ) para falar sobre o conjunto de vértices ordenados. Essa ordem é utilizada para o processo de geração das bonecas. Cada boneca está associado ao subgrafo 

G i = (V i , E i ), i ∈ {1, . . . , n}, onde V 1 = {ρ 1 } e V i+1 = V i ∪ {ρ i+1 }, E i = E[V i ]. O Algoritmo
G[V i-1 ∩ N (ρ i )] ou mostrar que seu peso é no máximo c[ρ i-1 ] -w(ρ i ). No Algoritmo 5.1, este problema é resolvido pela chamada RDS({ρ i }, U ∩ N (ρ i ), W ), onde U
mantém os iterados V i e W representa um limite inferior para a próxima boneca, que passa a receber o peso da clique máxima em G i , caso este seja maior.

De maneira geral, a ordem utilizada em [ Östergård 2002] para CLIQUE e a utilizada em [ Östergård 1999] para CLIQUE PONDERADA tentam limitar o crescimento de c[ρ i ] durante o processo de enumeração.

Algoritmo 5.1 Algoritmo de enumeração das bonecas

função Inicial ρ ← (ρ 1 , . . . , ρ n ) c[ρ 1 ] ← w(ρ 1 ) W ← c(ρ 1 ) U ← {ρ 1 } Para i ← 2 até n faça RDS({ρ i }, U ∩ N (ρ i ), W ) c[ρ i ] ← W U ← U ∪ {ρ i }
Segundo Östergård [ Östergård 1999], é um problema em aberto estudar como diferentes ordens dos vértices afetam o desempenho do Algoritmo 5.1 e determinar quais são as características de uma boa ordem.

Em [ Östergård 2002], a ordem inicial dos vértices baseada em uma heurística de coloração mostrou-se experimentalmente eficiente para a clique máxima. Nessa coloração, as classes de cores são construídas uma por vez, adicionando sempre o vértice com o maior grau no grafo não colorido e numerando estes vértices como (ρ 1 , . . . , ρ n ).

Já para a clique máxima ponderada [ Östergård 1999], a ordem dos vértices baseada em seus pesos(com um critério de desempate) obteve os melhores resultados experimentais. Nessa ordem, ρ n é o vértice com o maior peso. Em caso de empate, será escolhido o vértice com a maior soma dos pesos de seus vizinhos. Iterativamente, para i = n -1, . . . , 1, o vértice ρ i é selecionado aplicado a mesma regra em G i .

Em [ Östergård 2002 A primeira regra de poda utiliza o peso do conjunto P . O subproblema (C, P, LB) pode ser podado, se w(C) + w(P ) ≤ LB.

A segunda regra de poda utiliza o vetor de soluções c[.], gerado ao longo do processo, como segue.

Lema 5 Para um subproblema (C, P, LB), se existe um j tal que P ⊆ V j e c(ρ j ) + Como no Algoritmo 5.1, uma ordem inicial dos vértices ρ é definida. Em nosso caso, vamos utilizar as duas ordens já apresentadas no Capítulo 4. Esta ordem inicial será utilizada para definir os vértices associados a cada boneca. Precisamente, cada boneca está associada ao subgrafo 

w(C \ V j ) ≤ LB então toda clique C tal que C ⊆ (C ∪ P ) tem w(C ) ≤ LB. Prova Seja C ⊆ C ∪ P . Então C ⊆ C ∪ V j e, conseqüentemente, C = (C ∩ V j ) ∪ (C ∩ (C \ V j )). Como essa partição é disjunta, temos que w(C ) = w(C ∩ V j ) + w(C ∩ (C \ V j )) ≤ c(ρ j ) + w(C \ V j ) ≤ LB. Particularmente, no subproblema ({ρ i }, V i-1 ∩ N (ρ i ), c(ρ i-1 )), temos que P ⊆ V i-1 . Logo, sempre existe j ≤ i -1 tal que P ⊆ V j . O
G i = (V i , E i ), i ∈ {1, . . . , n}, onde V 1 = {ρ 1 },V i+1 = V i ∪ {ρ i+1 } e E i = E[V i ]. A criação
, ou seja, Q ← Q \ N (v); Q ← Q \ {v}.
A construção de S i continua até Q tornar-se vazio, quando S i será um conjunto independente maximal. O peso de S i é dado pelo menor peso residual de seus vértices ou valor corrente de K, o que for menor. O valor de K e o peso residual de cada vértice v de S i é atualizado, decrementando-os do peso da classe de cor S i . Os vértices com peso residual igual a zero podem ser removidos de R. A heurística de coloração ponderada termina quando K torna-se zero ou R torna-se vazio.

Os bits de todos os vetores de bits são organizados seguindo a ordem ρ. Logo, por exemplo, a instrução ´´selecione o primeiro vértice na ordem inicial que está em Q" poderia ser substituída por ´´selecione o primeiro bit setado em 1 do vetor de bits Q". As instruções em caixas são substituídas por instruções específicas que manipulam diretamente os vetores de bits.

Algoritmo 5.3 Heurística de Coloração Ponderada Inteira Modificada função ColoraçãoRestrita(R,K) Para v ∈ V faça res(v) ← w(v) i ← 1 Enquanto K > 0 e R = ∅ faça S i ← ∅ Q ← R Enquanto Q = ∅ faça v ← Selecione o primeiro elemento de Q. Q ← Q \ N (v) Q ← Q \ {v} S i ← S i ∪ {v} min res ← min{res(v)|v ∈ S i } y(S i ) ← min(min res, K) K ← K -y(S i ) Para v ∈ S i faça res(v) ← res(v) -y(S i ) Se res(v) = 0 então R ← R \ {v} i ← i + 1
Se, ao final do Algoritmo 5.3, o conjunto R for igual a ∅, então o peso da coloração ponderada inteira de P é menor igual a LB -w(C). Logo, o subproblema (C, P, LB) pode ser podado.

O uso da heurística de coloração leva à modificação da função RDS (Algoritmo 5.2), que passamos a chamar de BITRDS, conforme descrição no Algoritmo 5.4. Incluímos uma segunda regra de poda, alteramos a definição do conjunto de ramificação, porém mantemos a estratégia de ramificar o último vértice do conjunto seguindo a ordem ρ. Observe que essa combinação consegue aproveitar tanto a regra de poda definida pela vetor c quanto pela heurística de coloração ponderada.

Algoritmo 5.4 Algoritmo de Bonecas Russas BITRDS. função BITRDS(C, P , LB ) Quando o tempo limite é ultrapassado, tal ocorrência é assinalada como * na tabela.

Se w(C) > LB então LB ← w(C) R ← P ColoraçãoRestrita(R, LB -w(C)) Enquanto R = ∅ faça v ← Selecione o último vértice de R seguindo a ordem ρ R ← R \ {v} u ←
Identificamos em negrito o melhor desempenho em cada caso.

Número de Subproblemas

Comparando apenas os algoritmos de Bonecas Russas com relação ao número de subproblemas( Ver Tabela 5.3), temos os seguintes casos:

Para as instâncias com densidade entre 65% e 90%( com exceção da família p-hat), BITRDS1 vence BITRDS2, seguido por CLIQUER.

Para as instâncias com densidade superior 90% e da família p-hat, RDS2 supera BITRDS1, seguido por CLIQUER.

A diferença no número de subproblemas é bem mais expressiva quando comparamos cada um dos 2 algoritmos com CLIQUER do que em uma comparação entre os dois. O algoritmo BITRDS1 resolve 7 instâncias que CLIQUER não foi capaz de resolver em 2h (san1000, san400 0.7 1, san400 0.7 2, san400 0.7 3, p hat500-3, san200 0.9 1 e san400 0.9 1 ). Para as instâncias que ambos conseguem resolver dentro do tempo limite, a redução no número de subproblemas chega a ser de 4 ordens de magnitude na instância hamming10-2, levando a uma redução no tempo de processamento de 716.315s para 1.81s (Tabela 5.4) Já RDS2 resolve 11 instâncias não resolvidas por CLIQUER dentro do tempo limite considerado (san1000, san400 0.7 1, san400 0.7 2, san400 0.7 3, p hat1500-2, p hat500-3, gen400 p0.9 55, gen400 p0.9 75, san200 0.9 1,san400 0.9 1 e MANN a27 ). Para as instâncias em ambos conseguem resolver dentro do tempo limite, a redução no número de subproblemas chega a ser 5 ordens de magnitude na instância gen200 p0.9 55, levando a uma redução no tempo de processamento de 885.36s para 0.26s (Tabela 5.4).

Comparando Em [Posta, Ferland e Michelon 2011], a Busca por Resolução é generalizada para resolver um problema qualquer de programação inteira.

O Método de Busca

Em [START_REF] Chv Átal | Resolution search[END_REF], Chvátal [Chvátal 1997] propôs um método exato diferente para problemas de otimização com variáveis binárias, chamado Busca por Resolução. O objetivo principal era definir um método alternativo ao de enumeração implícita menos dependente da estratégia de ramificação. A dependência extrema da estratégia de ramificação ocasiona o fenômeno conhecido como thrashing nos métodos de enumeração implícita.

Na busca por resolução, a árvore de busca é substituída por uma família de condições lógicas que, representam o espaço de busca explorado. Por exemplo, a cláusula x 1 ∧ x 3 ∧ x 6 representa o conjunto de soluções com x 1 = x 6 = 1 e

x 3 = 0 e qualquer valor para as demais variáveis binárias. Uma cláusula é declarada um nogood 1 quando ela está associada a uma região já explorada do espaço de

1 O termo nogoods é um termo emprestado da terminologia de programação por restrições.

busca. Um mecanismo de inferência é aplicado à família de condições lógicas para a obtenção de uma região do espaço de busca não alcançada pelos nogoods memorizados. Uma restrição sobre estrutura das condições lógicas armazenadas garante que o mecanismo de inferência execute em tempo polinomial e que o número de nogoods memorizados seja linear.

Em geral, o esforço computacional da etapa de atualização da família está diretamente relacionado com o grau de liberdade de escolha da região do espaço de busca ainda não alcançado. Quanto maior a liberdade de escolha da região não alcançada, maior será o esforço computacional relacionado com a atualização da família.

Definições preliminares

Na Busca por Resolução, um nogood pode ser entendido como uma combinação de valores para algumas variáveis que não podem fazer parte de uma solução desejada (viável ou melhor que uma solução viável conhecida). Logo, qualquer combinação de valores das variáveis que seja derivada de um nogood deve ser evitada durante o processo de busca. Essas informações são utilizadas para selecionar novas regiões do espaço de busca ainda não explorado. A menos que dito o contrário, consideramos um problema de maximização, definido sobre n variáveis binárias: max{c T x|Ax ≥ b, x ∈ {0, 1}}.

A seguir, apresentaremos as notações e definições que serão utilizadas ao longo desse capítulo.

Solução Parcial

Definição 1 Uma solução parcial é um vetor (u 1 , u 2 , . . . , u n ) ∈ {0, 1, * } n . Se u i = * dizemos que u i está livre; caso contrário, u i está fixa. Uma solução parcial define, pois, uma fixação de valor para algumas das variáveis do problema.

Uma solução parcial é denominada solução completa se não tem variáveis livres.

Definição 2 Se (u 1 , u 2 , . . . , u n ) ∈ {0, 1, * } n e (v 1 , v 2 , . . . , v n ) ∈ {0, 1, * } n tais que u j = v j , se u j = * então dizemos que (v 1 , v 2 , . . . , v n ) é uma extensão de (u 1 , u 2 , . . . , u n ) e denotamos por (u 1 , u 2 , . . . , u n ) (v 1 , v 2 , . . . , v n ) Por exemplo, se U = (1, 1, * , * ) e V = (1, 1, * , 1), então V é uma extensão de U (U V ).
Definição 3 Para uma solução parcial U , o conjunto X(U ), chamado cobertura ou alcance de U , será definido como

X(U ) = {V | U V } Uma solução parcial V é coberta por U se somente se V ∈ X(U ). Definição 4 Duas soluções parciais U = (u 1 , . . . , u n ) e V = (v 1 , . . . , v n ) são conflitantes ou conflitam se existe i ∈ {1, . . . , n} tal que u i ∈ {0, 1} e v i ∈ {0, 1}
e u i = v i . Caso contrário, são ditos não-conflitantes.

Definição 5 A união de duas soluções parciais não-conflitantes

U = (u 1 , . . . , u n ) e V = (v 1 , . . . , v n ) é a solução parcial W = U ∪ V tal que w i =          u i , seu i ∈ {0, 1} v i , sev i ∈ {0, 1} * u i = v i = *
Proposição 4 Para duas soluções parciais U e V valem as seguintes propriedades:

SeU V então X(V ) ⊆ X(U ). Se U e V não conflitam então X(U ∪ V ) = X(U ) ∩ X(V ) Se U e V não conflitam então X(U ) ∩ X(V ) = ∅ Toda solução parcial U = (u 1 , . . . , u n ) ∈ {0, 1, * } n pode ser descrita,
alternativamente, por uma cláusula não conflitante C, definida pela a conjunção dos literais x i , quando u i = 1, e x i , quando u i = 0. Em outras palavras, os literais das cláusulas indicam os valores das variáveis fixadas na solução parcial. Por exemplo,

U = (1, * , 0, 1, * ) ⇒ C = x 1 ∧ x 3 ∧ x 4 (6.1)
Dessa forma, vamos indistintamente usar a representação vetorial ou em cláusula, conforme seja mais conveniente, assim como usar os termos solução parcial e cláusula de forma indistinta. Além disso, por simplicidade, vamos alternativamente denotar uma cláusula conjuntiva sem os "∧" ou pelo conjunto de literais que nela aparecem.

Assim, no exemplo acima,

U = (1, * , 0, 1, * ) ⇒ C = x 1 ∧ x 3 ∧ x 4 = x 1 x 3 x 4 = {x 1 , x 3 , x 4 } (6.2)
Em particular, ∅ denota uma solução parcial com todas as variáveis livres, ou seja, (*,*,. . . ,*).

Nogood

Definição 6 Para um problema de maximização, uma função f é chamada oráculo

se somente se f (U ) ≥ f (V ), quando U V .
Observe que um procedimento de limite superior para um problema de maximização pode ser utilizado como uma função oráculo. No algoritmo proposto por Chvátal, a função oráculo é dada pela relaxação linear do problema de maximização, aplicada a uma solução parcial U .

Algoritmo 6.1 oráculo ( U = (u 1 , u 2 , . . . , u n ) ) 1: Seja X U = {Ax ≥ b, 0 ≤ x ≤ 1, x j = u j para todo u j = * } 2: Se {c T x|x ∈ X U } é inviável então 3: Retorne -∞ 4: Senão Se max{c T x|x ∈ X U } é ilimitado então 5: Retorne +∞ 6: Senão 7: Retorne max{c T x|x ∈ X U }
Finalmente, podemos definir uma combinação de valores das variáveis que não podem fazer parte de nenhuma solução desejável. Essa combinação de valores está associada com uma solução parcial considerada não promissora pela função oráculo.

Definição 7 Seja record um limite inferior para um problema de maximização.

Uma solução parcial U é chamada um nogood se oráculo(U ) ≤ record.

Nogoods podem ser obtidos de diversas formas. Em particular, dada uma solução parcial U , tal que X(U ) represente uma região do espaço de busca ainda não explorado, deseja-se encontrar um nogood que cubra pelo menos uma parte dessa região. Chvátal sugere um procedimento, chamado obstáculo, para encontrar uma solução parcial S com tais propriedades, ou seja, i. S é um nogood.

ii. X(S) ∩ X(U ) = ∅ Uma implementação simples do procedimento obstáculo seria iterativamente fixar variáveis livres em U até descobrir uma solução parcial S tal que oráculo(S) = -∞ ou S é viável (neste caso, record pode ser atualizado por max(record, oráculo(S)). Nos dois casos, temos que S é um nogood, pois oráculo(S) ≤ record. Adicionalmente, X(U ) ∩ X(S) = ∅, pois S U .

Por ora é suficiente saber que encontrar uma solução com as propriedades (i) e

(ii) é possível. Mais detalhes sobre a implementação do obstáculo serão apresentados na Subseção 6.1.5.

Definição 8 O alcance X(F) de uma família F = [U 1 , . . . , U m ] de soluções parciais é o conjunto de todas as soluções parciais cobertas por pelo menos um elemento da família F, ou seja, Selecione uma solução parcial U F tal que U F ∈ X(F) 5:

X(F) = m i=1 X(U i ) 6 
obstáculo(U F , record, S).

6:

Atualize a família de nogoods com S.

O segundo ponto fundamental é encontrar a solução parcial U F não alcançada pela família F. Isto equivale a um problema de satisfabilidade de uma fórmula obtida pelo complemento dos nogoods da família F. No exemplo seguinte, ilustramos como obter essa fórmula.

Exemplo 7 Considere a seguinte família

F = [x 1 x 2 , x 1 x 2 x 3 , x 3 x 4 x 5 ].
Associada à família F, temos uma fórmula α F , formada pela conjunção do complemento das cláusulas associadas a cada nogood de F:

α F = (x 1 ∨ x 2 ) ∧ (x 1 ∨ x 2 ∨ x 3 ) ∧ (x 3 ∨ x 4 ∨ x 5 )
Essa fórmula representa a região do espaço de busca ainda não explorado pela família F. Ela pode ser satisfeita de diversas maneiras. Por exemplo, x 1 x 2 x 3 e x 2 x 3 satisfazem a fórmula obtida pela família F. Cada solução parcial que satisfaz a fórmula α F representa uma solução parcial não alcançada por F, utilizada na Linha 4 do Algoritmo 6.2.

Claramente, encontrar U F torna-se mais complicado à medida que o tamanho da família cresce. Em princípio, a quantidade de nogoods gerado no processo pode ser exponencial. Este poderia ser um grave problema para a Busca por Resolução.

Por essas razões, faz-se necessário impor certas restrições à família F para que ela mantenha uma estrutura que permita gerar de maneira mais fácil U F . Além disso, essa restrição mantém o tamanho da família polinomial. A estrutura será apresentada na subseção seguinte. 

w i ∈ C j se somente se j = i (6.3) Se w i ∈ C j então j > i (6.4) Se w ∈ C i ∧ w ∈ C j então (w i = w) ∨ (w j = w) (6.5) Dizemos que w i é o representante de C i , i = 1, . . . , m.
A propriedade (6.3) estabelece que o representante de C i só aparece em C i . A propriedade (6.4) diz que a negação do representante de C i só pode figurar em uma cláusula C j , quando j > i. A propriedade (6.5) assegura que apenas representantes podem aparecer também negados em uma outra cláusula da família.

Exemplo 8 A família F = [C 1 = x 1 x 2 , C 2 = x 1 x 2 x 3 , C 3 = x 3 x 4 x 5 ] e o conjunto de literais W = [x 1 , x 3 , x 4
] têm a estrutura path-like. Note que x 1 ,x 3 e x 4 só aparecem, respectivamente, em C 1 ,C 2 e C 3 . A negação de cada w i ou não aparece ou aparece apenas C j tal que j > i. Todo literal que aparece em uma cláusula assim como sua negação pertence a W.

Exemplo 9 A família F = [C 1 = x 1 x 2 , C 2 = x 1 x 2 x 3 , C 3 = x 4 x 5 ] e o conjunto de literais W = [w 1 = x 1 , w 2 = x 2 , w 3 = x 4 ] não têm a estrutura path-like, pois o representante de C 2 (a saber, w 2 ) aparece em C 1 e C 2 .
Dada uma família F e um conjunto de literais W com a estrutura path-like, uma solução parcial não alcançada por F, denotada U F , pode ser determinada da seguinte maneira:

Proposição 5 Seja F = [C 1 , C 2 , . . . , C m ] uma família e W = [w 1 , w 2 , . . . , w m ] um
conjunto de literais com a estrutura de path-like. Uma solução parcial válida não alcançada por F é:

U F = i=1 ((C i -{w i }) ∪ {w i })
Prova Vamos mostrar que U F é uma solução parcial válida, ou seja, sua cláusula associada não é uma contradição. A propriedade (6.3) garante que não existe contradição entre (C i -w i ) ∧ w j . A propriedade (6.4) implica que um literal e a sua negação não podem ser simultaneamente representante , ou seja, não existe contradição em m i=1 {w i }. Já (6.5) implica que qualquer literal de C i -w i não ocorre negado em C j -w j . Logo, as três propriedades garantem que U F é uma solução parcial válida.

Mais ainda, a inclusão de

w i em U F torna verdadeira a fórmula α F = m i=1 C i , levando a U F ∈ X(F).
A família path-like F pode ser estendida seguinte maneira:

Proposição 6 Uma família F = [C 1 , C 2 , . . . , C m , C m+1 ] e um conjunto de literais W = [w 1 , w 2 , . . . , w m , w m+1 ] têm uma estrutura path-like se a família F = [C 1 , C 2 , . . . , C m ] e um conjunto de literais W = [w 1 , w 2 , . . . , w m ] têm a estrutura path-like e: i. w m+1 ∈ C m+1 ii. w m+1 ∈ U F iii. w m+1 ∈ U F . iv. Se w ∈ U F então w ∈ C m+1
Prova Para mostrar (6.3) é suficiente mostrar que w m+1 ∈ C i , para i = 1, . . . , m.

A propriedade (ii) garante que w m+1 ∈ C i -w i . A propriedade (iii) assegura que w m+1 ∈ {w i }, ou seja, w m+1 ∈ {w i }, para i = 1, . . . , m. Logo, w m+1 ∈ C i , para i = 1, . . . , m Para (6.4), vamos demonstrar que w m+1 ∈ C i , para i = 1, . . . , m . A propriedade (iii) garante que w m+1 ∈ C i -w i . A propriedade (ii) assegura que w m+1 ∈ {w i }, ou seja, w m+1 ∈ {w i }, para i = 1, . . . , m. Logo, w m+1 ∈ C i para todo i = 1, . . . , m Para (6.5), devemos mostrar que se w ∈ C i -w i , para i = 1, . . . , m (ou seja, w está em C i , mas não é representante), então w ∈ C m+1 -{w m+1 }, ou seja, w não está em C m+1 ou é seu complemento. Isto é garantindo pela propriedade (iv), pois

C i -w i ⊆ U F .
Por definição, U F não está na cobertura de nenhuma solução parcial de F, isto é, U F ∈ X(F). A solução parcial U F é o ponto inicial utilizado pela função obstáculo para encontrar um nogood S tal que X(S) ∩ X(U F ) = ∅. O nogood S é usado para atualizar a família F. Tal atualização de F será separada em dois casos: i. S ⊆ U F (S contém um literal que pode ser representante)

ii. S ⊆ U F (S não contém um literal que pode ser representante)

No caso 1, o nogood S contém um literal w que satisfaz a condição path-like, permitindo que S seja adicionado diretamente à família. No caso 2, o nogood S não pode ser adicionado diretamente na família F. A seguir, mostramos esses dois casos: O Algoritmo 6.3 apresenta a atualização da família path-like F, de tamanho m, a partir de um nogood S tal que S ⊆ U F e X(S) ∩ X(U F ) = ∅. Sua corretude é dada pelo Corolário 1.

Algoritmo 6.3 AtualizaçãoFamília1(F, W, S) 1: Escolha um literal w tal que w ∈ S \ U F 2: C m+1 = S 3: w m+1 = w 4: F = F ∪ C m+1 5: m ← m + 1 Corolário 1 Seja uma família F = [C 1 , . . . , C m ] e um conjunto de literais W = [w 1 , . . . , w m ] com a estrutura path-like e um nogood S tal que S ⊆ U F e X(S) ∩ X(U F ) = ∅ então F = [C 1 , . . . , C m , S] e W = [w 1 , . . . , w m , w] tal que w ∈ S \ U F
(gerado pelo Algoritmo 6.3) mantêm a estrutura path-like.

Prova Por hipótese, S ⊆ U F . Então, podemos escolher um literal w ∈ S \ U F .

Também, por hipótese, X(S)

∩ X(U F ) = ∅. Logo, w ∈ U F . Logo, u ∈ S implica que u ∈ U F , u ∈ U F implica que u ∈ S. Então w ∈ S, w ∈ U F , conseqüentemente
w ∈ U F e assim todas as condições da Proposição 6 são satisfeitas.

Exemplo 10 Considere o seguinte exemplo:

F 0 = ∅, W = ∅, U F 0 = ∅. Suponha S = x 2 x 3 , e portanto, C 1 = S
Podemos escolher x 2 ou x 3 para ser w 1 .

F 1 = [x 2 x 3 ], W = [x 2 ], U F 1 = x 2 x 3 . Suponha S = x 3 x 6 , e portanto, C 2 = S
Neste caso, podemos escolher x 6 para ser w 2 .

F 2 = [x 2 x 3 , x 3 x 6 ], W = [x 2 , x 6 ], U F 2 = x 2 x 3 x 6 . Suponha S = x 2 x 3 x 6
Neste caso, não existe nenhum literal que possa ser escolhido para ser w 3 .

Quando S ⊆ U F não existe um representante de modo a estender a família diretamente. Neste caso, a atualização da família passa por duas etapas. Primeiro, são resolvidos os conflitos entre S e a família F, gerando um nogood reduzido R, através da regra da resolução. Em seguida, R é usado para atualizar a família, pela regra da absorção. Prova É suficiente mostrar que X(A∇B) ⊆ X(A) ∪ X(B). De fato, se U é uma extensão de A∇B, então U é uma extensão de A, ou B, ou de ambos, dependendo se a variável associada ao literal conflitante w é 0,1 ou * em U . Logo, X(A∇B) ⊆

X(A) ∪ X(B).

A seguinte proposição estabelece que um nogood S obtido pelo obstáculo e os nogoods da família F podem conflitar apenas nos literais representantes, ou seja, (C j -w j )) (6.7)

w i ∈ S, para i = 1, . . . , m. Proposição 8 Seja S um nogood tal que X(S) ∩ X(U F ) = ∅, onde F = [C 1 , . . . , C m ] e W = [
Uma vez obtida a propriedade (6.7) acima com a fase ResoluçãoNogood, podemos proceder com a atualização da família, realizando os seguintes passos:

Passo 1: Encontre o menor k tal que R ⊆ ( k j=1 (C j -w j )). Passo 2: Escolha um literal w ∈ R -(C 1 ∪ . . . C k-1 ) Passo 3: Faça C k ← R e w k ← w
Passo 4: Remova todas as cláusulas C k+1 , . . . , C m que contenham w.

Os passos (1) a (3) são realizados pelo procedimento AbsorçãoNogood(Algoritmo 6.5), cuja corretude segue da Proposição 9.

Algoritmo 6.5 AbsorçãoNogood(F, W, R, k) 1: Para k ← 1 até m faça 2: Se R ⊆ ( k j=1 (C j -w j )) então 3: pare 4: Escolha um w ∈ R -(C 1 ∪ . . . C k-1 ) 5: C k ← R 6: w k ← w Proposição 9 Seja F = [C 1 , . . . , C k-1 ] e W = [w 1 , . . . , w k-1 ] uma família path-like. Seja um nogood R ⊆ m i=1 C i -w i , obtido por ResoluçãonNogood. Seja k ≤ m o menor índice tal que R ⊆ k i=1 C i -w i e w ∈ R -(C 1 ∪ C 2 ∪ . . . ∪ C k-1 ). Então F = [C 1 , . . . , C k-1 , R] e W = [w 1 , . . . , w k-1 , w] é uma família path-like. Prova Como k é o menor índice tal que R ⊆ k i=1 C i -w i , temos que R ⊆ k-1 i=1 C i - w i . Como k-1 i=1 {w i }∩R = ∅, devido a ResoluçãoNogood, podemos concluir que R ⊆ k-1 i=1 (C i -w i ) ∪ {w i }, ou seja, R ⊆ U F k-1 , onde F k-1 = [C 1 , . . . , C k-1 ]. Além disso, como R não tem conflitos com U F k-1 após a ResoluçãoNogood, temos que X(R) ∩ X(U F k-1 ) = ∅. Pelo Corolário 1, F = [C 1 , . . . , C k-1 , R] e W = [w 1 , . . . , w k-1 , w] é uma família path-like.
Os nogoods C k+1 , C k+2 , . . . , C m podem ser aproveitados dependendo se o representante w do novo nogood R pertence ou não a eles, como mostra a seguinte proposição.

Proposição 10 Sejam k, R e w como na Proposição 9. Sejam {i 1 , i 2 , . . . , i p } ⊆ {k + 1, . . . , m} tais que

i 1 < i 2 < . . . < i p . Então F = [C 1 , . . . , C k-1 , R, C i 1 , C i 2 , . . . , C ip ] e W = [w 1 , . . . , w k-1 , w, w i 1 , w i 2 , . . . , w ip ] é path-like se somente se w ∈ C i j , para j = 1, . . . , p
Prova Se F e W é path-like, pela propriedade (6.3), o literal w só pode aparecer em R. Logo, w ∈ C i j , j = 1, . . . , p. Suponha agora que w ∈ C i j , j = 1, . . . , p.

Como

F e W é path-like e R ⊆ k i=1 C i (o que implica, por exemplo, w i j ∈ R)
, temos a propriedade (6.3). Para (6.4), falta garantir que w i j ∈ R, j = 1, . . . , p, o que é verdade, pois R e C i j não conflitam. Finalmente, (6.5) também é assegurada pelo fato de que R e C i j , j = 1, . . . , p são não conflitantes e, portanto, não pode ocorrer w ∈ R e w ∈ C i j , para qualquer w.

Formalmente podemos definir essa sequência de operações da seguinte maneira:

Algoritmo 6.6 ReciclandoNogood(F, W, k) 1: M ← m 2: m ← k 3: w k é o representante do novo nogood C k 4: Para i ← k + 1 até M faça 5: Se w k ∈ C i então 6: m ← m + 1 7: C m ← C i 8:
w m ← w i A atualização da família quando S não tem um literal representante pode ser vista no Algoritmo 6.7. Algoritmo 6.7 AtualizaçãoFamília2(F, W, S, k)

1: ResoluçãoNogood(F, W, S, R) 2: AbsorçãoNogood(F, W, R, k) 3: ReciclandoNogood(F, W, k)
Corolário 2 Seja F uma família path-like e um nogood S ⊆ U F tal que X(S) ∩ X(U F ) = ∅. Então Algoritmo 6.8 que gera uma nova família que mantém a propriedade path-like.

Prova Pela Proposição 9, podemos concluir que

F = [C 1 , . . . , C k-1 , R] e W =
[w 1 , . . . , w k-1 , w] é path-like. Pela Proposição 10, as cláusulas dentre C k+1 , . . . , C m restauradas por ReciclandoNogood(Algoritmo 6.6) mantêm a estrutura path-like.

O processo completo de atualização da família pode ser apresentado pelo Algoritmo 6.8. Note que w k ∈ S, o nogood S pode ser usado novamente para atualizar a família corrente (Linha 6). O Exemplo 11 ilustra uma atualização da família em que o nogood S é usado uma única vez. Já no Exemplo 12, o mesmo nogood é utilizado para atualizar a família duas vezes.

Algoritmo 6.8 AtualizaçãoFamília(F, W, S)

1: Se S ⊆ U F então 2: AtualizaçãoFamília1(F, W, S) 3: Senão 4: AtualizaçãoFamília2(F, W, S, k) 5: Se w k ∈ S então 6: AtualizaçãoFamília(F, W, S)
Exemplo 11 Considere a família path-like e o nogood S abaixo:

C 1 = x 2 x 3 (w 1 = x 2 ) C 2 = x 3 x 6 (w 2 = x 6 ) C 3 = x 1 x 5 x 9 (w 3 = x 1 ) C 4 = x 2 x 5 x 8 (w 4 = x 8 ) C 5 = x 3 x 5 x 7 x 9 (w 5 = x 7 ) C 6 = x 2 x 4 x 6 (w 6 = x 4 ) S = x 5 x 6 x 7 Aplicando o procedimento ResoluçãoNogood: R = S∇C 5 = x 3 x 5 x 6 x 9 R = R∇C 2 = x 3 x 5 x 9 Aplicando o procedimento AbsorçãoNogood: O menor k tal que R ⊆ ( k j=1 (C j -w j )) é 3. C 3 = R Escolha w = x 5 Aplicando o procedimento ReciclandoNogood: Remova C 4 e C 5 de F e mantenha C 6
A família atualizada F é:

C 1 = x 2 x 3 (w 1 = x 2 ) C 2 = x 3 x 6 (w 2 = x 6 ) C 3 = x 3 x 5 x 9 (w 3 = x 5 ) C 4 = x 2 x 4 x 6 (w 4 = x 4 ) Observe que x 5 ∈ S.
Exemplo 12 Considere a seguinte família path-like e o nogood S:

C 1 = x 3 (w 1 = x 3 ) C 2 = x 2 x 6 (w 2 = x 2 ) C 3 = x 1 x 5 x 6 (w 3 = x 1 ) C 4 = x 3 x 6 x 9 (w 4 = x 9 ) C 5 = x 5 x 7 x 9 (w 5 = x 7 ) C 6 = x 5 x 7 x 8 (w 6 = x 8 ) S = x 6 x 7 x 8 Aplicando o procedimento ResoluçãoNogood: R = S∇C 6 = x 6 x 7 x 8 ∇x 5 x 7 x 8 = x 5 x 6 x 7 R = R∇C 5 = x 5 x 6 x 7 ∇x 5 x 7 x 9 = x 5 x 6 x 9 R = R∇C 4 = x 5 x 6 x 9 ∇x 3 x 6 x 9 = x 3 x 5 x 6 R = R∇C 1 = x 3 x 5 x 6 ∇x 3 = x 5 x 6 Aplicando o procedimento AbsorçãoNogood: O menor k tal que R ⊆ ( k j=1 (C j -w j )) é 3. C 3 = R Escolha w = x 5 Aplicando o procedimento ReciclandoNogood:
Remova C 5 e C 6 de F e mantenha C 4 A família atualizada F é:

C 1 = x 3 (w 1 = x 3 ) C 2 = x 2 x 6 (w 2 = x 2 ) C 3 = x 5 x 6 (w 3 = x 5 )
C 4 = x 3 x 6 x 9 (w 4 = x 9 ) Observe que x 5 ∈ S. Logo, S pode ser adicionada na família F construída:

C 5 = x 6 x 7 x 8 (w 1 = x 7 )

Procedimento obstáculo

Em cada iteração da Busca por Resolução, uma região do espaço de busca ainda não explorada é parcialmente explorada por um procedimento chamado obstáculo(U, record, S) resultando em um nogood S. O procedimento obstáculo recebe dois parâmetros: U : Uma solução parcial não coberta pela família corrente, que, portanto representa uma região do espaço de busca ainda não explorada; e record: um limite inferior para um problema de maximização. e devolve um terceiro S: Um nogood encontrado a partir da solução parcial U tal que X(U )∩X(S) = ∅, representando a parte do espaço de busca implicitamente enumerado pelo procedimento obstáculo.

Essa exploração pode ser realizada de diversas maneiras, desde que X(U ) ∩

X(S) = ∅. Assim, w ∈ U implica que w ∈ S e bem como w ∈ S implica que w ∈ U .
Como vimos, essa propriedade garante que seja possível atualizar a família F usando S e mantendo a propriedade path-like.

Em [Chvátal 1997], é apresentada uma heurística para encontrar um nogood S que não conflita com U . O procedimento obstáculo apresentado por Chvátal pode ser separado em duas fases específicas: a fase de crescimento e a fase de decrescimento.

Na fase de crescimento, uma solução parcial U + é construída a partir de U tal que U U + e U + seja um nogood.

Na fase de decrescimento, uma solução parcial S é construída a partir da solução parcial U + tal que S U + e S seja um nogood.

Na fase de crescimento, o procedimento obstáculo substitui uma variável livre por 0 ou 1 até que

oráculo(U + ) ≤ record ou U + ∈ {0, 1} n .
(6.8)

Então temos dois casos:

oráculo(U + ) ≤ record e, conseqüentemente U + é um nogood.
oráculo(U + ) > record e U + é uma solução completa. Neste caso, o valor de record é atualizado para oráculo(U + ) e U + torna-se um nogood.

Claramente, X(U ) ∩ X(U + ) = ∅ e U + é um nogood. Logo, S = U + pode ser uma opção de retorno do procedimento obstáculo. Uma versão rápida para o procedimento obstáculo pode ser obtida implementando apenas a fase de crescimento, como no Algoritmo 6.9.

Algoritmo 6.9 obstáculo_rápido(U, record, S) 1: bound ← oráculo(U ) 2: Enquanto U ∈ {0, 1} n e bound > record faça 3:

Escolha um subscrito j com u j = * e um valor c ∈ {0,1}

4:

u j ← c 5:
bound ← oráculo(U )

6: Se bound > record então U é uma solução completa A seguir, apresentamos a heurística proposta por Chvátal para encontrar um nogood minimal (Algoritmo 6.10). Inicialmente, as variáveis fixadas em U são empilhadas. Depois, as variáveis fixadas na fase de crescimento são empilhadas.

Após o final da fase de crescimento, S recebe uma solução parcial U + representando um nogood. Enquanto a pilha não estiver vazia, uma variável x j é desempilhada e liberada em S. Se oráculo(S) > record, então a variável x j é necessária para definir um nogood minimal e seu valor anterior é recuperado. Caso contrário, a variável x j permanece liberada.

Algoritmo 6.10 obstáculo(U, record, S) 1: Inicialize a pilha vazia 2: Para i = 1 até n faça Se oráculo(S) > record então 21:

S j ← U j
Essa variável contribui para oráculo(S) ≤ record, logo ela é necessária para o nogood Observe que, se a fase de crescimento não gera uma solução completa, a última variável fixada em U + não é empilhada e não é analisada na fase de decrescimento.

Políticas de Ramificação

O algoritmo de Busca por Resolução usa duas políticas de ramificação durante o processo de busca, que diferenciamos como: (1) Uma política de mergulho e (2) Uma política de recomeço.

A política de mergulho é a estratégia de ramificação utilizada no procedimento obstáculo na fase de crescimento. Ela consiste em escolher uma variável livre e um valor para ser fixado, correspondendo a seguinte instrução:

Escolha um subscrito j com u j = * e um valor c ∈ {0,1} Essa política corresponde a estratégia de ramificação clássica utilizada nos algoritmos de enumeração implícita.

A política de recomeço é a estratégia de ramificação responsável por escolher o representante do novo nogood que, em última análise, é essencial para a definição do ponto de recomeço do mergulho, ou seja, U F . Tal política é implementada em duas situações:

No passo 1 do Algoritmo 6.3: Escolha um literal w tal que w ∈ S \ U F No passo 4 do Algoritmo 6.5:

Escolha um w ∈ R -(C 1 ∪ . . . C k-1 )
Em [Chvátal 1997], a política de mergulho utilizada é

Escolha a primeira variável na ordem lexicográfica tal que u j = * e fixe seu valor em 0.

Já a política de recomeço utilizada é

Escolha a última variável na ordem lexicográfica Em [Boussier 2008], temos uma implementação da Busca por Resolução sem a fase de decrescimento, utilizando diferentes políticas de mergulho e recomeço. As duas políticas de mergulho testadas são:

M 1 Escolha a variável livre com o menor custo reduzido e fixe-a no valor inteiro mais próximo de seu valor ótimo na relaxação linear do problema.

M 2 Escolha a primeira variável livre na ordem lexicográfica e fixe-a no valor inteiro mais próximo de seu valor ótimo na relaxação linear do problema.

Também são avaliados duas políticas de recomeço:

R 1 Escolha o literal associado à variável mais recentemente instanciada R 2 Escolha o literal associado à variável de menor custo reduzido.

Os resultados computacionais obtidos pelos autores mostram que o número médio de chamadas ao oráculo no algoritmo de Busca por Resolução que usa R 1 -M 1 é praticamente o mesmo daquele que usa R 1 -M 2 , sendo também similar ao número de resoluções da relaxação linear em um processo de enumeração implícita que usa as mesmas políticas de mergulho.

Por outro lado, a implementação da Busca por Resolução que utiliza R 2 -M 1 realiza menos chamadas ao oráculo que a versão que usa R 1 -M 1 , na maior parte das instâncias testadas. Esse resultado sugere que a política de recomeço introduz um nível de flexibilidade ao processo de busca que não consegue ser alcançado por um método de enumeração implícita.

Convergência

Para mostrar a convergência do método de Busca por Resolução, precisamos mostrar que a cada iteração o alcance da família cresce. Dado um problema com n variáveis, podemos definir a força de uma família F, denotada por τ (F), como 2 -n |X C (F)|, onde X C (F) são as soluções completas em X(F). Este valor, entre 0 e 1, representa a razão entre número de soluções exploradas pela família F e o número total de soluções. Infelizmente, o valor de τ (F) não necessariamente aumenta a cada iteração do algoritmo de Busca por Resolução. Contudo, podemos identificar um limite inferior para a força da família que cresce a cada iteração.

Dizemos que uma família F cobre uma variável x i se pelo menos um dos dois literais associados a x i aparece em uma cláusula de F.

Dada uma família F = [C 1 , . . . , C m ], seja n i o número de variáveis cobertas pela família [C 1 , . . . , C i ]. Proposição 11 Se F = [C 1 , . . . , C m ] então τ (F) ≥ σ(F), onde σ(F) = m i=1 2 -n i Prova Por indução, Se F = [C 1 ],
as soluções completas exploradas por F são aquelas onde as n 1 variáveis cobertas por C 1 estão fixas e as outras n -n 1 variáveis podem assumir qualquer valor em {0,1}.

Logo, τ (F) = 2 -n (2 n-n 1 ) = 2 -n 1 = σ(F). Suponha o resultado verdadeiro para F = [C 1 , . . . , C m-1 ], ou seja, τ (F ) ≥ m-1 i=1 2 -n i . Considere F = [C 1 , . . . , C m-1 , C m ].
As soluções completas cobertas por F são as 2 n τ (F ) cobertas por F junto com aquelas não cobertas por F mas cobertas por C m . Estas últimas são aquelas cobertas por

C 1 ∧C 2 ∧C 2 ∧. . .∧C m-1 ∧C m .
Entre elas estão todas as 2 n-nm soluções completas, onde as n -n m variáveis não cobertas por F podem assumir qualquer valor em {0,1}. Logo,

τ (F) = 2 -n (2 n τ (F ) + 2 n-nm ) = τ (F ) + 2 -nm ≥ m-1 i=1 2 -n i + 2 -nm σ(F)
Teorema 3 Se F e F são duas famílias geradas pela Busca por Resolução com F obtida após F, então σ(F) < σ(F ).

Prova Vamos mostrar que σ(F) aumenta estritamente a cada execução da atualização da família. Sendo F = [C 1 , . . . , C m ] a família corrente, a nova família F pode ser obtida de duas maneiras:

i. S ⊆ U F : a família é aumentada para F = [C 1 , . . . , C m , C m+1 ], onde C m+1 = S. Claramente, σ(F ) = m i=1 2 -n i + 2 -n m+1 > m i 2 n i = σ(F ). (6.9) ii. S ⊆ U F : F = [C 1 , . . . , C m ] é substituída por F = [C 1 , . . . , C k-1 , R] e então
possivelmente estendida por alguns dos nogoods C k+1 , . . . , C m . Primeiramente, calculamos σ(F) e então mostramos que σ(F

) > σ(F). Como n i+1 > n i , i = 1, . . . , m -1, σ(F) = k-1 i=1 2 -n i + m i=k 2 -n i = k-1 i=1 2 -n i + 2 -n k (1 + 2 n k -n k+1 + . . . + 2 n k -nm ) < k-1 i=1 2 -n i + 2 -n k * 2 Por outro lado, como R ⊆ k i=1 (C i -{w i }), toda variável coberta por [C 1 , . . . , C k-1 , R] é coberta por [C 1 , . . . , C k-1 , C k ]. Além disso, a variável associada a w k não é coberta por [C 1 , . . . , C k-1 ], pois w k é o representante de C k , de modo que então nem ele e nem sua negação aparecem na família [C 1 . . . C k-1 ]. Sabemos também que nem w k nem w k aparecem em R. Logo, o número de literais cobertos por F , denotado por n , é tal que n ≤ n k -1. Portanto, σ(F ) = k-1 i=1 2 -n i + 2 -n ≥ k-1 i=1 2 -n i + 2 -(n k -1) = k-1 i=1 2 -n i + 2 * 2 -n k > σ(F) (6.10)
A possível inclusão em F de alguns dos nogood s C k+1 , . . . , C m só faria aumentar ainda mais σ(F ).

Em qualquer dos casos, o limite inferior da força da família cresce a cada iteração.

Corolário 3 O método da Busca por Resolução converge.

Otimalidade

Nesta seção, provamos a corretude do método de Busca por Resolução, ou melhor, que o mesmo converge para a solução ótima. Trivialmente, se existem vértices não vizinhos i e j tais que u i = 1 e u j = 1, então X(U ) não contém nenhuma solução viável, de modo que oráculo(U ) = -∞.

Definição 10 ( [Boussier 2008]) Seja r ∈ R. Um nogood C é r-nogood sse, para todo U ∈ {0, 1} n tal queC U , oráculo(U ) ≤ r. Lema 6 Se C 1 e C 2 são r-nogoods conflitantes com w ∈ C 1 e w ∈ C 2 , então C 3 = C 1 ∇C 2 é também r-nogood. Prova Suponha por absurdo que C 1 e C 2 são dois r-nogoods e C 3 = (C 1 -w) ∪ (C 2 -w), não é um r-nogood. Seja U ∈ {0, 1} n tal que C 3 U e oráculo(U ) > r. Então C 1 -w C 3 U e C 2 -w C 3 U . Por outro lado, w ∈ U ou w ∈ U . Se w ∈ U então C 1 U , pois C 1 -w U . Logo, oráculo(U ) ≤ r, porque C 1 é um r-nogood. Se w ∈ U então C 2 U , pois C 2 -w U . Logo, oráculo(U ) ≤ r, porque C 2 é um r-nogood.
= 1, . . . , N , R k foi gerado tendo oráculo(R k ) ≤ r k ≤ r * ou R k = R i ∇R j para i, j < k, onde r k é o valor corrente de record quando R k foi gerado. Vamos mostrar por indução que R k é r * -nogood, para todo k = 1, . . . , N . Trivialmente, R 1 é r * -nogood, pois R 1 foi gerado satisfazendo oráculo(R 1 ) ≤ r 1 ≤ r * . Suponha que R k seja um r * -nogood para k = 1, . . . , n. Se oráculo(R n+1 ) ≤ r n+1 ≤ r * , segue que R n+1 é r * -nogood. Do contrário, R n+1 = R i ∇R j , para i, j ∈ {1, . . . , n} e R n+1 é r * -nogood pelo Lema 6. Considere agora F = [C 1 , . . . , C m ] a última família gerada. Tome U ∈ {0, 1} n . Como X(F) = {0, 1} n , então C i U para algum i = 1, . . . , m. Como C i é um
Caso contrário, um limite superior para U é obtido pelo peso de C mais um limite superior para a maior clique ponderada em P , que será dado por uma heurística de coloração ponderada.

A heurística de coloração ponderada recebe um vetor de bits com os vértice de P e uma ordem ρ (ordem inicial dos vértices), representando a ordem em que os bits estão organizados no vetor de bits. Ela é passada implicitamente juntamente com o vetor de bits P . Ao longo deste trabalho, temos utilizado duas ordens iniciais ρ: a ordem menor peso primeiro e a ordem maior grau ponderado primeiro. Por simplicidade e para manter a uniformidade com as seções anteriores, mantemos a chamada ao oráculo como oráculo(U ), quando, na verdade, em nosso caso, deveria ser oráculo(U, C, P, π, color, cont). Os demais parâmetros são retornados pelo oráculo e podem ser usados em outros procedimentos Algoritmo 6.11 oráculo(U )

1: C ← ∅ 2: P ← V 3: Para j = 1 até n faça 4:
Se u j = 1 então 5:

Se j ∈ P então 6:

P ← P ∩ N (j) ; Retorne -∞ Inviabilidade Encontrada 10:

Senão Se u j = 0 então 11:

P ← P \ {j} ;

12: BITCOLOR(P, ρ, π, color, cont) record ← bound 8: S ← U

Política de recomeço

Para cada ordem inicial ρ, vamos propor duas estratégias de recomeço: R 1 : Escolha a primeira variável que pode ser representante na ordem inicial.

R 2 : Escolha a última variável que pode ser representante na ordem inicial.

Para cada ordem inicial, o critério de recomeço tem um significado diferente. Por exemplo, na ordem de menor peso primeiro, a estratégia R 1 prioriza inverter a fixação da variável associada ao vértice com o menor peso, enquanto a estratégia R 2 prioriza fixar no valor oposto a variável do vértice com o maior peso.

Em [Chvátal 1997], não temos uma indicação sólida para um bom critério para a escolha da política de recomeço. Em nosso caso, para cada critério de ordenação inicial dos vértices, vamos escolher uma política de recomeço mais adequada com base em testes computacionais preliminares.

A Tabela 6.1 apresenta o número de chamadas ao oráculo e o tempo de execução do algoritmo de Busca por Resolução utilizando as duas estratégias de recomeço com a ordem de menor peso primeiro. Apesar da estratégia R 1 obter o menor número de chamadas ao oráculo e o menor tempo de execução na maioria das vezes, as diferenças são muito pouco expressivas, de maneira que podemos considerar as duas estratégias comparáveis. Na próxima subseção, apresentamos um procedimento de obstáculo que realiza menos chamadas ao oráculo para encontrar um nogood. Este procedimento será chamado de obstáculo modificado.

Obstáculo Modificado

A heurística de coloração ponderada, além de prover um limite superior para o problema, devolve uma ordenação dos vértices e limites superiores parciais que podem ser aproveitados para a identificação de um nogood de maneira mais rápida. x 0 x 1 x 2 x 3 x 4 x 5 e os nogoods armazenados pela família, obtendo o nogood x 2 x 3 x 4 x 5 .

Na fase de absorção, o nogood x 2 x 3 x 4 x 5 assume a posição número 1 na família e

x 2 será escolhido como representante. Depois o nogood da posição 2 não é mantido pelo procedimento ReciclandoNogood. Desempilhe v da pilha

Iteração Família (F) Representante (W ) S record 0 ∅ ∅ x 0 x 1 x 2 x 3 x 4 x 5 1 [x 0 x 1 x 2 x 3 x 4 x 5 ] [x 0 ] x 0 x 1 x 2 x 3 x 4 x 5 2 [x 1 x 2 x 3 x 4 x 5 ] [x 1 ] x 1 x 2 x 3 x 4 x 5 3 [x 1 x 2 x 3 x 4 x 5 , x 0 x 1 x 2 x 3 x 4 x 5 ] [x 1 , x 0 ] x 0 x 1 x 2 x 3 x 4 x 5 4 [x 2 x 3 x 4 x 5 ] [x 2 , ] x 2 x 3 x 4 x 5 5 [x 3 x 4 x 5 ] [x 3 , ] x 1 x 2 x 3 x 4 x 5 6 [x 3 x 4 x 5 , x 1 x 2 x 3 x 4 x 5 ] [x 3 , x 1 ] x 0 x 1 x 2 x 3 x 4 x 5 7 [x 3 x 4 x 5 , x 1 x 2 x 3 x 4 x 5 , x 0 x 1 x 2 x 3 x 4 x 5 ] [x 3 , x 1 , x 0 ] x 0 x 1 x 2 x 3 x 4 x 5 8 [x 3 x 4 x 5 , x 2 x 4 x 5 ] [x 3 , x 2 ] x 2 x 3 x 4 x 5 9 [x 4 x 5 ] [x 4 ] x 4 x 5 10 [x 5 ] [x 5 ] x 4 x 5 11 [x 5 , x 4 x 5 ] [x 5 , x 4 ] x 4 x 5 12 ∅ ∅ ∅ Tabela 
17: i ← max{k|π[k] ∈ R ∩ N (v)} 18: u ← π[i] 19: U B ← w(C) + w(v) + color[u] 20:
Se U B ≤ record então 21:

S j ← * 22:
R ← R ∪ {v} A Tabela 6.6 apresenta uma comparação entre os algoritmos de Busca por

Resolução com a regra de recomeço R 1 e com procedimentos obstáculos apresentados (obstáculo padrão, obstáculo modificado e obstáculo modificado com decrescimento), para a ordem de menor peso primeiro. Podemos ver que a utilização do obstáculo modificado consegue uma boa redução do números de chamadas total ao oráculo, como também uma boa redução do tempo de execução com relação ao obstáculo padrão. Já a redução obtida pela adoção da fase de decrescimento acontece em uma escala menor, mas consideramos que ela é ainda evidente. Tabela 6.6: Comparação entre os procedimentos obstáculo padrão, modificado e modificado com fase de decrescimento considerando a ordem de menor peso primeiro.

A Tabela 6.7 apresenta uma comparação similar, agora para a ordem de maior grau ponderado primeiro. Novamente, conseguimos uma redução significativa com a utilização do procedimento de obstáculo modificado e uma redução menos expressiva com a fase de decrescimento, tanto no número de chamadas como no tempo de execução total. No problema da CLIQUE PONDERADA, dada uma ordem inicial dos vértices ρ = (ρ 1 , . . . , ρ n ), definimos uma sequência de n subproblemas (as bonecas), onde i-ésimo subproblema está associado ao subgrafo G[ρ 1 , . . . , ρ i ], i ∈ {1, . . . , n}. Depois da solução ótima do i-ésimo subproblema, podemos representar a região do espaço de busca explorada pelo seguinte nogood:

x ρ i+1 x ρ i+2 . . . x ρn (6.12)

Esse nogood diz que, para obter uma solução de valor maior que c(ρ i ), é preciso fixar em 1 pelo menos uma variável entre i + 1 e n, ou seja, é preciso escolher pelo menos um vértice entre ρ i+1 , . 

= (ρ 1 , . . . , ρ n ) record ← c(v 1 ) c(ρ 1 ) ← record U ← {ρ 1 } Para i ← 2 até limite faça RDS({ρ i }, U ∩ N (ρ i ), record) c[ρ i ] ← record U ← U ∪ {ρ i } Para i ← limite + 1 até n faça j ← max{k | v k ∈ N (v i )} c[v i ] ← max{c[v i-1 , c[v j ] + w(v i )]} Algoritmo de Busca por Resolução novo record ← heurística tabu com multivizinhaça. record ← max(record, novo record) Para i ← 1 até limite faça S i ← * Para i ← limite + 1 até n faça S i ← 0 F ← ∅ W ← ∅ AtualizaçãoFamília(S, F, W ). Enquanto X(F) = {0, 1} n faça Encontre U F obstáculo_híbrido(U F , record, S).
AtualizaçãoFamília(S, F, W ).

Oráculo

No oráculo proposto na Subseção 6.2.1 (Algoritmo 6.11), usamos a coloração ponderada para fornecer um limite superior. Agora, porém, temos um procedimento de limite superior com um custo computacional bem menor, dado pelo vetor de soluções ótimas das bonecas. Definimos então uma nova função oráculo, tirando proveito desse limite (Ver Algoritmo 6.16). A única mudança em relação ao anterior é que o limite superior para a clique ponderada máxima de P será dada pela tabela construída pelo Algoritmo de Bonecas Russas .

Algoritmo 6.16 oráculo(U )

1: C ← ∅ 2: P ← V 3: Para j = 1 até n faça 4:

Se u j = 1 então 5:

Se j ∈ P então 6:

P ← P ∩ N (j) ; 7: C ← C ∪ {j} ; 8: Senão 9:
Retorne -∞ Inviabilidade Encontrada 

U 1 ← U 8: Enquanto R = ∅ e bound > record faça 9: j ← max{k | v k ∈ R} 10: bound ← w(C) + c(v j ) 11:
Se bound > record então 12:

(u 1 ) j ← 0 

Todos os testes foram realizados num computador equipado com processador

Intel Core i7-2600K 3.40Ghz, 8Mb de cache, 6Gb de memória, utilizando sistema operacional Linux.

Similarmente aos experimentos anteriores, avaliamos o desempenho do algoritmo híbrido utilizando as principais instâncias disponíveis na literatura.

Grafos Aleatórios

No nosso experimento, nós geramos 10 grafos aleatórios para cada combinação n (número de vértices) e p (probabilidade de existência de cada aresta). Os pesos A redução em BR1 chega a ser 1 ordem de magnitude em relação BITCLIQUER1 para o grupo (400,0.8).

Já a Tabela 6.11 apresenta o tempo de execução médio de cada algoritmo.

Apesar de BR1 conseguir uma redução do número de colorações ponderadas com relação aos demais algoritmos em várias instâncias, essa redução não foi acompanhada por uma melhoria no tempo de execução. Mesmo assim, BR1 mostrou-se bastante competitivo com os demais algoritmos usando a mesma ordem inicial dos vértices. Além disso, dentro do tempo limite, BR1 resolveu uma instância do grupo (300, 0.90) que não foi resolvida por RDS1. O mesmo não aconteceu com BR2, que não conseguiu um tempo próximo ao melhor algoritmo que usa a mesma ordem. Na maioria dos casos, o tempo de execução de BR2 chega a ser perto do dobro de BITCLIQUE2 

DIMACS-W

Os resultados dos experimentos computacionais com as instâncias DIMACS-W podem ser vistos na Tabelas 6.12 e 6.13 . Agora, o tempo limite de resolução para cada instância é 2h (7200s latin square 10 (90,0.00) 1.00e+00 1.00e+00 0.00e+00 0.00e+00 1.00e+00 1.00e+00 r1000.5 (234,0.00) 1.00e+00 1.00e+00 0.00e+00 0.00e+00 1.00e+00 1.00e+00 Outro trabalho que deve ser feito é uma comparação de BITRDS com o algoritmo apresentado em [Corrêa et al. 2014]. Ambos integram a heurística de coloração ao método original, porém essa integração é realizada de maneira diferente.

Com relação ao algoritmo de Busca por Resolução, temos vários obstáculos pela frente, como:

Desenvolvimento de políticas de mergulho e recomeço eficientes.

Desenvolvimento de regras mais efetivas para a fase de decrescimento.

Adaptação do método para novos problemas de programação inteira. X ← X ∪ {v} B Enumeração de cliques maximais com peso acima de um limiar Em [START_REF] Brito | [END_REF], uma versão modificada de BK, para a enumeração de cliques com peso acima de um limiar, é apresentada (Ver Algoritmo A.2). A regra de pivoteamento utilizada consiste em escolher um vértice u ∈ P com o maior grau modificado (soma do grau do vértice u e dos graus dos seus vizinhos) e com o maior peso. Segundo os autores esta regra de pivoteamento acelera o processo de descoberta de cliques maximais pesadas. Além disso, o algoritmo utiliza uma regra de poda que usa como estimativa para a clique ponderada máxima de P a soma dos pesos dos vértices de P . Resultados computacionais mostraram que essas adaptações levam a um bom desempenho prático.

Algoritmo A.2 Algoritmo BKA [START_REF] Brito | [END_REF] 1: função BKA(C, P , X, limiar)

2:

Se P = ∅ e X = ∅ então Escolha um vértice pivô u ∈ P com o maior grau modificado. O segundo conjunto de instâncias, denominado INRC, foi obtido pela formulação usada em [Santos et al. 2014], e contém 60 instâncias. O terceiro conjunto de instâncias, denominado Telebus [Borndörfer et al. 1999], origina-se do problema de planejamento de rotas para o Telebus. O quarto conjunto de instâncias, denominado Uchoa, deriva de uma instância do problema de p-dispersão [Franco e Uchoa 2015].

A partir dos problemas de programação inteira são gerados grafos de conflito que definem as instâncias para o problema de enumeração de cliques.

Em geral, dado um problema de programação inteira, um grafo de conflito pode ser construído a partir da análise de suas restrições, usando técnicas de probing. O grafo de conflito tem um vértice i para cada variável x i . Dois vértices i e j definem uma aresta se, por exemplo, as variáveis correspondentes não podem assumir valor não nulo simultaneamente. Logo, uma clique K no grafo de conflito define uma desigualdade válida

i∈K x i ≤ 1
Assim, as desigualdades de clique violadas por uma solução fracionária x são definidas pelas cliques com peso maior que 1 no grafo de conflito onde cada vértice i é ponderado com xi . De outra forma, interessa-nos enumerar as cliques com peso maior que limiar, no grafo de conflito onde cada vértice i tem peso limiar * xi , sendo limiar escolhido para tornar os pesos inteiros.

Na verdade, grafos de conflitos podem ser construídos de forma mais geral, seja a partir de restrições originais do problema ou gerados pelo método de plano de cortes.

Em [Brito, Santos e ρ ← ordem ordem crescente dos graus modificados 3:

BIT BKC(∅, V (G), ∅, limiar)

4: função BITBKC(C, P , X, limiar)

5:

Se P = ∅ e X = ∅ então A ordem de expansão dos vértices P segue a ordem inicial. Novamente, as instruções em caixas são aquelas simplificadas pela utilização de vetores de bits.

Algoritmo A.4 Algoritmo BITBKA 1: função MAIN 2:

ρ ← ordem não decrescente de grau modificados. BITBKA(C ∪ {v}, P ∩ N (v) , X ∩ N (v) )

12:

P ← P \ {v} No último conjunto, todas as instâncias estão na segunda faixa de densidade(Ver 

  Ponderado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Gráfico com a razão entre a média dos limites superiores de cada heurística e a média do limite superior de YM, por densidade, para instâncias com 200 vértices . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Gráfico com a razão entre a média dos limites superiores de cada heurística e a média do limite superior de YM, por densidade, para instâncias com 300 vértices . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Gráfico com a razão entre a média dos tempos de execução de cada heurística e a média do tempo de execução de HCS, por densidade, para instâncias com 200 vértices . . . . . . . . . . . . . . . . . . . . . 3.9 Gráfico com a razão entre a média dos tempos de execução de cada heurística e a média do tempo de execução de HCS, por densidade, para instâncias com 300 vértices . . . . . . . . . . . . . . . . . . . . . 3.10 Esquema de ramificação de Balas-Yu . . . . . . . . . . . . . . . . . . 4.1 Relação entre uma clique C e os subconjuntos de vértices P A e OM . Fonte: [Wu, Hao e Glover 2012] . . . . . . . . . . . . . . . . . . . . . 5.1 Limites superiores dados pela soma dos pesos dos vértices e pelos valores de c[i] para cada G i , para i = 1, . . . , 4. . . . . . . . . . . . . . 5.2 Limites superiores dados pela soma dos pesos dos vértices e pelos valores de c[] para a resolução da penúltima boneca. . . . . . . . . . . 5.3 Limites superiores dados pela soma dos pesos dos vértices e pelos valores de c[] para a resolução da última boneca. . . . . . . . . . . . . 6.1 Grafo ponderado com os vértices ordenados seguindo a ordem do menor peso primeiro. . . . . . . . . . . . . . . . . . . . . . . . . . Lista de Tabelas 3.1 Execução do Algoritmo 3.2. . . . . . . . . . . . . . . . . . . . . . . . 3.2 Tamanho médio dos conjuntos de ramificação gerados por cada heurística, por densidade, para instâncias com 200 vértices. . . . . . 3.3 Tamanho médio dos conjuntos de ramificação gerados por cada heurística, por densidade, para instâncias com 300 vértices. . . . . . 4.1 Procedimentos de limite inferior . . . . . . . . . . . . . . . . . . . . . 4.2 Procedimentos de limite superior . . . . . . . . . . . . . . . . . . . . 4.3 Média dos número de subproblemas para 10 instâncias de grafos aleatórios para cada par (n, p).. . . . . . . . . . . . . . . . . . . . . . 4.4 Média dos tempo de execução para 10 instâncias de grafos aleatórios para cada par (n, p). . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Resultados computacionais com as instâncias DIMACS-W . . . . . . 4.6 Instâncias do problema de clique máxima ponderada obtidas a partir das instâncias de conjunto independente máximo ponderado . . . . . 4.7 Melhor limite inferior encontrado para cada instância Exactcolor . . . 4.8 Tempo de Execução para cada instância Exactcolor . . . . . . . . . . 5.1 Média dos números de subproblemas para grafos aleatórios gerados por par (n, p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Média dos tempos de execução para os grafos aleatórios gerados por par (n, p) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Números de subproblemas gerados para as instâncias DIMACS-W . . 5.4 Tempos de execução para as instâncias DIMACS-W . . . . . . . . . . 5.5 Números de subproblemas para cada instância EXACTCOLOR . . . . . . 5.6 Tempos de execução para cada instância EXACTCOLOR . . . . . . . . .

  . . . . . . . . . . . 6.12 Número médio de colorações ponderadas realizadas pelo algoritmo nas instâncias DIMACS-W. . . . . . . . . . . . . . . . . . . . . . . . 6.13 Tempo de execução dos algoritmos nas instâncias DIMACS-W. . . . . 6.14 Número de colorações ponderadas para cada instância EXACTCOLOR155 6.15 Tempo de execução dos algoritmos para cada instância EXACTCOLOR.156 A.1 Densidade mínima, máxima e média das instâncias do problema de detecção de cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Tempo para enumerar todas as cliques violadas para todas as instâncias de cada grupo [Boas, Santos e Brito 2015] . . . . . . . . . A.3 Tempo para enumerar todas as cliques violadas para todas as instâncias de cada grupo . . . . . . . . . . . . . . . . . . . . . . . . . A.4 Tempo para enumerar todas as cliques violadas para todas as instâncias de cada grupo . . . . . . . . . . . . . . . . . . . . . . . . . A.5 Resultados computacionais para instâncias MIPLIB . . . . . . . . . . A.2 Algoritmo BKA [Brito e Santos 2011] . . . . . . . . . . . . . . . . . A.3 Algoritmo BITBKC . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.4 Algoritmo BITBKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.5 Algoritmo BKA M AX . . . . . . . . . . . . . . . . . . . . . . . . . . .

  Figura 2.1: A relação entre a clique máxima, conjunto independente máximo e cobertura mínima de vértices. O grafo da direita, denotado por G, é o complemento do grafo da esquerda denotado por G. O conjunto de vértices {4,5,6} define a clique máxima de G e o conjunto independente máximo de G. O conjunto de vértices {1,2,3} representa a cobertura mínima de G.

  Figura 2.2: Relação entre o problema CLIQUE e CLIQUE PONDERADA: o conjunto de vértices {4,5,6} é uma clique máxima de G , mas não é a clique máxima de ponderada de G , que é definida por {1,2}.

  cujos elementos são denominados arcos. Diferentes das arestas, os arcos são pares ordenados. Para cada arco (u, v), dizemos que u é a extremidade inicial e que v é a extremidade final; dizemos ainda que v é um vizinho positivo de u e que u é um vizinho negativo de v. Para cada vértice v, os conjuntos N + (v),N -(v) são, respectivamente, a vizinhança positiva de v, definida como {u : (v, u) ∈ A}, e a vizinhança negativa, definida como {u : (u, v) ∈ A}. Um passeio orientado em um grafo direcionado é uma sequência finita de vértices (v 1 , v 2 , . . . , v k ) tal que existe um arco (v i , v i+1 ) para todo i = 1, . . . , k -1. Se não houver repetição de vértices , o passeio é um caminho orientado. Se apenas o primeiro e o último vértices são iguais, o passeio é um ciclo orientado. Um grafo direcionado que não possui ciclos orientados é um grafo direcionado acíclico. Um grafo direcionado ponderado, denotado por (V, A, w), é composto por um grafo direcionado -→ G e uma função de ponderação w : V → R + . O peso de um caminho direcionado P em -→ G é dado pela soma dos pesos de todos os vértices de P . Dados um grafo G = (V, E) e uma sequência dos vértices ρ = [ρ 1 , . . . , ρ |V | ], o

  Figura 2.4: Coloração ponderada trivial: o peso da coloração ponderada trivial de G é 13. A clique máxima ponderada de G é 6.

  Uma coloração ponderada pode ser entendida como uma solução viável para o dual da formulação por conjunto independentes. Uma solução viável pode ser obtida de diversas maneiras. Para facilitar a referência atribuímos uma denominação diferente à cada coloração ponderada, de acordo com a forma usada para obter a solução viável correspondente. A seguir, apresentamos os seguintes tipos de coloração ponderada utilizadas para gerar limites superiores para CLIQUE PONDERADA: Coloração Ponderada Trivial. Coloração Ponderada Particionada.

  2007] utiliza uma versão fracionária da coloração particionada para obter limites superiores em seu algoritmo de Resolution Branch & Bound. [Kumlander 2008] usa uma coloração ponderada particionada em seu algoritmo de Branch & Bound para CLIQUE PONDERADA. O autor usa a ordem decrescente de pesos dos vértices para definir a sequência dos vértices ρ. Essa coloração ponderada inteira é realizada uma única vez no nó raiz do Branch & Bound e utilizada para determinar os limites superiores em cada nó da árvore de Branch & Bound.

  Figura 3.5: Grafo Ponderado

S

  é reduzido pelo peso do conjunto independente S. Quando o peso residual de um vértice v torna-se zero, o vértice é adicionado à sequência π, color[v] recebe a soma dos pesos dos conjuntos independentes gerados até o momento e o vértice v é removido do processo de coloração. Note que color[π[j]] representa o peso da coloração ponderada do subgrafo G[π[1], . . . , π[j]]. O processo continua enquanto existir vértice com peso residual maior do que zero.

  min{res(v) : v ∈ S i } 11: y(S i ) ← min res 12: U B ← U B + min res 13: Para u ∈ S i faça 14: res(v) ← res(v) -y(S i ) 15:

  Comparamos o desempenho computacional da Heurística de Yamaguchi & Masuda (denotada por YM), Heurística de Held et al (denotada por HCS) e a Heurística de Coloração Ponderada com paralelismo de bits com as ordens iniciais menor peso primeiro (denotada por BITCOLOR1)e maior grau ponderado primeiro (denotada por BITCOLOR1). O código da Heurística YM foi disponibilizado gentilmente pelos autores. Os demais códigos são implementações próprias. Vale lembrar que tanto a YM quanto HCS não utilizam uma ordenação inicial dos vértices. Os testes computacionais foram conduzidos num computador com processador Intel Core i7-2600K 3.40 Ghz, com 16Gb de memória, utilizando o sistema operacional Linux. Avaliamos o desempenho das heurísticas utilizando instâncias aleatórias. Para cada combinação n (número de vértices) e p (probabilidade de existência de aresta), 10 grafos aleatórios foram gerados. Como é usual na literatura, os pesos dos vértices são distribuídos uniformemente entre 1 e 10. No total, consideramos 22 combinações (n, p), levando a 220 instâncias no total. Para cada (n, p), calculamos a média do tempo consumido e a média do limite superior obtidos pelas 10 instâncias para cada heurística. As Figuras 3.6 e 3.7 apresentam uma comparação entre as médias dos limites superiores das quatros heurísticas para instâncias com 200 e 300 vértices, respectivamente. A comparação tem por base a Heurística YM. Assim, para cada grupo de 10 instâncias, calculamos a razão entre a média de cada heurística e a média de YM. Os resultados revelam que BITCOLOR1 e BITCOLOR2 obtém os melhores limites superiores em média em todas as instâncias geradas. Os valores dos limites superiores calculados podem ser consultados no Apêndice A.

Figura 3. 6 :

 6 Figura 3.6: Razão entre a média dos limites superiores de cada heurística e a média do limite superior de YM, por densidade, para instâncias com 200 vértices

Figura 3. 8 :

 8 Figura 3.8: Razão entre a média dos tempos de execução de cada heurística e a média do tempo de execução de HCS, por densidade, para instâncias com 200 vértices

4. 1

 1 Estrutura geral para CLIQUE PONDERADA Apesar de sua simplicidade, o algoritmo apresentado em [Carraghan e Pardalos 1990, Carraghan e Pardalos 1990] mostra a estrutura geral utilizada pela maioria dos algoritmos de Branch & Bound para CLIQUE PONDERADA propostos na literatura. A partir dele, podemos destacar os elementos chaves que impactam no desempenho de um procedimento utilizando essa estrutura, que pode ser vista no Algoritmo 4.1. Basicamente, ele enumera as cliques de G seguindo a estratégia descrita na Seção 3.6. Nesse algoritmo há uma chamada recursiva à função CLIQUE, responsável por gerar todos os subproblemas da árvore de Branch & Bound. Cada subproblema é definido pela tripla (C, P, LB), onde LB é um limite inferior para o problema, dado pela clique com o maior peso encontrada até o momento, C = {v 1 , . . . , v d } (onde d é a profundidade do subproblema) é a clique atual e P é o conjunto de vértices que podem entrar na clique atual , ou seja, P ⊆ ∩ d i=1 N (v i ), chamado de conjunto candidato. Seja U B(P ) um limite superior para a clique ponderada mais pesada de G[P ]. Para um subproblema (C, P, LB), se w(C) + U B(P ) > LB, então toda clique C ⊆ (C ∪ P ) tal que w(C ) ≥ LB deve possuir pelo menos um vértice de P . Usando algum critério, um vértice v de P é selecionado, para ser adicionado à clique atual. Quando o vértice v é adicionado, dizemos que o vértice v foi ramificado. Depois que todas as cliques contendo C ∪ {v} são enumeradas implicitamente pela chamada recursiva CLIQU E(C ∪ {v}, P ∩ N (v), LB), o vértice v é removido do conjunto P . Em cada subproblema, pode-se determinar um conjunto U ⊆ P tal que U B(U ) ≤ LB -w(C), de modo que os vértices em U não precisam ser ramificados. Em outras palavras, apenas os vértices de P \ U são ramificados em uma ordem definida pela estratégia de ramificação. Esse esquema de ramificação foi apresentado primeiramente em [Balas e Yu 1986]. No algoritmo Branch & Bound podemos destacar quatro pontos chaves, que estão destacados nas de caixas: i. Procedimento de limite inferior.

  ∪ {v}, P ∩ N (v) , LB) 12: P ← P \ {v} A seguir, apresentamos sucintamente como esses quatro pontos são tratados nos principais algoritmos de Branch & Bound da literatura. Ressaltamos que a efetividade desses procedimentos no processo global pode não ser a mesma quando observamos cada ponto separadamente. Por exemplo, o procedimento que gera o melhor limite superior pode não ser o mais efetivo para a estratégia de ramificação escolhida.O primeiro ponto chave, destacado no Algoritmo 4.1, está relacionado com a obtenção de um limite inferior de qualidade. Aqui há que se procurar um equilíbrio entre a qualidade do limite, que impacta no tamanho da árvore de busca, com o tempo para calculá-lo. Várias opções têm sido propostas na literatura.Há também que se decidir se o limite inferior será calculado no nó raiz (Linha 2) e atualizado quando uma solução for encontrada (Linha 6), ou se vamos tentar melhorar o limite inferior corrente a cada nó da árvore.Para o problema da clique máxima, onde todos pesos são iguais, uma heurística de busca local eficiente foi utilizada em[START_REF] Maslov | Speeding up branch and bound algorithms for solving the maximum clique problem[END_REF]] para a obtenção de uma solução de alta qualidade apenas no nó raiz. Sua utilização mostrou-se bastante efetiva em instâncias difíceis da DIMACS.Para o problema com pesos, destacamos os limites inferiores apresentados por[Balas e Xue 1996],[START_REF] Babel | A fast algorithm for the maximum weight clique problem[END_REF]],[START_REF] Warren E Hicks | [END_REF] e[START_REF] Held | Maximum-weight stable sets and safe lower bounds for graph coloring[END_REF]].

  Diferente das referências anteriores, que usam coloração ponderada, em [Yamaguchi e Masuda 2008], o limite superior é determinado a partir de uma orientação acíclica dos vértices de G. Os autores apresentam um algoritmo polinomial para encontrar um sequência dos vértices ,que é utilizada para definir o grafo direcionado acíclico -→ G π . O limite superior é dado pelo caminho com o maior peso em -→ G π . Em [Held, Cook e Sewell 2012] e [Tavares et al. 2015], as heurísticas de coloração ponderada apresentadas no Capítulo 2 são utilizadas como procedimento de limite superior. Masuda 2008] Tamanho do maior caminho no grafo direcionado pela sequencia Π HCS [Held, Cook e Sewell 2012] Heurística de coloração ponderada inteira TCRM [Tavares et al. 2015] Heurística de coloração ponderada inteira seguindo uma ordem inicial ρ O terceiro ponto chave v ← Selecione um vértice de P está relacionado com a estratégia de ramificação. A ordem em que os vértices são ramificados determina os subproblemas a serem avaliados (em outros termos, os subgrafos pesquisados) e o seu potencial para gerarem limites favoráveis à poda. Em alguns algoritmos, uma única ordem de ramificação é usada em todos os subproblemas desde a raiz. Em outros, a cada nó da árvore, uma nova ordem de ramificação dos vértices candidatos é determinada. Tais ordens podem seguir um critério estático ou dinâmico. Observe que a ordem de ramificação pode ser definida antes de sabermos exatamente que são os vértices que devem ser ramificados. Nesse caso, o conjunto de ramificação é encontrado à medida que os vértices são ramificados e o conjunto candidato resultante ainda consiga superar a melhor clique conhecida. Em outros algoritmos, um procedimento é utilizado para encontrar o conjunto de ramificação previamente.

  Os vértices são ramificados em ordem decrescente do valor de color enquanto ainda for possível superar a melhor clique conhecida. Também neste caso o conjunto de ramificação é determinado ao longo do processo. Em [Balas e Xue 1991, Balas e Xue 1996], um procedimento é utilizada para definir o conjunto de ramificação F . Os vértices de F são ramificados em uma ordem arbitrária. Vale salientar aqui que enquanto em [Carraghan e Pardalos 1990], o foco é reduzir o conjunto de ramificação, em [Babel 1994, Balas e Xue 1991, Balas e Xue 1996], o foco é reduzir limite superior, ou seja, na capacidade de poda. A maior parte dos algoritmos falham em não conciliar esses dois objetivos.

  Os vértices são ramificados em ordem decrescente do peso da coloração ponderada. Embora a estratégia seja similar a de Babel, a coloração ponderada usada aqui é diferente.Na maior parte dos algoritmos analisados, o conjunto de ramificação não é definido previamente. A principal vantagem dessa abordagem é que a melhoria do limite inferior pode contribuir para a redução do conjunto de ramificação. No caso dos algoritmo de [Balas e Xue 1991], [Balas e Xue 1996] e [Held, Cook e Sewell 2012], o conjunto de ramificação é definido previamente. No caso do algoritmo proposto em [Held, Cook e Sewell 2012], a situação é atenuada pelo fato de que diferentes regras para gerar o conjunto de ramificação são utilizadas. O quarto ponto chave P ∩ N (v) está relacionado com a estrutura de dados que armazena o grafo e com a eficiência em que operações são realizadas sobre G durante o algoritmo. Mais recentemente, a utilização de estrutura de dados que armazena bits individualmente (vetores de bits) começou a ser explorada [Segundo, Rodriguez-Losada e Jiménez 2011, Segundo et al. 2013, Corrêa et al. 2014] para CLIQUE. A utilização dos vetores de bits possibilita a redução dos requisitos de memória e uma melhor aproveitamento do paralelismo das operações bit-a-bit realizadas pelo hardware. A utilização dessa estrutura de dados para CLIQUE PONDERADA é proposta nesta tese. 4.2 Algoritmos do Estado da Arte Dentre os métodos do estado da arte para o problema CLIQUE PONDERADA, podemos destacar o algoritmo CLIQUER baseado no método das bonecas russas que será apresentado no próximo capítulo, e os seguintes 2 algoritmos de B & B: Algoritmo YM: Yamaguchi e Masuda apresentaram um algoritmo de Branch & Bound em [Yamaguchi e Masuda 2008]. Neste algoritmo, uma heurística é utilizada para encontrar uma orientação acíclica do grafo objetivando minimizar o peso do caminho mais pesado no grafo orientado. O algoritmo YM supera o algoritmo CLIQUER para grafos aleatórios com densidade superior 50%. Algoritmo HCS: Held, Cook e Sewell apresentaram um algoritmo de Branch & Bound melhorado para o problema do conjunto independente ponderado máximo em [Held, Cook e Sewell 2012]. O algoritmo utiliza duas estratégias de poda e três estratégias de ramificação. No trabalho, o algoritmo é comparado com o algoritmo CLIQUER e com dois algoritmos de Branch & Cut que usam o CPLEX 12.2 e Gurobi 3.0.0, respectivamente. O algoritmo CLIQUER mostrou-se mais eficiente para grafos com densidade inferior 50%. Por outro lado, os algoritmos de Branch & Cut mostraram-se mais eficientes para grafos com densidade maior que 97%. O algoritmo HCS mostrou-se mais eficientes para as faixas intermediárias de densidade entre 50% e 97%. 4.2.1 Algoritmo de Yamaguchi e Masuda O algoritmo YM segue a estrutura geral do Algoritmo 4.1. Um subproblema é definido pela tripla (C, P, LB). Em cada nó, aplica-se a heurística que devolve uma ordem dos vértices π 1 , . . . , π n tal que (π 1 ) ≤ (π 2 ) ≤ . . . < (π n ), onde (π i ) representa o tamanho do maior caminho direcionado no subgrafo -→ G π [π 1 , . . . , π i ]. O primeiro vértice escolhido para ser ramificado é π n , se a(π n ) > LB -w(C). Então, todas as cliques contendo o vértice π n são enumeradas implicitamente. O vértice π n é removido de P e o processo continua enquanto (π k ) > LB -w(C) para k = n -1, . . . , 1. Esses passos podem ser vistos no Algoritmo 4.2. Algoritmo 4.2 Algoritmo proposto por Yamaguchi e Masuda função MAIN LB

  4.2.2 Algoritmo de Held, Cook e Sewell O algoritmo de Branch & Bound apresentado por Held, Cook e Sewell, que denotaremos por HCS, resolve o problema do conjunto independente máximo ponderado. Esse algoritmo adota várias idéias dos algoritmos apresentados em [Balas e Xue 1996, Babel 1994, Warren e Hicks 2006, Sewell 1998, Bron e Kerbosch 1973]. Como o problema da clique máxima ponderada de G pode ser resolvido encontrando o conjunto independente máximo no grafo G, vamos descrever o algoritmo no contexto de clique máxima ponderada. Um subproblema na árvore de Branch & Bound gerado por HCS é definido pela quádrupla (C, P, X, LB), onde LB é um limite inferior, dado pela clique com o maior peso até o momento, C = {v 1 , . . . , v d } (onde d é a profundidade do subproblema) é a clique ponderada atual, P é o conjunto de vértices que podem entrar na clique atual chamado de conjunto candidato e X é o conjunto de vértices que já explorados em algum subproblema antecessor, ou seja, o peso de qualquer clique ponderada contendo um vértice de X é no máximo LB.

  da regra de ramificação proposta por Balas e Yu [Balas e Yu 1986]. Dado um subproblema (C, P, X, LB), suponha que exista um U ⊆ P tal que ω(G[U ], w) ≤ LB -w(C) Então toda clique C ⊆ C ∪ P com w(C ) > LB deve conter pelo menos um vértice de P \ U . O conjunto de ramificação é reduzido para F = P \ U . A determinação do conjunto F assim como a verificação da segunda regra de poda são feitas conjuntamente por uma modificação da HeurísticaHCS (Ver Algoritmo 3.2). A versão modificada, que denotamos por HeurísticaHCSRestrita, termina quando todos os vértices estiverem totalmente coloridos (como antes) ou quando o peso da coloração atingir LB -w(C), o que ocorrer primeiro. No primeiro caso, a segunda regra de poda é satisfeita. No segundo caso, os vértices não coloridos ou parcialmente coloridos definem F . A segunda regra de ramificação utiliza o conjunto de vértices X. Podemos notar que toda clique ponderada máxima C em G[C ∪ F ] com w(C ) > LB deve conter pelo menos um vértice da não vizinhos de x ∈ X, um contradição, pois toda clique contendo x tem peso no máximo LB. Neste caso, podemos tomar o conjunto de ramificação como F = P ∩ N (x). A terceira regra de ramificação pode ser definida se existe um v ∈ P tal que w(v) ≥ w(P ∩ N (v)) Podemos mostrar que existe uma clique ponderada máximo C de G[P ] que inclui o vértice v. Lema 4 Dado um subproblema (C, P, X, LB). Se existe um v ∈ P tal que w(v) ≥ w(P ∩ N (v)) então existe uma clique ponderada máxima C de G[P ] que inclui o vértice v. Prova Suponha que existe uma clique ponderada máxima C de G[P ] que não inclui o vértice v. Seja C = {v} ∪ (C \ N (v)) uma clique ponderada de G[P ] que inclui o vértice v. Vamos mostrar que w(C ) ≥ w(C ). De fato, temos as seguintes relações são válidas:

  Se ∃x ∈ X tal que w(x) ≥ w((C ∪ P ) ∩ N (x)) então 13: retorne 14: HeurísticaHCSRestrita(G[P ], π, color, tamanho) 15: Todos os vértices são coloridos pela heurística de coloração ponderada 16: Se tamanho = |P | então 17: returne 18:

  19:Ordene F em ordem decrescente de seus graus em G[P ] 20: Para i ← p até 1 faça 21:

  4.3.1 Procedimento de Limite Inferior Diversas heurísticas disponíveis são capazes de encontrar boas soluções viáveis para o problema da CLIQUE PONDERADA: Algoritmo aumentante [Mannino e Stefanutti 1999] Busca Local Escalonada (Phased Local Search) [Pullan 2008] Busca Tabu com Multivizinhaça [Wu, Hao e Glover 2012] Busca Local de Fuga (Breakout Local Search) [Benlic e Hao 2013] A heurística escolhida para obter uma boa solução inicial foi a Busca Tabu com Multivizinhança [Wu, Hao e Glover 2012] (Ver Algoritmo 4.4). Em cada iteração, nessa metaheurística, é explorada a união de 3 vizinhanças, e a melhor solução admissível da vizinhança (não proibida ou melhor global) é escolhida. Inicialmente, uma solução inicial é construída de forma iterativa, a partir de um conjunto vazio e adicionando um vértice por vez, sem um critério específico, até encontrar uma clique maximal. Os operadores de movimento, que definem respectivamente as 3 vizinhanças, são ADD, SWAP e DROP. Esses operadores são definidos em função de dois subconjuntos de vértices P A e OM , relacionados com uma clique C. O subconjunto de vértices P A é formado pelos vértices que não estão em C, mas são adjacentes a todos os vértices de C. O subconjunto de vértices OM é formado pelos vértices que não estão em C, mas têm |C| -1 vizinhos em C. A relação entre a clique C e os conjuntos de vértices P A e OM estão ilustradas na Figura 4.1, extraída do artigo [Wu, Hao e Glover 2012]. O operador ADD(v) adiciona um vértice v de P A na clique atual C. Esse movimento só pode ser aplicado quando P A = ∅. Depois do movimento ADD(v), o peso da clique ponderada atual aumenta em w(v). O operador DROP (u) remove um vértice da clique atual C. Esse movimento só pode ser aplicado quando C = ∅.

Figura 4. 1 :

 1 Figura 4.1: Relação entre uma clique C e os subconjuntos de vértices P A e OM . Fonte: [Wu, Hao e Glover 2012]

  Yates e Gonnet 1992]. Recentemente, o paralelismo de bits tem sido explorado para resolver problemas de otimização combinatória como SAT [Segundo et al. 2008], Clique Máxima [Segundo et al. 2010, Segundo, Rodriguez-Losada e Jiménez 2011,Segundo et al. 2013,Segundo e Tapia 2014,Segundo, Nikolaev e Batsyn 2015] e Coloração de Vértices [Komosko et al. 2015].

  Nós comparamos o desempenho computacional do nosso algoritmo BITCLIQUE com o algoritmo Branch & Bound de Yamaguchi e Masuda (YM), disponibilizado gentilmente pelos os autores, e com algoritmo de Branch & Bound proposto em [Held, Cook e Sewell 2012], disponibilizado em https://code.google.com/p/ exactcolors/. Consideramos duas versões do nosso algoritmo: BITCLIQUE1, que usa a ordenação inicial dada pelo menor peso primeiro; BITCLIQUE2 onde a ordem inicial considera o critério do maior grau ponderado primeiro. Todos os testes foram realizados num computador com processador Intel Core i7-2600K 3.40Ghz, 8 Mb de cache, com 6Gb de memória, utilizando o sistema operacional Linux. Nós avaliaremos o desempenho do nosso algoritmo utilizando as principais instâncias disponíveis na literatura: Grafos Aleatórios DIMACS-W ExactColor 4.4.1 Grafos Aleatórios Em nosso experimento, nós geramos 10 grafos aleatórios para cada combinação n (número de vértices) e p (probabilidade de existência de cada aresta) considerada. Nós estamos usando o modelo de grafos aleatórios G(n, p). Neste modelo, o grafo é construído adicionando arestas aleatoriamente. Cada aresta é incluída no grafo com probabilidade p, independentemente de todas as outras arestas. Logo, todos os grafos com n vértices e m arestas têm a mesma probabilidade de serem gerados definida por p m (1 -p)

  4.4.2 DIMACS-W O conjunto de instâncias da DIMACS foi criada para o Segundo Desafio em Cliques, Satisfabilidade e Coloração de Grafos. Ele é formado por 80 grafos obtidos a partir de vários problemas: brock : instâncias do gerador de Mark Brockington e Joe Culberson que tenta esconder uma clique com um tamanho maior do que o esperado pelo modelo clássico de grafos aleatórios.p hat: instâncias construídas por um gerador que usa 3 parâmetros: n, número de nós, e a e b, dois parâmetros de probabilidade de existência de arestas tal que 0 ≤ a ≤ b ≤ 1, gerando grafos com cliques maiores do que o esperado pelo modelo clássico de grafos aleatórios. hamming: instâncias de problemas de Teoria de Códigos. san e sanr : instâncias obtidas a partir do problema de cobertura de vértices mínima. MANN : instâncias obtidas da formulação do problema da cobertura tripla de Steiner O conjunto de instâncias DIMACS-W são instâncias obtidas a partir das instâncias DIMACS para o problema da clique máxima. Várias heurísticas utilizam as instâncias da DIMACS-W como instâncias de referência. Há diversas maneiras de definir uma função de ponderação dos vértices. Vamos adotar a função de ponderação descrita em [Pullan 2008]: para cada vértice i, w i é igual a (i mod 200)+ 1. Os resultados dos experimentos computacionais com as instâncias desse grupo podem ser vistos na Tabela 4.5. Agora, o tempo limite de resolução para cada instância é 2h (7200s). Quando o tempo limite é ultrapassado, tal ocorrência é assinalada como * na tabela. Identificamos em negrito o melhor desempenho em cada caso. Podemos observar novamente que BITCLIQUE1 gera sempre menos subproblemas que YM e HCS. O mesmo ocorre com BITCLIQUE2, com exceção das instâncias hamming10-2, que esse algoritmo não consegue resolver, e san400 0.7 1, onde o número de subproblemas é superior ao de HCS. Por outro lado, não há prevalência clara de BITCLIQUE1 sobre BITCLIQUE2 ou vice-versa, a não ser para instâncias com densidade a partir de 0.90, quando o segundo gera menos subproblemas que o primeiro. Em relação a tempo, o algoritmo BITCLIQUE1 é mais rápido que o algoritmo BITCLIQUE2 para instâncias com densidade menor que 0.90 (com exceção dos grafos da família p hat). Além disso, o algoritmo BITCLIQUE1 resolve todas as instâncias resolvidas pelos algoritmos anteriores enquanto BITCLIQUE2 não consegue resolver a instância hamming10-2, que é resolvida por HCS. Note ainda que os novos algoritmos são quase sempre mais rápidos que os da literatura. Há reduções bastante significativas, como no caso das instâncias phat 1000-2 e phat 1500-2. Notamos também que os novos algoritmos conseguiram resolver mais instâncias dentro do tempo limite estabelecido. 4.4.3 Exactcolor Essas instâncias representam subproblemas de conjunto independente máximo ponderado, obtidos durante o algoritmo de Branch & Price para o problema de coloração de vértices [Held, Cook e Sewell 2012]. Seja S o conjunto de todos os conjuntos independentes em G. O número cromático de G, denotado por χ(G), pode ser obtido da seguinte maneira:

  satisfaz essa condição se somente se o conjunto independente máximo ponderado por π de G é maior que 1. O valor deste conjunto é dado por:α(G, π) = max v∈V π v y v s.a. y v + y u ≤ 1 ∀{u, v} ∈ E y v ∈ {0, 1} ∀v ∈ V Na literatura,este problema é atacado de maneira exata e/ou heurística utilizando alguns algoritmos de Branch & Bound eficientes para o problema da clique máxima ponderada ou, equivalentemente, conjunto independente máximo ponderado. Em [Held, Cook e Sewell 2012], um conjunto de instâncias do problema α(G, π) é gerado durante o método de geração de colunas. O conjunto completo de instâncias pode ser obtido em: http://code.google.com/p/exactcolors/wiki/MWISInstances Em [Held, Cook e Sewell 2012], um conjunto de 25 instâncias do problema α(G, π) é utilizado como instâncias desafio para o problema do conjunto independente máximo ponderado (Ver Tabela 4.6). Essas instâncias podem ser convertidas para instâncias do problema da clique máxima ponderada no grafo complementar G. A densidade reportada na tabela é do grafo G. Para o algoritmo ser numericamente seguro, os pesos duais são escalonados por um valor K. Na prática, isso significa que queremos encontrar conjuntos independentes com peso maior que K. Nos testes realizados em [Held, Cook e Sewell 2012], para as instâncias grandes como C2000.5.1029, DSJC1000.1.3915 e DSJC500.1.117, a computação é finalizada quando um conjunto independente com peso maior que K é encontrado. O algoritmo apresentado pelos autores não conseguiu encontrar tal conjunto independente para essas instâncias grandes em tempo limite de 10h.

  ], cada boneca é resolvida por um algoritmo de Branch & Bound implementado pela função RDS do Algoritmo 5.1. Um subproblema na árvore de Branch & Bound é definido pela tripla (C, P, LB), onde LB é um limite inferior, dado pelo peso da clique mais pesada encontrada até o momento, C é a clique atual e P é o conjunto de vértices que podem entrar na clique atual chamado de conjunto candidato. Particularmente, o subproblema da raiz da árvore de B & Bassociada à boneca RDS({ρ i }, U ∩ N (ρ i ), W ) é dado por C = {ρ i }, P = U ∩ N (ρ i ) e LB = W .Esse algoritmo Branch & Bound emprega duas regras de poda e uma estratégia de ramificação, baseada na ordem ρ (Ver Algoritmo 5.2).

Figura 5 . 2 :

 52 Figura 5.1: Limites superiores dados pela soma dos pesos dos vértices e pelos valores de c[i] para cada G i , para i = 1, . . . , 4.

  das bonecas segue pois o Algoritmo 5.1, partindo entretanto de outras ordens. Como antecipado, cada boneca é resolvida por um B & B que utiliza a coloração ponderada inteira para definir uma regra de poda e/ou o conjunto de ramificação. A heurística de coloração apresentada no Algoritmo 5.3 usa dois parâmetros: R é um vetor de bits e K é um valor inteiro. O parâmetro R devolve o conjunto de ramificação e é inicializado com P (o conjunto de candidatos). O parâmetro K mantém o peso ainda disponível para a coloração, sendo inicializado com LB -w(C) ( o limite inicial máximo). O Algoritmo 5.3 apresenta um procedimento da heurística de coloração ponderada inteira que contempla essas duas utilizações da coloração ponderada. A cada iteração, um conjunto independente ponderado S i será construído, até se atingir o limite de peso da coloração ou se colorir P completamente. O vetor de bits Q representa os vértices que podem ser adicionados ao conjunto independente ponderado S i atual. Os vértices a serem adicionados a S i são selecionados do vetor de bits Q, seguindo a ordenação inicial dos vértices ρ. Cada vez que um vértice v é selecionado, o conjunto independente S i é atualizado S i ← S i ∪ {v}. Os vértices adjacentes a v e o próprio v são removidos do vetor de bits Q

  Path-Like Uma família de cláusulas F = [C 1 , C 2 , . . . , C m ] e um conjunto de literais W = [w 1 , w 2 , . . . , w m ] têm estrutura especial chamada de path-like se as seguintes propriedades são válidas:

Definição 9

 9 Sejam A e B dois nogoods que conflitam em um único literal w, tal que w ∈ A e w ∈ B. O resolvente de A e B é definida pela seguinte solução parcial: A∇B = (A -w) ∪ (B -w) Proposição 7 Sejam A e B dois nogoods que conflitam em um único literal w, tal que w ∈ A e w ∈ B, então A∇B é um nogood.

  w 1 , . . . , w m ] é uma família path-like. Para i = 1, . . . , m, S conflita com C i se somente se w i ∈ S. Prova Como X(S) ∩ X(U F ) = ∅ e C i -w i ⊆ U F , temos que w ∈ C i -w i , implica que w ∈ S. Logo, se w ∈ C i e w ∈ S então w = w i Pela Proposição 8, todos os conflitos entre o nogood S e algum nogood C i da família path-like F são resolvidos na fase de ResoluçãoNogood formalmente definida pelo Algoritmo 6.4. Algoritmo 6.4 ResoluçãoNogood(F, W, S, R) 1: R ← S 2: Para i ← m até 1 faça Dado que S ⊆ U F , depois de cada execução i do laço do algoritmo 6.4,temos a seguinte propriedade: R ⊆ (U F \ {w i , . . . , w m } (6.6) Ao final do laço, temos:

  Na fase de decrescimento, escolhemos uma variável já fixada para ser liberada de maneira que a solução parcial continue representando um nogood, ou seja, Procure um índice j tal que u + j ∈ {0, 1}, faça u + j = * e verifique se oráculo(U + ) < record.A fase de decrescimento é responsável por encontrar um nogood minimal S tal que S U + . Um nogood S é dito minimal, se somente se não existe um nogood S tal que S S.

  Início da Fase de crescimento 6: bound ← oráculo(U ) 7: Enquanto U ∈ {0, 1} n e bound > record faça 8:Escolha um subscrito j com u j = * e um valor c ∈ {0,1}

Teorema 4

 4 Seja r * o último valor de record obtido pelo Algoritmo de Busca por Resolução. Então oráculo(U ) ≤ r * ∀U ∈ {0, 1} n Prova Considere a lista R 1 , R 2 , . . . , R N de todos os nogoods gerados ao longo do algoritmo, ordenados segundo o momento em que foram gerados. Para todo k

r

  * -nogood, concluímos que oráculo(U ) ≤ r * Corolário 4 O valor de record retornado pelo Algoritmo de Busca por Resolução é o valor ótimo do problema. 6.2 Algoritmo de Busca por Resolução para CLIQUE PONDERADA Nesta seção, apresentamos o nosso algoritmo de Busca por Resolução para CLIQUE PONDERADA. Como visto nas seções anteriores, para a descrição do algoritmo, precisamos definir os procedimentos oráculo e obstáculo, assim como as políticas de mergulho e recomeço. 6.2.1 Oráculo Na implementação clássica do algoritmo de Busca por Resolução, o procedimento oráculo é responsável apenas por prover um limite superior para uma solução parcial U . Ele é utilizado como uma caixa preta. No nosso oráculo, utilizamos a heurística de coloração ponderada para prover um limite superior, assim como a ordem de mergulho. No problema CLIQUE PONDERADA, uma solução parcial é um vetor indexado pelos vértices do grafo G = (V, E). Dado uma solução parcial U , definimos os conjuntos C, que contém uma clique maximal em {j ∈ V |u j = 1}, e P , formado pelos vértices que podem estender a clique C. Esses conjuntos são usados na descrição do oráculo (Ver Algoritmo 6.11): C é construído iterativamente no Linha 7; P começa com V e é atualizado com a remoção de todo vértice j tal que u j = 0 ou j ∈ v∈C N (v) (Linhas 6 e 11).

A

  ordem ρ influencia a sequência em que os vértices são analisados durante a coloração ponderada. Por outro lado, a heurística de coloração ponderada devolve uma outra ordem π dos vértices de P e o vetor color com o valor das colorações ponderadas dos subgrafos, ou seja, color[π i ] é o valor da coloração ponderada do subgrafo G[π 1 , . . . , π i ].

  Figura 6.1: Grafo ponderado com os vértices ordenados seguindo a ordem do menor peso primeiro.

  6.5: Execução do Algoritmo de Busca de Resolução utilizando o obstáculo modificado.6.2.7 Obstáculo Modificado com fase de decrescimentoPara o nosso obstáculo modificado, podemos ainda definir uma fase de decrescimento simplificada. Para liberar uma fixação s j = 0 tal que j ∈ P , precisamos mostrar que um limite superior para a clique ponderada contendo C∪{j}, que é dado pela soma de w(C ∪{j}) com um limite superior para a clique ponderada de P ∩ N (j), é inferior ou igual a record. A segunda parcela desse limite superior pode ser obtida encontrando o último vértice vizinho de j em P na ordem π dada pela heurística de coloração ponderada. Em outras palavras, o valor que devemos comparar a record éw(C) + w(v) + color[π[u]], onde u = max{k | π[k] ∈ P ∩ N (v)} (6.11) O Algoritmo 6.14 apresenta o procedimento obstáculo_modificado com a fase de decrescimento aqui proposto. Algoritmo 6.14 obstáculo modificado com decrescimento(U, record, S) 1: Inicialize a pilha vazia 2: bound ← oraculo(U ) 3: Se w(C) > record então pilha 14: S ← U 15: Enquanto a pilha não estiver vazia faça 16:

6. 3

 3 BITBR -Cooperação entre Busca por Resolução e Boneca Russas para CLIQUE PONDERADA Nesta seção, apresentamos um algoritmo exato para o problema da CLIQUE PONDERADA, combinando o algoritmo de Busca por Resolução e o Algoritmo de Bonecas Russas. No método das Bonecas Russas, o problema é decomposto em uma sequência de subproblemas aninhados. O método sugere que os subproblemas devam ser resolvidos seqüencialmente, e a sua solução ótima deve ser memorizada para ser utilizada como critério de poda para os futuros subproblemas. Note que uma subsequência inicial de subproblemas resolvidos pelo método das Bonecas Russas representa uma exploração parcial do espaço de busca, que podemos representar como um nogood.

  Nesta subseção, analisamos o desempenho computacional do nosso algoritmo híbrido de Busca por Resolução com Bonecas Russas. Novamente, temos duas versões, definidas pelas ordens iniciais dos vértices. O algoritmo que usa a ordem menor peso primeiro será denotado por BR1, enquanto o que usa a ordem inicial maior grau ponderado primeiro será denotado por BR2.

  atribuídos aos vértices variam entre 1 e 10. Como é usual na literatura, o número de vértices das instâncias diminui à medida que a probabilidade de existência de aresta aumenta. Consideramos 20 combinações, levando a 200 instâncias no total. Para cada par (n, p), calculamos a média do tempo consumido pelas 10 instâncias para cada algoritmo. O tempo de limite de resolução para cada instância é 1h (3600s). Quando o tempo limite é ultrapassado, tal ocorrência é assinalada na tabela como * x , onde x ∈ [1, 10] significa o número de instâncias não resolvidas no tempo limite . Identificamos em negrito o melhor desempenho médio em cada caso. Inicialmente, analisamos o comportamento dos 6 algoritmos propostos até agora, com relação ao número médio de colorações realizadas por cada um. A coloração ponderada é o procedimento com o maior custo computacional realizado por todos os algoritmos. No caso do algoritmo híbrido, contamos o número de colorações ponderadas realizadas na fase de Bonecas Russas e da Busca por Resolução. A Tabela 6.10 mostra que, em praticamente todos os grupos, BR1 e BR2 reduzem o número de colorações ponderadas realizadas com relação à RDS1 e RDS2, respectivamente. Além disso, BR1 consegue executar o menor número de colorações que todos os outros algoritmos em muitas instâncias com densidade entre 30% e 80%.

  Neste apêndice, discutimos o problema da enumeração de cliques com peso acima de um limiar. Em programação inteira, a enumeração de cliques maximais com certo peso está relacionada, por exemplo, com o problema de encontrar todas as desigualdades de clique violadas. O impacto destas desigualdades na resolução de vários problemas de programação inteira vem sendo explorado em diversos trabalhos[Avella e Vasil'Ev 2005, Burke et al. 2012, Santos et al. 2014[START_REF] Brito | [END_REF],Corrêa et al. 2015]. Além disso, em muitas aplicações, é importante não apenas encontrar a clique com o peso máximo ou com a cardinalidade máxima, mas todas as cliques maximais ou ainda um subconjuntos delas.Muitos algoritmos são conhecidos para o problema de enumeração de todas as cliques maximais[START_REF] Akkoyunlu | The enumeration of maximal cliques of large graphs[END_REF], Bron e Kerbosch 1973, Cazals e Karande 2008, Chiba e Nishizeki 1985, Gerhards e Lindenberg 1979, Harary e Ross 1957, Johnston 1976, Makino e Uno 2004, Tomita, Tanaka e Takahashi 2006]. Um dos mais bem sucedidos na prática é o algoritmo de Bron-Kerbosch [Bron e Kerbosch 1973], que identificamos por BK. O algoritmo BK foi adaptado para o problema da enumeração de cliques maximais acima de um limiar em [Brito e Santos 2011, Boas, Santos e Brito 2015] e aplicado com sucesso em problemas de programação inteira em [Santos et al. 2014, Brito, Santos e Poggi 2015]. Na Subseção A, apresentamos o algoritmo BK com uma regra de pivoteamento. Na Subseção B, apresentamos algumas adaptações do algoritmo BK para o problema de enumeração de cliques maximais com peso acima de um limiar. Na Subseção C, usamos esses algoritmos adaptados para resolver o problema CLIQUE PONDERADA e os comparamos computacionalmente com os outros algoritmos propostos ao longo deste trabalho. A Algoritmo de Bron-Kerbosch BK é um algoritmo simples de backtracking que resolve recursivamente subproblemas definidos pela tripla (C, P, X), onde C é uma clique atual, P é o conjunto dos vértices que ainda podem entrar na clique atual, chamado de conjunto candidato e X é o conjunto dos vértices que já foram explorados em algum subproblema anterior e que poderiam entrar na clique não-maximal C. Em outras palavras, P ∪ X é uma partição da vizinhança comum dos vértices em C. Bron e Kerbosch também introduziram uma variante do algoritmo que envolve a escolha de um vértice pivô u. Eles observaram que qualquer clique maximal deve incluir o vértice u ou um dos vértices não adjacentes a ele, pois, caso contrário, a clique não seria maximal. Nessa variação de BK, temos uma regra de pivoteamento responsável por selecionar o vértice pivô. Em [Tomita, Tanaka e Takahashi 2006], os autores sugerem escolher o pivô u ∈ P ∪ X a fim de maximizar |P ∩ N (u)|, ou seja, o pivô é o vértice da vizinhança comum de C com o maior número de vizinhos no conjunto de candidatos. Com isso, garantem que o algoritmo de Bron-Kerbosch executa com uma complexidade de tempo no pior caso O(3 n 3 ). Apesar de sua complexidade exponencial, o algoritmo tem se mostrado extremamente rápido na prática. O Algoritmo A.1 apresenta o algoritmo de Bron-Kerbosck com a regra de pivoteamento proposta em [Tomita, Tanaka e Takahashi 2006]. O processo de enumeração de cliques maximais de um grafo G começa com a seguinte chamada BK(∅, V (G), ∅). Note que a regra de pivoteamento proposta em [Tomita, Tanaka e Takahashi 2006] acelera o processo de descoberta de cliques maximais com uma grande cardinalidade. Algoritmo A.1 Algoritmo BK com a regra de pivoteamento 1: função BK(C, P , X) Escolha um vértice pivô u ∈ P ∪ X Em [Tomita, Tanaka e Takahashi 2006], os autores sugerem escolher o vértice u ∈ (P ∪X) que maximiza |P ∩N (u)| 5: Para v ∈ P \ N (u) faça 6: BK(C ∪ {v}, P ∩ N (v), X ∩ N (v))

  Se w(C) + w(P ) ≥ limiar então 6:

  ∪ {v}, P ∩ N (v), X ∩ N (v)) , Santos e Brito 2015], uma versão melhorada do algoritmo BKA é apresentada. Além disso, testes computacionais foram conduzidos utilizando 7292 instâncias oriundas de quatro conjuntos de instâncias de problemas de programação inteira. O primeiro conjunto, denominado MIPLIB, advém da biblioteca de instâncias MIPLIB2010[Koch et al. 2011], contendo 87 instâncias.

  Para v ∈ P \ N (u) faça ordem não decrescente de grau modificados 12:BITBKC(C ∪ {v}, P ∩ N (v) , X ∩ N (v) )13:P ← P \ {v} 14: X ← X ∪ {v} A Tabela A.3 mostra uma comparação entre os tempos de execução do algoritmo BKA apresentado em [Boas, Santos e Brito 2015], gentilmente cedido pelos autores, e de BITBKC. O algoritmo BITBKC conseguiu uma boa redução no tempo para enumerar todas as cliques maximais violadas. Essa redução reveste-se de maior significado quando relembramos que esse algoritmo é utilizado com uma grande frequência na rotina de separação de cortes. Tempo para enumerar todas as cliques violadas para todas as instâncias de cada grupo Consideramos também uma segunda variante do algoritmo BK, denominada BITBKA (Ver Algoritmo A.4), que utiliza o mesmo critério de poda e a mesma estratégia de escolha do pivô que BKA, ou seja, a estimativa da clique ponderada máxima de P é dada por w(P ) e o pivô é o vértice com o maior grau modificado e maior peso. A diferença aqui é que utilizamos vetores de bits (bitmap) para representar os conjuntos P e X. O grau modificado é calculado, uma única vez, antes do procedimento BITBKA. O pivô é dado pelo último vértice do conjunto P .

  Se w(C) + w(P ) ≥ limiar então 9:Escolha o último vértice u de P 10:Para v ∈ P \ N (u) faça 11:

Tabela A. 4 :

 4 Tempo para enumerar todas as cliques violadas para todas as instâncias de cada grupo C Adaptação para o problema da clique máxima ponderada Apesar de o problema de enumeração de todas as cliques com peso a partir de um certo limiar e o problema da clique máxima ponderada serem problemas diferentes, podemos adaptar facilmente um algoritmo que resolve uma instância do primeiro para resolver uma do segundo. Basta modificar o valor do limiar toda vez que uma nova clique ponderada for encontrada (Linha 4 Algoritmo A.5). Outra modificação possível é enumerar apenas as cliques com limite superior estritamente acima do limiar estabelecido (Linha 5 Algoritmo A.5).Algoritmo A.5 Algoritmo BKA M AX 1: função BKA M AX (C, P , X, limiar)Para v ∈ P \ N (u) faça 8: BKA M AX (C ∪ {v}, P ∩ N (v), X ∩ N (v))9:P ← P \ {v} 10: X ← X ∪ {v}Aqui, nós comparamos o desempenho computacional do nosso algoritmo BITRDS1 com a modificação dos seguintes algoritmos para resolver CLIQUE PONDERADA : Algoritmo BKA apresentado em [Boas, Santos e Brito 2015], agora denominado BKA M AX . Algoritmo BITBKA(Ver Algoritmo A.4), agora denominado BITBKA M AX . Novamente, utilizamos todas as 7292 instâncias para a realização dos testes computacionis. Agora, realizamos uma análise mais acurada do tempo de execução dos algoritmos. Separamos as instâncias em três faixas de densidades: densidade < 0.1, 0.1 ≤ densidade ≤ 0.5 e densidade > 0.5. A Tabela A.5 apresenta os resultados das instâncias MIPLIB. BITBKA M AX teve o melhor desempenho nas instâncias com baixa densidade e para as demais densidades, BITCLIQUE1 foi superior ou teve um desempenho comparável com BITKBA M AX . Note que todas as instâncias INRC estão na primeira faixa de densidade (Ver Tabela A.6). Novamente, BITBKA M AX superou os demais algoritmos. Já as instâncias Telebus concentram-se apenas nas duas primeiras faixas(Ver Tabela A.7). BITBKA M AX encontrou a clique máxima mais rapidamente na primeira faixa de densidade. Na segunda faixa, podemos considerar que os três algoritmos tem um comportamento comparável, embora exista uma ligeira vantagem de BKA M AX e BITBKA M AX .

  

  

  Problema de enumeração de cliques maximais com peso acima de um limiar A Algoritmo de Bron-Kerbosch . . . . . . . . . . . . . . . . . . . B Enumeração de cliques maximais com peso acima de um limiar C Adaptação para o problema da clique máxima ponderada . . . D Testes com Grafos Aleatórios . . . . . . . . . . . . . . . . . . Relação entre clique máxima, conjunto independente máximo e cobertura mínima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Relação entre clique máxima e clique ponderada máxima . . . . . . . 2.3 Grafo ponderado direcionado -→ G ρ . . . . . . . . . . . . . . . . . . . . 2.4 Coloração Ponderada Trivial . . . . . . . . . . . . . . . . . . . . . . . 2.5 Coloração Ponderada Particionada . . . . . . . . . . . . . . . . . . . 2.6 Coloração Ponderada Inteira . . . . . . . . . . . . . . . . . . . . . . .

	SUM ÁRIO
	Apêndice A Referências Bibliográficas Lista de Figuras
	2.1
	Lista de Figuras
	Lista de Tabelas
	Lista de Algoritmos

  6.1 Resultados das estratégias de recomeço para a ordem de menor peso primeiro para o Algoritmo de Busca por Resolução usando o Algoritmo 6.12 como obstáculo. . . . . . . . . . . . . . . . . . . . . 6.2 Resultados das estratégias de recomeço para a ordem de maior grau ponderado primeiro para o Algoritmo de Busca por Resolução usando o Algoritmo 6.12 como obstáculo . . . . . . . . . . . . . . . . 6.3 Resultados das estratégias de recomeço para a ordem de menor peso primeiro para o obstáculo modificado . . . . . . . . . . . . . . . . . 6.4 Resultados das estratégias de recomeço para a ordem de maior grau ponderado primeiro. . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Execução do Algoritmo de Busca de Resolução utilizando o obstáculo modificado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Comparação entre os procedimentos obstáculo padrão, modificado e modificado com fase de decrescimento considerando a ordem de menor peso primeiro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.7 Comparação entre os procedimentos obstáculo padrão, modificado e modificado com fase de decrescimento considerando a ordem de menor peso primeiro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.8 Comparação entre o número de chamadas ao oráculo pelo Algoritmo de Busca por Resolução utilizando obstáculo modificado com decrescimento e pelo Algoritmo de Branch & Bound, nas duas ordem testadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.9 Comparação entre o tempo de execução do Algoritmo de Busca por Resolução utilizando obstáculo modificado com decrescimento com o Algoritmo de Branch & Bound, nas duas ordem testadas. . . . . . . . 6.10 Número médio de colorações ponderadas realizadas para cada grupo

(n, p). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.11 Tempo de execução médio para cada grupo (n, p).

  , Gualandi e Malucelli 2012, Held, Cook e Sewell 2012] ou de geração de cortes clique para problemas de otimização combinatória variados [Avella e Vasil'Ev 2005, Burke et al. 2012, Santos et al. 2014,Brito, Santos e Poggi 2015]( Ver Apêndice A ). Essa é uma das motivações principais do nosso trabalho.

Apresentamos nesta tese novos algoritmos para CLIQUE PONDERADA e avaliamos seus desempenhos frente aos algoritmos do estado da arte para o problema No Capítulo 4, apresentamos um algoritmo de Branch & Bound mais eficiente que HCS e YM, que combina também as ideias presentes [Balas e Xue 1991, Balas e Xue 1996,

  Essa estrutura de dados possibilita realizar operações como união e intersecção de conjuntos com menos instruções[Segundo et al. 2010, Segundo, 

	Rodriguez-Losada e Jiménez 2011, Segundo et al. 2013]. Além disso, adotamos
	uma ordem fixa ρ dos vértices, que será utilizada para organizar os bits nos vetores
	de bits e usada para selecionar os vértices durante a heurística de coloração. Por
	isso, nosso algoritmo BITCLIQUE é apresentado em duas versões, que variam
	de acordo com a ordem inicial dos vértices escolhida. Para avaliá-las, realizamos
	extensos experimentos computacionais. Ainda no Capítulo 4, apresentamos uma
	comparação dos resultados computacionais entre os Algoritmos de Branch & Bound,
	aqui proposto e da literatura, tendo como base os principais conjuntos de instâncias
	disponíveis na literatura.

Através

de testes computacionais, mostramos que o nosso procedimento de limite superior, denominado BITCOLOR, apresenta o melhor compromisso entre a qualidade do limite superior e o tempo gasto para calculá-lo do que seus competidores diretos (YM e HCS). Um dos pontos chaves para a boa eficiência computacional da heurística BITCOLOR encontra-se na forma como são efetuadas as operações sobre o grafo, sobretudo cálculo da vizinhança dos vértices. Em nosso algoritmo, implementamos o grafo e as estruturas relacionadas a ele através de vetores de bits (bitmaps).

No Capítulo 5, apresentamos a estrutura geral do Algoritmo de Bonecas Russas para CLIQUE PONDERADA, proposto por Östergård em

[ Östergård 2002

]. Depois, mostramos nossas intervenções na estrutura geral para incorporar eficientemente a heurística de coloração ponderada como procedimento de limite superior e regra de ramificação. Aqui, utilizamos uma versão modificada da heurística BITCOLOR. Geramos um algoritmo, chamado BITRDS, também apresentado em duas versões. Uma comparação computacional computacional é efetuada entre BITCLIQUE, BITRDS e CLIQUER. No Capítulo 6, apresentamos o método de Busca por Resolução proposto por Chvátal em [Chvátal 1997] para problemas gerais em programação inteira 0-1. Em seguida, apresentamos as nossas adaptações ao método para aplicação à CLIQUE PONDERADA. Uma hibridização entre nossos algoritmos algoritmos de BITRDS e Busca por Resolução é, então, proposta. Testes computacionais são executados e uma comparação entre todos os algoritmos propostos nesta tese é feita. No Capítulo 7, apresentamos uma conclusão revendo as principais contribuições presentes nesta tese. Apontamos também perspectivas para aprimoramentos e extensões do trabalho.

No Apêndice A, discutimos o problema da enumeração de cliques com o peso acima de um limiar. Apresentamos duas variações do algoritmo clássico de Bron-Kerbosch para esse problema. Além disso, adaptamos esses algoritmos para resolver o problema da CLIQUE PONDERADA e comparamos tais algoritmos de enumeração "exaustiva" de cliques maximais com o algoritmo BITRDS1, utilizando grafos de conflitos gerados a partir de problemas de programação inteira e os grafos gerados aleatoriamente.

  no caso de empate, u vem antes de v na ordem ρ. Note que a ordem π depende de ρ e da política de atribuição de pesos aos conjuntos independentes.

	Na seção 2.4, apresentamos uma heurística de coloração proposta em [Tavares
	et al. 2015]. Essa heurística utiliza uma ordem inicial dos vértices fixa para gerar
	os conjuntos independentes durante a heurística de coloração. Nós propomos dois
	esquemas de ordenação, que serão testados computacionalmente.
	Capítulo 3 3.1 Comparação entre limites superiores
	Primeiramente, mostramos que dada uma sequência dos vértices ρ utilizada para
	Limite Superior induzir o grafo direcionado -→ G ρ , podemos encontrar uma coloração ponderada inteira (S, y), utilizando o algoritmo 2.4, tal que y(S) ≤ ( -→ G ρ ). O seguinte lema estabelece
	esse resultado:
	Ela terá influência no cálculo dos limites superiores para a clique máxima Lema 1 Seja (G, w) um grafo ponderada. Para qualquer seqüencia dos vértices ρ, Durante um algoritmo de enumeração implícita para um problema de maximização, a maneira mais comum de podar um subproblema é calcular um limite existe uma coloração ponderada inteira (S, y) de (G, w) tal que y(S) ≤ ( -→ G ρ ).
	ponderada no subgrafos. Por exemplo, o limite superior para G[π 1 , . . . , π j ], conforme superior e verificar que ele é menor que a melhor solução conhecida. De maneira Prova Considere a coloração ponderada inteira (S, y), S = {S 1 , . . . , S k }, construída
	a Proposição 1 geral, um limite superior é computado a partir de uma relaxação do problema. Para é pelo o Algoritmo 2.4, usando como entrada o grafo ponderado (G, w) e a seqüencia ρ .
	max{k|π j ∈S k } o problema CLIQUE PONDERADA, os dois procedimentos principais de limite Vamos mostrar que existe um caminho direcionado P em -→ G ρ que contém pelo menos
	S i superior para a clique máxima ponderada são: um vértice de cada S i . O caminho será construído iterativamente considerando
	i=1 heurística de coloração ponderada os conjuntos independentes na ordem reversa, ou seja, S k , S k-1 , . . . , S 1 . Em S k , No próximo capítulo, mostramos que potencialmente o peso da coloração escolhemos arbitrariamente um vértice v, para ser o último vértice de P . Então
	ponderada inteira que escolhe os vértices seguindo a ordem ρ é igual ao peso do caminho mais pesado no grafo ponderado direcionado -heurística para encontrar o caminho com peso máximo para cada i = k -1, . . . , 1, seja P = vP o caminho direcionado formado após → G ρ . Apresentamos uma heurística de coloração ponderada inteira que encontra resultados melhores que Os procedimentos de limites superiores podem variar quanto à qualidade do considerar os conjuntos independentes S k , . . . , S i+1 , temos duas possibilidades:
	as principais heurísticas encontradas na literatura. A nossa heurística especifica uma ordem fixa ρ para a escolha dos vértices durante a heurística e utiliza uma limite superior e ao tempo gasto para obtê-lo. Uma boa estratégia é procurar o melhor compromisso entre a qualidade do limite superior e o tempo gasto para i. Caso P ∩ S i = ∅, não escolhemos nenhum vértice de S i
	estrutura de dados chamada vetores de bits para acelerar o processo de determinação dos conjuntos independentes. Essas duas características combinadas definem uma calculá-lo em cada subproblema. Na seção 2.1, fazemos uma comparação teórica entre o limite superior dado ii. Caso P ∩ S i = ∅, estendemos P para uvP , escolhendo um vértice u ∈ S i tal que (u, v) ∈ E( -→ G ρ ) tal vértice existe porque S i é maximal e foi formado
	heurística de coloração ponderada que fornecem um limite superior de qualidade por uma coloração ponderada inteira e o limite superior dado pelo caminho com seguindo a sequência π
	peso máximo no grafo ponderado direcionado. Mostramos que os dois limites são com um custo computacional baixo. potencialmente equivalentes. No final, temos que
	Na seção 2.2, apresentamos um procedimento de limite superior baseado no
	caminho direcionado com o maior peso [Yamaguchi e Masuda 2008]. Esse limite k
	superior é utilizado em um algoritmo de Branch & Bound, obtendo bons resultados y(S) = y(S i ) ≤
	computacionais em grafos mais densos i v∈P S∈mathbbS:v∈S
	Na seção 2.3, apresentamos a heurística proposta em [Held, Cook e Sewell 2012].
	Nessa heurística, a ordem em que os vértices são escolhidos durante a coloração
	ponderada é definida dinamicamente usando os pesos residuais.

  S 2 , . . . , S k , ou seja, os vértices em S i vem antes daqueles em S i+1 (dentro do mesma parte, a ordem é arbitrária).

	Seja P um caminho de peso máximo em	-→ G ρ . Note que P não contém dois
	vértices de um mesmo S i . Do contrário, se u e v são dois vértices distintos de P em
	S i , todo o subcaminho de P entre u e v também estaria em S i , um absurdo pois S i
	é um conjunto independente. Logo,
	v∈P	i:v∈S i y(S i ) ≤ i y(S i )

  , . . . , v n ) tal que v i é o vértice com o menor soma dos pesos dos seus adjacentes em G[V \ {v i+1 , . . . , v n }]. Em caso de empate, o vértice v i é o vértice com a maior peso em G[V \ {v i+1 , . . . , v n }].

	],
	um algoritmo de Branch & Bound foi apresentado utilizando esta ordenação
	inicial dos vértices com uma heurística de coloração ponderada. Os resultados
	computacionais mostraram que esse algoritmo superou os algoritmos de
	Ostergaard [ Östergård 2002] e o algoritmo de Yamaguchi [Yamaguchi e Masuda
	2008] para grafos com densidade maior que 50%.
	A ordem de maior grau ponderado primeiro dos vértices de G é uma
	ordem (v 1 Essa estratégia de
	ordenação foi utilizada para ordenar os vértices do conjunto de ramificação
	em [Warren e Hicks 2006](Ver Seção 3.6). Essa ordem pode ser entendida
	como uma extensão para o caso ponderado da ordem proposta em [Matula e
	Beck 1983].

  Tabela 4.1: Procedimentos de limite inferior

	Algoritmo	Referência	Limite Inferior
	BX,BX2	[Balas e Xue 1991], [Balas e Xue 1996] Um limite inferior inicial é obtido a partir da clique máxima
			ponderada de um subgrafo cordal
	Ba	[Babel 1994]	

Um limite inferior é obtido a partir de uma heurística de coloração ponderada inspirada no DSATUR WH [Warren e Hicks 2006] Um limite inferior é obtido a partir de uma heurística gulosa best-in HCS [Held, Cook e Sewell 2012] Um limite inferior inicial é obtido a partir de heurísticas gulosas e melhorado por um procedimento de busca local

  A cada subproblema, o algoritmo usa a regra que gera o menor conjunto de ramificação. Em caso de empate, a primeira regra tem maior prioridade, depois a terceira regra. O conjunto de ramificação é ordenado em ordem decrescente de seus graus em G[P ]. Seja v 1 , v 2 , . . . , v p a ordem do conjunto de ramificação F . O problema é ramificado da seguinte maneira. SendoP i = (P ∩ N (v i )) \ {v i+1 , . . . , v p } ∀v i ∈ F (4.1)Resolve-se recursivamente o problema em cada G[P i ] para i = p, p -1, . . . , 1.

existe uma clique ponderada máxima que deve incluir o vértice v em G[P ], o mesmo acontece para qualquer clique ponderada de G[S ∪ P ] Neste caso, o conjunto de ramificação será F = {v}. O algoritmo usa três heurísticas gulosas para encontrar uma solução inicial e depois essa solução inicial é melhorada através de uma busca local. Cada heurística gulosa constrói uma clique iniciando de um conjunto vazio e adicionando um vértice por vez usando um critério guloso diferente. O peso da clique obtida é utilizada para atualizar o limite inferior inicial do problema. O algoritmo HCS completo encontra-se descrito pelo Algoritmo 4.3. Algoritmo 4.3 Algoritmo proposto por Held, Cook e Sewell 1: função CLIQUE PONDERADA(G, w) 2:

  Busca Tabu com Multivizinhança para clique máxima ponderada função BuscaTabuMultivinhanca (G, L,Iter max ) Entrada: Um grafo ponderado G = (V, E, w), um inteiro L (profundidade da busca) e Iter max número máximo de iterações.

	Algoritmo 4.4
	No nosso algoritmo, o número máximo de iterações, Iter max , depende da
	densidade do grafo. Quando a densidade do grafo for maior 80%, o número máximo
	de iterações será 1.000.000. Caso contrário, será 100.000. A profundidade da busca
	tabu será 4000, valor sugerido em [Wu, Hao e Glover 2012] para grafos ponderados.

Enquanto as restrições da busca tabu estabelecem uma forma de diversificação local, a estratégia de reinicialização aleatória assegura uma forma de diversificação global, forçando a busca a deixar regiões visitadas. O processo de reinicialização é acionado quando a busca atual estiver presa em um ótimo local profundo. Isso acontece quando o número de iterações consecutivas sem melhoras no peso da clique (representado por N I) excede o valor de L (número máximo permitido de iterações sem melhorias). Em outras palavras, L representa a profundidade da busca tabu. Um outro parâmetro da metaheurística é o número máximo de iterações, representado por Iter max .

  3.2 Procedimento de Limite Superior . A ordenação inicial dos vértices ρ é colocada como parâmetro de entrada apenas para dar maior clareza ao texto. Os bits de todos os vetores de bits são organizados seguindo a ordem ρ. Logo, a instrução selecione o primeiro vértice do conjunto Q seguindo a ordem ρ pode ser substituído por selecione o índice do primeiro bit setado em 1 do vetor de bits Q.A cada iteração, um conjunto independente ponderado S i será construído. O vetor de bits Q representa os vértices que podem ser adicionados ao conjunto independente corrente S i . Os vértices adicionados em S i são selecionados do vetor de bits Q seguindo a ordem inicial ρ. Cada vez que um vértice v é selecionado, o conjunto independente S i é atualizado S i ← S i ∪ {v}. Os vértices adjacentes a v e

	No capítulo anterior, mostramos que as heurísticas BIT COLOR1 e
	BIT COLOR2 conseguem obter o melhor compromisso entre a qualidade do limite
	superior e o tempo gasto para calculá-lo. A redução do custo computacional	é
	alcançada por dois fatores:	
	Utilização de vetores de bits.	
	Critério simples de escolha do vértice durante a coloração ponderada.	
	No Algoritmo 4.5, propomos uma implementação, utilizando vetores de bits,
	para a heurística de coloração ponderada inteira. O procedimento tem como

parâmetros: um vetor de bits U , representando um conjunto de vértices; um vetor ρ, representando a ordem inicial dos vértices; um vetor π, representando a ordem obtida a partir da coloração, um vetor color, que armazena o limite superior dado pela coloração ponderada de subgrafos; e um inteiro tamanho que armazena o número de vértices coloridoso próprio v são removidos do bitmap Q

  Tabela 4.6: Instâncias do problema de clique máxima ponderada obtidas a partir das instâncias de conjunto independente máximo ponderado principal ativo de BITCLIQUE é a heurística de coloração ponderada inteira BITCOLOR. Essa heurística consegue o melhor compromisso entre a qualidade do limite superior e o tempo gasto para computá-lo. A qualidade do limite deve-se, em boa parte, a ordem ρ dos vértices adotada. Observe que ela é utilizada a todo momento sem a necessidade de reordenação dos vértices. Já a eficiência computacional é garantida pela utilização de uma estrutura de dados, chamada de vetores de bits (bitmaps), usada para representar o grafo e as estruturas relacionadas a ele. Ela possibilita a realização de operações recorrentes com menos instruções.Além disso, ela fornece uma outra ordenação dos vértices π usada pela estratégia de ramificação.De maneira geral, o método consiste em resolver iterativamente subproblemas cada vez maiores (também chamados de bonecas) até chegar ao problema completo.As bonecas são geradas de maneira que uma esteja contida na próxima, o que sugere o nome do método. Por exemplo, uma boneca pode ser definida por um subproblema contendo menos variáveis (ou menos restrições) que aquele relativo à próxima.

	Instância Problema da clique máxima probabilística [Miao, Balasundaram e Pasiliao (n,p) Tempo de Execução
	2014].		YM	HCS	BITCLIQUE1 BITCLIQUE2
	Instância 1-Insertions 6 Problema da clique máxima ponderada com restrição de agrupamentos (n,p) K Instância (n,p) (527,0.96) 2242.33236 44.24440 1.60668 21.09391 K 1-Insertions 6 (527,0.96) 3537864 2-Insertions 4 2-Insertions 5 (369,0.97) 3597125 3-Insertions 4 (208,0.97) 7642290 2-Insertions 5 (369,0.97) 6089.65302 85.43386 5.97728 3-Insertions 4 (208,0.97) 94.30376 0.60412 0.96879 0.24253 Capítulo 5 5.65855 (149,0.95) 14412641 2-Insertions 4 (149,0.95) 0.38999 0.06504 0.19627 0.26794 [Malladi 2014].
	3-Insertions 5 3-Insertions 5	(460,0.98) 1527371 (460,0.98) *	4-Insertions 4 * 1404.59394 (295,0.98)	4521018 *
	C2000.5.1029 (2000,0.50) 1073741 4-Insertions 4 (295,0.98) 4083.37884 11.38059 DSJC250.1	(241,0.89) 3.63031	8589934 64.45659
	DSJC250.5 DSJC500.1.117 (494,0.90) 4294967 (250,0.50) 8589934 DSJC250.1 (241,0.89) 5831.52009 5261.10567 DSJC250.9 DSJC500.5 C2000.5.1029 (2000,0.50) * * Algoritmos de Bonecas Russas (250,0.10) 8589934 (500,0.50) 646.72284 508.14150 4294967 * *
	DSJC500.9 DSJC250.5	(500,0.10) 4294967 DSJC1000.1.3915 (998,0.90) (250,0.50) 0.09572 0.53295 0.10656	2147483 0.10380
	DSJC1000.5 DSJC250.9	(1000,0.50) 2147483 (250,0.10) 0.00043	DSJC1000.9 0.00526	(1000,0.10) 2147483 0.07170 0.07037
	DSJR500.1c DSJC500.1.117	(189,0.02) 4294967 (494,0.90) *	flat300 28 0 *	(300,0.52) *	7158278 *
	flat1000 50 0 DSJC500.5	(967,0.51) 2147483 (500,0.50) 5.89928	flat1000 60 0 28.16698	(999,0.51) 3.21632	2147483 3.22747
	flat1000 76 0 (1000,0.51) 2147483 DSJC500.9 (500,0.10) 0.00499	latin square 10 0.04924	(90,0.00) 0.13717	2386092 0.14236
	r1000.1c DSJC1000.1.3915 (998,0.90) (511,0.03) 2147483 *	r1000.5 *		(234,0.00) *	2147483 *
	school1 DSJC1000.5 BITRDS.	(336,0.71) 5577879 (1000,0.50) 693.66427 3091.07580		418.77270	411.11693
	DSJC1000.9	(1000,0.10)	0.01523	0.46503		0.28024	0.28836
	DSJR500.1c	(189,0.02)	0.00028	0.00280		0.15113	0.15162
	Em nosso experimentos, o tempo limite de resolução para cada instância é 2h flat300 28 0 (300,0.52) 0.44294 1.80078 0.26329 0.26556
	(7200s). Quando o tempo limite é ultrapassado, tal ocorrência é assinalada como flat1000 50 0 (967,0.51) 159.55484 673.98914 53.00945 93.38235
	* na tabela. Além do tempo de execução, o melhor limite inferior será também flat1000 60 0 (999,0.51) 409.66139 1674.89864 178.62988 227.20397
	reportado. Identificamos em negrito o melhor tempo de execução e o melhor limite flat1000 76 0 (1000,0.51) 863.26174 3940.79916 539.63199 524.88818
	inferior. latin square 10	(90,0.00)	0.00006	0.00119		0.08183	0.08926
	Dentro do tempo limite, os algoritmos BITCLIQUE1 e BITCLIQUE2 r1000.1c (511,0.03) 0.00194 0.02384 0.16896 0.15756
	encontram os melhores limites inferiores (Ver Tabela 4.7), à exceção de r1000.5 (234,0.00) 0.00028 0.00080 0.18398 0.18849 Problema do subtorneio transitivo máximo [Kiviluoto, Östergård e Vaskelainen
	2 instâncias para BITCLIQUE2. school1 (336,0.71) 39.23673 2014].	Em particular, para as instâncias 12.60694 2.12217 0.59738
	C2000.5.1029, DSJC500.1.117 e DSJC1000.1.3915, os algoritmos BITCLIQUE1 Problema do melhor churrasco combinatório [ Östergård, Vaskelainen e Mosig Tabela 4.8: Tempo de Execução para cada instância Exactcolor e BITCLIQUE2 encontram uma clique ponderada com peso superior ao valor K. 2007].
	Isso significa que o algoritmo consegue encontrar uma coluna para ser adicionada
	pelo algoritmo de geração de colunas. O algoritmo HCS não encontra tal coluna no 4.5 Conclusão Problema s-plex máxima [McClosky e Hicks 2012, Trukhanov et al. 2013,
	tempo limite de 10h. Neste capítulo, apresentamos um algoritmo de Branch & Bound combinatório Gschwind et al. 2015].
	Em geral, os algoritmos BITCLIQUE1 e BITCLIQUE2 mostram-se com um desempenho melhor que os outros algoritmos do estado da arte na mesma Problema da clique s-deficiente máxima [Trukhanov et al. 2013, Gschwind et
	competitivos em todas as densidades (Ver Tabela 4.8). Contudo, o algoritmo categoria, atendendo a uma das principais motivações do nosso trabalho. Os al. 2015].

BITCLIQUE1 conseguiu resolver mais instâncias que BITCLIQUE2. Quando um dos novos algoritmos não consegue resolver a instância com o melhor tempo, resultados computacionais mostraram que BITCLIQUE reduz tanto a quantidade de subproblemas quanto o tempo de execução na maior parte das instâncias testadas. O BITCLIQUE1 é mais rápido que os algoritmos anteriores em quase todas as densidades. Essa vantagem cresce à medida que a densidade do grafo aumenta. Ela só é superada por BITCLIQUE2, quando a densidade do grafo ultrapassa 90%. No próximo capítulo, mostraremos como incorporar a heurística BITCOLOR em um algoritmo de Bonecas Russas. Essa adaptação está sendo chamada de O método de Busca de Bonecas Russas (Russian Doll Search) foi proposto originalmente em 1996 para problemas de satisfação de restrições em [Verfaillie, Lemaître e Schiex 1996]. De maneira independente, Östergård apresentou uma variação do método de Bonecas Russas para um problema de otimização discreta em [ Östergård 2002]. Recentemente, o método de Bonecas Russas foi aplicado em outros problemas de otimização discreta:

Problema da clique máxima

[START_REF] Östergård | A fast algorithm for the maximum clique problem[END_REF][ Östergård , Corrêa et al. 2014

].

Problema da clique máxima ponderada

[ Östergård 1999, Kumlander 2008, Shimizu et al. 2012]

.

Problema da cobertura tripla de Steiner

[ Östergård e Vaskelainen 2011]

.

Problema s-feixo máximo

[Gschwind et al. 2015]

.

A eficiência do método de Bonecas Russas depende também da utilização do conhecimento acumulado durante a resolução de subproblemas menores (bonecas menores), de modo a reduzir o tamanho da árvore de busca empregada na resolução dos subproblemas maiores (bonecas maiores). Com a ajuda das bonecas, podemos definir uma relação de dominação entre subproblemas que permite podar os subproblemas dominados. Dizer que um subproblema S 1 domina um outro subproblema S 2 significa que, para qualquer solução de S 2 , existe uma solução melhor ou igual em S 1 . A partir dessa relação, podemos definir regras de poda que utilizem eficientemente o conhecimento previamente obtido.

  ], mostra-se que o método de Busca de Bonecas Russas pode ser estendido para qualquer propriedade Π que seja hereditária nos subgrafos Várias propriedades em grafos são hereditárias, tais como: clique, conjunto independente, bipartido, acíclico, perfeito, planar entre outros. Trukhanov apresenta uma extensão do algoritmo das Bonecas Russas para o problema s-plex máxima e o problema da clique s-deficiente máxima. De maneira geral, esses dois problemas são relaxações do problema da clique máxima e/ou conjunto independente máximo.Em[Corrêa et al. 2014], apresenta-se um algoritmo de Busca das Bonecas Russas para o problema da clique máxima que apresenta duas modificações importantes em relação ao algoritmode Östergård: 

induzidos, ou seja, para qualquer S ⊆ V tal que G[S] satisfaz a propriedade Π, a remoção de qualquer subconjunto de vértices em G[S] não produz um grafo que viola a propriedade Π.

  5.1 resolve cada uma das n bonecas, ou seja, encontra a clique máxima ponderada em cada subgrafo G i , para i ∈ {1, . . . , n}; seu peso é armazenado em c[ρ i ]. O problema da i-ésima boneca divide-se em verificar se existe ou não uma clique máxima ponderada em G i com o vértice ρ i . Sabemos que o peso da clique máxima ponderada sem o vértice ρ i em G i é c[ρ i-1 ]. Assim, o problema da clique ponderada máxima em G i se resume a encontrar a clique máxima ponderada em

  BITRDS2, o desempenho médio de BITCLIQUE2 é superior. Vale salientar aqui que a ordem maior grau ponderado primeiro compromete o poder de poda do vetor c, uma vez que o valor das soluções armazenadas cresce rapidamente.

	Instância Instância vértices são dados pelos valores das variáveis duais do problema escalonados por Números de Subproblemas Tempo de Execução Instancia (n,p) Número de Subproblemas limite, ou obtém um tempo de execução bastante superior aos outros algoritmo 5.4 Conclusão a integração de métodos mais elaborados de enumeração implícita à Busca por
	Nome sanr400 0.5 san1000 brock400 1 brock400 2 brock400 3 brock400 4 brock800 1 brock800 2 brock800 3 brock800 4 sanr400 0.7 san400 0.7 1 san400 0.7 2 Nas outras instâncias, temos que os algoritmos que usam a primeira ordem, (n,p) BITCLIQUER1 BITCLIQUER2 CLIQUER BITRDS1 RDS2 (400,0.50) 3.74e+03 4.05e+03 2.88e+05 5.22e+04 4.13e+04 (1000,0.50) 3.06e+03 2.35e+03 * 1.03e+05 4.05e+04 (400,0.75) 1.96e+06 1.76e+06 5.14e+08 1.14e+07 1.94e+07 (400,0.75) 2.28e+06 2.51e+06 7.05e+08 1.69e+07 2.58e+07 (400,0.75) 1.77e+06 1.85e+06 5.44e+08 1.11e+07 1.55e+07 (400,0.75) 1.04e+06 7.56e+05 5.54e+08 1.36e+07 3.24e+07 (800,0.65) 8.77e+06 1.64e+07 2.23e+09 9.85e+07 2.44e+08 (800,0.65) 1.62e+07 3.07e+07 2.34e+09 1.01e+08 3.41e+08 (800,0.65) 1.15e+07 2.12e+07 2.44e+09 1.04e+08 2.56e+08 (800,0.65) 1.78e+07 3.38e+07 2.86e+09 1.19e+08 3.84e+08 (400,0.70) 3.46e+05 3.46e+05 6.06e+07 2.83e+06 3.88e+06 (400,0.70) 4.30e+04 9.19e+04 * 3.85e+05 6.77e+05 (400,0.70) 6.45e+04 7.20e+04 * 1.04e+06 2.29e+06 BITCLIQUE1 e BITRDS1, são mais rápidos que os demais. Da mesma maneira, nem sempre BITCLIQUE1 é superior a BITRDS1, contudo seu melhor desempenho médio prevalece. Percebemos também que BITRDS1 resolve 7 instâncias, que não são resolvidas por CLIQUER em 2h, em menos de 600s, enquanto, BITRDS2 resolve 11 instâncias não resolvidas por CLIQUER. Em geral, na maioria das instâncias, qualquer um dos quatro algoritmos demanda san400 0.7 2 (400,0.70) 2.95 5.12 * 6.69 15.43 C2000.5.1029 (2000,0.50) * * * * r1000.1c (511,0.03) 0.17 0.16 0.00 0.00 menos tempo de computação que CLIQUER. Nome (n,p) BITCLIQUER1 BITCLIQUER2 CLIQUER BITRDS1 RDS2 sanr400 0.5 (400,0.50) 0.15 0.18 0.11 0.12 0.12 san1000 (1000,0.50) 1.99 2.29 * 5.61 2.22 brock400 1 (400,0.75) 29.98 37.80 152.09 29.21 51.94 brock400 2 (400,0.75) 34.75 51.32 213.81 44.37 65.67 brock400 3 (400,0.75) 28.66 38.58 170.55 27.94 43.63 brock400 4 (400,0.75) 17.83 20.11 168.36 32.79 78.49 brock800 1 (800,0.65) 391.50 853.90 972.69 413.09 1096.71 brock800 2 (800,0.65) 598.11 1323.48 1005.68 437.06 1531.12 brock800 3 (800,0.65) 457.88 986.15 1062.58 462.08 1144.26 brock800 4 (800,0.65) 610.96 1412.36 1248.55 511.67 sanr400 0.7 (400,0.70) 5.65 7.95 18.08 6.90 11.05 san400 0.7 1 (400,0.70) 2.13 4.56 * 2.75 3.94 DSJC500.5 (500,0.50) 4.50e+05 4.55e+05 2.00e+07 2.24e+06 DSJC1000.5 (1000,0.50) 3.08e+07 3.16e+07 2.19e+09 1.78e+08 DSJR500.1c (189,0.02) 0.15 0.15 0.00 0.00 r1000.5 (234,0.00) 0.18 0.19 0.00 0.00 algoritmos de Branch & Bound para instâncias com a densidade entre 50% e 80%. Resolução 1681.99 um valor K, para o algoritmo ser numericamente seguro. O tempo limite para a resolução de cada instância é 2h (7200s). Quando o tempo limite é ultrapassado, tal ocorrência é assinalada como * na tabela. Identificamos em negrito o melhor desempenho em cada caso. A Tabela 5.5 apresenta a quantidade de subproblemas enumerados por cada algoritmo. Já a Tabela 5.6 mostra o tempo de execução BITCLIQUER1 BITCLIQUER2 CLIQUER BITRDS1 latin square 10 (90,0.00) 1.00e+00 1.00e+00 9.00e+01 9.00e+01 r1000.5 (234,0.00) 1.00e+00 1.00e+00 2.35e+02 2.34e+02 DSJR500.1c (189,0.02) 7.00e+00 4.00e+00 3.34e+02 2.25e+02 r1000.1c (511,0.03) 1.60e+02 1.26e+02 1.68e+03 9.56e+02 DSJC250.9 (250,0.10) 9.50e+01 1.08e+02 9.75e+02 5.25e+02 de Bonecas Russas. Para essa mesma faixa, BITRDS1 e BITRDS2 conseguem Resolução representa um grande desafio. Neste capítulo, apresentamos uma maneira eficiente de incorporar a heurística resolver seis instâncias, que não foram resolvidas por CLIQUER, em menos de 10 BITCOLOR ao algoritmo de Bonecas Russas, dando origem ao algoritmo Em [Palpant, Artigues e Oliva 2007], uma hibridização da Busca por Resolução minutos . Por outro lado, nenhum dos algoritmos conseguiu encontrar a solução BITRDS. Em relação ao melhor algoritmo de Bonecas Russas da literatura, em com técnicas de programação por restrições é apresentada. Neste trabalho, o ótima das instâncias C2000.5.1029, DSJC500.1.117 e DSJC1000.1.3915 dentro do grafos gerados aleatoriamente, BITRDS1 reduz tanto o número de subproblemas Capítulo 6 algoritmo é adaptado para resolver o problema das n 2 -rainhas. Novamente, tempo limite. quanto o tempo de execução. Essa diferença fica mais evidente à medida que a o método baseado na Busca por Resolução mostrou-se superior ao algoritmo consumido por cada um deles. DSJC500.9 (500,0.10) 2.78e+02 3.47e+02 4.39e+03 2.10e+03 Instância (n,p) Tempo de Execução densidade do grafo aumenta. Essa redução torna-se bastante expressiva quando clássico de enumeração implícita usando a mesma estratégia de ramificação. Número de Subproblemas BITRDS1 e BITRDS2 reduzem o número de subproblemas enumerados DSJC1000.9 (1000,0.10) 1.41e+03 1.50e+03 2.55e+04 1.31e+04 DSJC250.5 (250,0.50) 1.30e+04 1.27e+04 3.54e+05 5.65e+04 BITCLIQUER1 BITCLIQUER2 CLIQUER BITRDS1 BITRDS2 0.01 * 2.28e+06 0.00 1.83e+08 0.00 RDS2 9.00e+01 2.34e+02 1.96e+02 6.22e+02 4.49e+02 2.00e+03 1.44e+04 5.29e+04 latin square 10 (90,0.00) 0.08 0.09 0.00 0.00 0.00 comparamos CLIQUER com BITRDS2 para grafos com a densidade superior ou igual a 90%. Além disso, vale notar que BITRDS1 mostra-se mais eficiente que os Contudo, apesar de interessante, o resultado computacional obtido não foi Algoritmos de Busca por competitivo com o algoritmo do estado da arte para o problema.
	san400 0.7 3 san400 0.7 3 flat300 28 0 DSJC250.9	(400,0.70) (400,0.70) (300,0.52) (250,0.10)	4.66e+04 2.12 4.58e+04 0.07	7.85e+03 0.76	* 4.67e+04 0.07	*	1.19e+06 1.37e+05 6.94 1.27 1.49e+06 1.98e+05 0.00 0.00	2.05e+05 0.00
	p hat500-2 p hat500-2 flat1000 50 0 DSJC500.9	(500,0.50) (500,0.50) (967,0.51) (500,0.10)	1.83e+04 0.51 1.16e+06 0.14	5.32e+02 0.09		1.43e+07 3.22 2.04e+06 0.14	4.01e+05 6.76e+03 1.64 0.03 7.38e+07 7.86e+06 0.01 0.01	2.27e+07 0.01
	p hat700-2 p hat700-2 flat1000 60 0 DSJC1000.9	(700,0.50) (700,0.50) (999,0.51) (1000,0.10) 7.59e+05 18.28 5.97e+06 0.28	2.07e+03 0.27		4.29e+08 93.14 7.80e+06 0.29	6.00e+06 2.24e+04 37.05 0.13 4.16e+08 3.47e+07 0.02 0.03	7.07e+07 0.03
	p hat1000-2 p hat1500-2 p hat1000-2 p hat1500-2 flat1000 76 0 (1000,0.49) (1500,0.51) (1000,0.49) (1500,0.51) (1000,0.51) 1.67e+07 * 716.71 * 3.93e+07 DSJC250.5 (250,0.50) 0.11	8.48e+04 3.20e+06 9.11 566.07 3.99e+07 1.07e+10 * 2955.63 * 0.10	9.76e+07 9.12e+05 * 3.74e+07 864.28 5.31 * 325.62 2.79e+09 2.25e+08 0.09 0.05	2.30e+08 0.05
	p hat300-3 p hat300-3 school1 DSJC500.5	(300,0.74) (300,0.74) (336,0.71) (500,0.50)	4.66e+04 0.57 1.31e+05 3.22	2.64e+03 0.10	4.70e+07 9.33 4.42e+04 3.23	6.05e+05 2.26e+04 1.47 0.08 1.49e+08 3.97e+05 5.51 3.22	1.27e+05 3.14
	p hat500-3 p hat500-3 DSJC250.1 DSJC1000.5	(500,0.75) (500,0.75) (241,0.89) (1000,0.50) 1.59e+07 301.27 1.12e+08 418.77	1.05e+05 4.53 7.60e+07 * 411.12	*	1.00e+08 1.10e+06 419.27 5.31 * 5.76e+08 733.11 416.52	3.85e+08 396.96
	gen200 p0.9 44 (200,0.90) gen200 p0.9 44 (200,0.90) DSJC500.1.117 (494,0.90) C2000.5.1029 (2000,0.50) 4.23e+05 2.91	* *	1.73e+04 0.48		* *	1.89e+09 345.45	2.39e+06 1.38e+05 5.13 0.37 * * * *	* *
	gen200 p0.9 55 (200,0.90) gen200 p0.9 55 (200,0.90) DSJC1000.1.3915 (998,0.90) flat300 28 0 (300,0.52)	1.12e+05 1.11	* 0.26	4.22e+03 0.35		4.68e+09 885.36 0.27 *	5.03e+06 9.73e+04 9.68 0.26 * * 0.36 0.30	* 0.21
	gen400 p0.9 55 (400,0.90) gen400 p0.9 55 (400,0.90) 2-Insertions 4 (149,0.95) flat1000 50 0 (967,0.51)	*	* 1.02e+04 53.01	1.32e+08 3272.15 4.34e+04 * 93.38	*	* 2.29e+08 * 36.58	1.42e+09 6950.08 2.16e+04 38.20	6.87e+04 97.06
	gen400 p0.9 65 (400,0.90) gen400 p0.9 65 (400,0.90) 1-Insertions 6 (527,0.96) flat1000 60 0 (999,0.51)	*	* 5.66e+04 178.63	*	*		* 8.50e+05 227.20	*	* * 187.11 *	* 1.95e+07 * 131.87	4.43e+06 232.54
	gen400 p0.9 75 (400,0.90) C250.9 (250,0.90) gen400 p0.9 75 (400,0.90) C250.9 (250,0.90) 2-Insertions 5 (369,0.97) flat1000 76 0 (1000,0.51) 3.48e+08 2.30e+06 6738.43 18.33 6.10e+05 539.63	9.03e+06 2.15e+05 325.59 3.55 6.01e+05 * 1.18e+10 * 2437.97 524.89	* 2.37e+07 2.49e+06 7.48e+08 * 3200.62 60.19 7.94 * 1.40e+07 935.53 531.48	6.65e+05 504.08
	san200 0.9 1 san200 0.9 1 3-Insertions 4 school1	(200,0.90) (200,0.90) (208,0.97) (336,0.71)	6.26e+03 0.54 2.20e+05 2.12	2.60e+01 0.46	* 4.50e+03 0.60	*	4.65e+05 5.48e+02 1.01 0.00 * 2.31e+06 48.65 3.22	1.03e+04 0.57
	san200 0.9 2 san200 0.9 2 4-Insertions 4 DSJC250.1	(200,0.90) (200,0.90) (295,0.98) (241,0.89)	2.29e+04 0.50 4.56e+05 646.72	6.54e+03 0.39	8.43e+08 118.20 9.57e+06 508.14	5.64e+05 3.66e+06 1.07 7.49 * 1.05e+07 * 1007.56	5.16e+06 737.97
	san200 0.9 3 san200 0.9 3 3-Insertions 5 DSJC500.1.117 (200,0.90) (200,0.90) (460,0.98) (494,0.90)	1.14e+06 7.41 1.19e+08 *	9.52e+04 1.51	* *	7.14e+09 1287.49	6.31e+06 7.19e+05 12.57 2.20 * * * *	3.92e+07 *
	san400 0.9 1 san400 0.9 1 DSJC1000.1.3915 (998,0.90) (400,0.90) (400,0.90) Busca por Resolução apresenta uma exploração mais inteligente do espaço de 6.59e+06 2.33e+06 * 1.06e+08 5.38e+08 174.92 83.22 * 492.12 2269.02 * * * *	*
	sanr200 0.9 sanr200 0.9 Tabela 5.5: Números de subproblemas para cada instância EXACTCOLOR (200,0.90) 7.24e+05 5.56e+04 3.11e+09 7.11e+06 3.59e+05 (200,0.90) 4.22 0.92 577.69 13.13 0.91 2-Insertions 4 (149,0.95) 0.20 0.27 29.38 0.03 busca, baseada nos algoritmos de backtracking inteligente. O método da Busca	0.11
	hamming10-2 (1024,0.99) hamming10-2 (1024,0.99) 1-Insertions 6 (527,0.96) 1.00e+01 0.62 por Resolução já foi utilizado nos seguintes problemas com um relativo sucesso: * 1.44e+09 3.41e+05 * * 716.31 1.81 * 1.61 21.09 * 132.64	46.32
	MANN a27 MANN a27 Tempo de Execução (378,0.99) (378,0.99) 2-Insertions 5 (369,0.97)	*	*	5.98	7.68e+03 1.17		5.66	*	*	* *	*	2.58e+04 0.20 72.38	4.19
	Tabela 5.3: Números de subproblemas gerados para as instâncias DIMACS-W Tempo de Execução Tabela 5.4: Tempos de execução para as instâncias DIMACS-W 5.3.3 EXACTCOLOR 3-Insertions 4 (208,0.97) 0.97 0.24 * 5.06 Em [Demassey, Artigues e Michelon 2004], o método foi aplicado ao problema Analisando os tempos de computação dos 4 novos algoritmos, percebemos que 4-Insertions 4 (295,0.98) 3.63 64.46 * 40.48 de escalonamento de projetos com restrição de recursos. Neste trabalho, uma para grafos com a densidade até 70%, os algoritmos de Bonecas Russas apresentam 3-Insertions 5 (460,0.98) 1404.59 * * * versão básica da Busca por Resolução é comparada com uma versão clássica de melhor desempenho que seus correspondentes em Branch & Bound (com raras enumeração implícita, ambas usando a mesma formulação e mesma regra de	0.04 25.54 381.25
	As instâncias EXACTCOLOR são instâncias oriundas da geração de colunas para Tabela 5.6: Tempos de execução para cada instância EXACTCOLOR ramificação. Os resultados computacionais indicaram uma vantagem da Busca
	resolução do problema do número cromático fracionário. Os pesos atribuídos aos por Resolução sobre o método de enumeração. Porém, os autores relatam que

todos os algoritmos entre si, vemos que os algoritmos de Branch & Bound BITCLIQUE1 e BITCLIQUE2 ainda geram menos subproblemas os demais algoritmos de Bonecas Russas. As instâncias com densidade superior a 90% (com exceção de hamming10-2 ) e aquelas da família p-hat são mais rapidamente resolvidas quando usamos a segunda ordem (maior grau ponderado primeiro). Embora, nem sempre melhor que em até 4 ordens de magnitude com relação ao algoritmo CLIQUER (Instância 2-Insertions 4 ). Novamente, essa redução aumenta à medida que a densidade do grafo aumenta. O algoritmo BITRDS1 resolve 5 instâncias que CLIQUER não resolve dentro do tempo limite, enquanto, BITRDS2 resolve 6 instâncias não resolvidas por ele. Destacamos que BITRDS2 resolve 1 instância não resolvida por BITCLIQUE2. Porém, na maioria das instâncias, BITRDS1 e BITRDS2 são superados pelo algoritmo de Branch & Bound usando a mesma ordem. exceções). Para a densidade superior 70%, não há uma tendência clara. Para instâncias até 50%, CLIQUER mostra-se competitivo com os demais algoritmos de Bonecas Russas. A partir de 50%, ou CLIQUER supera o tempo O nosso método de Bonecas Russas para CLIQUE PONDERADA adiciona algumas características interessantes ao método original: Integração com um procedimento de limite superior diferente, baseado em uma heurística de coloração. Definição de uma estratégia de ramificação diferente. Ela utiliza a coloração ponderada para definir o conjunto de ramificação e a ordem de ramificação segue a ordem inicial ρ. Acreditamos que essas modificações, junto com o uso de vetores de bits, foram responsáveis pelo bom desempenho de BITRDS nos grafos com a densidade média. A principal vantagem do método de Bonecas Russas é a estratégia de poda definida a partir do vetor de soluções armazenadas c. Contudo, o tempo requerido para calcular completamente o vetor c pode superar a redução de tempo proporcionada por ele. No próximo capítulo, apresentamos uma cooperação entre o algoritmo de Bonecas Russas e o Algoritmo de Busca por Resolução. Nela, o vetor c não é calculado completamente, mas ele continua sendo utilizado para enumerar implicitamente regiões do espaço de busca. Este capítulo é dedicado à apresentação do método de Busca por Resolução e da nossa proposta de aplicação ao problema CLIQUE PONDERADA. Este método foi apresentado por Chvátal em [Chvátal 1997], como uma alternativa ao método de enumeração implícita que fosse menos dependente da estratégia de ramificação. Durante o método de enumeração implícita usando a estratégia de busca em profundidade, o processo pode gastar bastante tempo de exploração em uma região infértil do espaço de busca. Esse fenômeno, conhecido como thrashing, ocorre quando diferentes regiões do espaço de busca falham pelo mesmo motivo ou por motivos similares. Por exemplo, isso ocorre quando uma inviabilidade causada pela fixação de uma variável é encontrada somente quando sua sub-árvore é totalmente explorada. Essa característica torna a enumeração implícita bastante dependente de uma estratégia de ramificação eficiente. Com o objetivo de reduzir o thrashing, a Em [Boussier et al. 2010], um algoritmo híbrido combinando Busca por Resolução, enumeração implícita e enumeração explícita foi apresentado para resolver o problema da mochila multidimensional. Com essa abordagem, instâncias previamente não resolvidas do problema da mochila inteira 0-1 multidimensional foram solucionadas de maneira exata. Os resultados indicam a vantagem de deixar a Busca por Resolução conduzir o processo de Busca, confirmando os resultados obtidos em [Demassey, Artigues e Michelon 2004] e [Palpant, Artigues e Oliva 2007].

  Busca por Resolução 1: record ← valor de uma solução inicial.

	Algoritmo 6.2	
	A eficácia do Algoritmo 6.2 depende de pelo menos 2 pontos que estão
	inter-relacionados.	O primeiro ponto fundamental é a implementação do
	procedimento obstáculo, cujo propósito descrito, já antecipado, é realizar uma
	busca em X(U F ), procurando por um nogood S. Deve-se ter em mente um
	compromisso entre o tempo gasto nessa busca e o tamanho da região coberta por S.

.1.3 Estrutura Geral

O algoritmo genérico de Busca por Resolução, que pode ser descrito como no Algoritmo 6.2, começa inicializando a família F de nogoods. Enquanto a família de nogoods F não alcançar todo o espaço de busca, uma solução parcial ainda não alcançada pela família F, denotado por U F , será selecionada. Na linha 5, o procedimento obstáculo é responsável por encontrar um nogood S tal que X(U F ) ∩ X(S) = ∅. Depois, o nogood S é "adicionado" a família F. Essa adição pode ser simplesmente inserir a solução parcial S na família ou modificar a família F para possibilitar a sua inserção. 2: Inicialize a família F de nogoods.

3: Enquanto X(F) = {0, 1} n faça 4:

  13: Retorne w(C) + color[pi c ont]

	6.2.2 Obstáculo e política de mergulho
		A partir da função oráculo, apresentada no Algoritmo 6.11, definimos um
	versão para o procedimento obstáculo rápido (Ver Algoritmo 6.12). O oráculo
	apresentado aqui não é totalmente caixa preta, uma vez que podemos acessar a
	ordem devolvida pela heurística de coloração ponderada. Tal ordem será usada para
	definir a política de mergulho: Enquanto o limite superior for superior a record e
	U ainda tem variável livre, o último vértice colorido pela heurística de coloração	é
	escolhido e a variável associada a ele é fixada em 1.
	Algoritmo 6.12 obstáculo(U, record, S)
	1: bound ← oráculo(U )	
	2: Enquanto U ∈ {0, 1} n e bound > record faça
	3:	j ← π[cont]	
	4:	u j ← 1	
	5:	bound ← oráculo(U )	oráculo(U, C, P, π, color, cont)
	6: Se bound > record então	
	7:		

  Mesmo quando o algoritmo de Busca por Resolução realiza menos chamadas ao oráculo do que o Algoritmo de Branch & Bound (ordem de menor peso primeiro), o tempo de execução daquele fica superior ao deste (Ver Tabela 6.9).

	Instância Instância	Chamadas do oráculo Ordem de menor peso primeiro	Tempo de Execução Ordem de maior grau ponderado primeiro
	Obstáculo Na próxima seção, propomos um algoritmo que realiza uma cooperação entre Obstáculo Chamadas ao oráculo Chamadas ao oráculo
	Nome o algoritmo de Bonecas Russas e o Algoritmo de Busca por Resolução. A ideia (n,p) Obstáculo Padrão Obstáculo Modificado Modificado com decrescimento Obstáculo Padrão Obstáculo Modificado com decrescimento Modificado Obstáculo Obstáculo é Modificado Modificado
	brock200 1 (200,0.75) realizar uma exploração parcial do espaço de busca usando o algoritmo de Bonecas 3.59e+04 2.08e+04 1.86e+04 0.189 0.105 Nome (n,p) com decrescimento Branch & Bound com decrescimento Branch & Bound 0.097
	brock200 2 (200,0.50) Russas e, depois, o restante da exploração passe a ser realizada pelo Algoritmo de 3.20e+03 1.96e+03 1.82e+03 0.065 0.056 brock200 1 (200,0.75) 0.13 0.10 0.10 0.08	0.056
	brock200 3 (200,0.61) brock200 4 (200,0.66) brock200 2 (200,0.50) Busca por Resolução, fazendo o uso da informação coletada durante a resolução das 4.06e+03 2.35e+03 2.12e+03 0.064 0.052 1.35e+04 7.69e+03 7.03e+03 0.095 0.063 0.05 0.05 0.06 0.05 brock200 3 (200,0.61) 0.05 0.05 0.05 0.05	0.054 0.062
	brock400 1 (400,0.75) bonecas. brock200 4 (200,0.66)	2.21e+07 0.06	1.44e+07	1.28e+07 0.06	155.657 0.06	69.192	0.05	63.060
	brock400 2 (400,0.75) brock400 1 (400,0.75)	3.09e+07 43.37	1.99e+07	1.77e+07 29.94	211.372 63.06	93.778	38.91	85.161
	brock400 3 (400,0.75) Instância brock400 2 (400,0.75)	2.35e+07 Ordem de menor peso primeiro 1.51e+07 1.34e+07 50.98 34.67	165.284 Ordem de maior grau ponderado primeiro 72.683 65.182 85.16 51.84
	brock400 4 (400,0.75) Instância brock400 3 (400,0.75)	1.15e+07 Chamadas do oráculo 2.12e+07 39.06 26.93 1.88e+07	82.529 Chamadas do oráculo 99.242 65.18 38.91	89.161
	p hat300-1 (300,0.24) p hat300-2 (300,0.49) brock400 4 (400,0.75) Nome (n,p) p hat300-1 (300,0.24)	4.03e+02 2.09e+03 Obstáculo 2.13e+02 1.22e+03 Modificado 46.68 com decrescimento Branch & Bound 2.03e+02 1.14e+03 17.66 0.08 0.07	0.082 0.060 Obstáculo 89.16 Modificado com decrescimento 0.08	0.077 0.048 Branch & Bound 0.075 20.41 0.048 0.07
	p hat300-3 (300,0.74) brock200 1 (200,0.75) p hat300-2 (300,0.49)	2.93e+04 2.96e+04 1.82e+04 0.06	1.62e+04 2.97e+04 0.06	0.247 1.86e+04 0.05	0.130 1.80e+04 0.04	0.122
	p hat500-1 (500,0.25) brock200 2 (200,0.50) p hat300-3 (300,0.74)	3.59e+03 1.58e+03 0.74	2.14e+03	2.01e+03 1.62e+03 0.57	0.160 1.82e+03 0.12	0.129	1.79e+03 0.10	0.121
	p hat500-2 (500,0.50) brock200 3 (200,0.61) p hat500-1 (500,0.25)	7.97e+03 2.77e+03 4.76e+03 0.12	4.38e+03 2.85e+03 0.12	0.177 2.12e+03 0.12	0.097 2.11e+03 0.12	0.095
	p hat500-3 (500,0.75) brock200 4 (200,0.66) p hat500-2 (500,0.50)	1.44e+06 7.37e+03 8.78e+05 0.58	7.94e+05 7.47e+03 0.50	15.730 7.03e+03 0.10	6.794	6.81e+03 0.09	6.310
	p hat700-1 (700,0.25) brock400 1 (400,0.75) p hat500-3 (500,0.75)	1.16e+04 8.59e+06 386.77	7.53e+03	7.08e+03 8.65e+06 296.29	0.367 1.28e+07 6.31	0.199	1.10e+07 4.57	0.190
	p hat700-2 (700,0.50) brock400 2 (400,0.75) p hat700-1 (700,0.25)	2.95e+04 1.02e+07 0.19	1.72e+04	1.62e+04 1.02e+07 0.18	0.740 1.77e+07 0.19	0.300		1.55e+07 0.18	0.287
	p hat1000-1 (1000,0.24) brock400 3 (400,0.75) p hat700-2 (700,0.50)	4.90e+04 7.76e+06 21.29	3.47e+04	3.28e+04 7.81e+06 17.69	1.425 1.34e+07 0.29	0.516		1.15e+07 0.27	0.496
	p hat1000-2 (1000,0.49) brock400 4 (400,0.75) p hat1000-1 (1000,0.24)	1.22e+06 9.42e+06 0.46	7.77e+05	7.19e+05 4.80e+06 0.41	30.749 1.88e+07 0.50	11.759	5.20e+06 0.38	10.942
	p hat1500-1 (1500,0.25) p hat300-1 (300,0.24) p hat1000-2 (1000,0.49)	3.15e+05 3.01e+02 1.99e+05 809.26	1.87e+05 3.09e+02 686.72	10.698 2.03e+02 10.94	2.865		2.18e+02 9.32	2.728
	p hat300-2 (300,0.49) p hat1500-1 (1500,0.25)	5.07e+03 2.63	5.36e+03 2.15	1.14e+03 2.73		1.08e+03 1.78
	Tabela 6.7: Comparação entre os procedimentos obstáculo padrão, modificado e p hat300-3 (300,0.74) 1.46e+05 1.47e+05 1.62e+04 1.50e+04
	modificado com fase de decrescimento considerando a ordem de menor peso p hat500-1 (500,0.25) 1.87e+03 1.96e+03 2.01e+03 2.01e+03 Tabela 6.9: Comparação entre o tempo de execução do Algoritmo de Busca por
	primeiro. p hat500-2 (500,0.50) Resolução utilizando obstáculo modificado com decrescimento com o 6.68e+04 6.70e+04 4.38e+03 4.12e+03
	p hat500-3 (500,0.75) Algoritmo de Branch & Bound, nas duas ordem testadas. 5.37e+07 5.10e+07 7.94e+05	6.97e+05 indica que o
	6.2.8 Comparação com o algoritmo BITCLIQUE p hat700-1 (700,0.25) 5.76e+03 6.07e+03 algoritmo consegue o menor tempo de execução entre os quatros algoritmos 7.08e+03 6.62e+03 p hat700-2 (700,0.50) 2.30e+06 2.36e+06 1.62e+04 1.57e+04 considerados.
	Realizamos um experimento computacional breve para comparar o desempenho p hat1000-1 (1000,0.24) 2.78e+04 2.91e+04 3.28e+04 2.93e+04
	do algoritmo de Busca por Resolução com Branch & Bound apresentado no Capítulo p hat1000-2 (1000,0.49) 6.44e+07 6.60e+07 7.19e+05 6.48e+05
	3. Considerando a ordem de menor peso primeiro (Ver Tabela 6.8), o algoritmo p hat1500-1 (1500,0.25) 1.79e+05 1.89e+05 1.87e+05 1.77e+05
	de Busca por Resolução realizou menos chamadas ao oráculo do que o Algoritmo Tabela 6.8: Comparação entre o número de chamadas ao oráculo pelo Algoritmo de de Branch & Bound. Já com a ordem de maior grau ponderado primeiro, o Busca por Resolução utilizando obstáculo modificado com decrescimento e
	algoritmo de Branch & Bound foi com maior freqüência aquele que gerou o menor pelo Algoritmo de Branch & Bound, nas duas ordem testadas. indica
	que o algoritmo consegue o menor número de chamadas ao oráculo entre os número de chamadas ao oráculo. De maneira geral, porém, para a mesma ordem quatros algoritmos considerados.
	inicial dos vértices, os algoritmos possuem um comportamento bastante similar com
	respeito ao número de chamadas ao oráculo.				

  Usando essa ideia, apresentamos o Algoritmo 6.15 que propõe uma cooperação entre Bonecas Russas e Busca por Resolução. Inicialmente, aplicamos o algoritmo de Bonecas Russas, seguindo a ordem ρ, até um vértice v l (l = limite). Com issocalculamos exatamente c(v 1 ) ≤ . . . ≤ c(v l ). Os demais valores c(v l+1 ) ≤ . . . ≤ c(v n ) sãocalculados de forma aproximada (limite superior). Nos testes realizados, utilizamos limite como 0.90 * n. Acreditamos que, a partir de 0.90 * n, o custo para calcular c(v) não é proporcional ao seu poder de poda no algoritmo de Bonecas Russas. Também com o algoritmo de Bonecas Russas, geramos o nogood inicial S = x ρ l+1 x ρ l+2 . . . x ρn . Para potencializar o processo de poda, calculamos também um novo record, usando a heurística tabu do nosso algoritmo de Branch & Bound.Após esses passos, aplicamos o Algoritmo de Busca por Resolução, que faz uso de um obstáculo híbrido a ser descrito na Subseção 6.3.2. Ele aproveita tanto a informação gerada pelas bonecas quanto da coloração dos vértices candidatos para gerar os nogoods.

	Algoritmo 6.15 Cooperação entre o algoritmo de Bonecas Russas e o Algoritmo
	de Busca por Resolução
	função MAIN
	Algoritmo de Bonecas Russas
	ρ

. . , ρ n Podemos usar esta ideia em conjunto com uma solução parcial U para gerar um nogood fixando, possivelmente, menos variáveis. Sejam C e P encontrados por oráculo(U ). Analogamente, ao caso da coloração, obtemos um nogood se fixamos em 0 todo o vértice v que w(C) + c(v) > record. Novamente o teste é facilitado porque os valores de c estão ordenados em ordem não-decrescente, quando seguimos a sequência ρ.

Se interrompemos o processo de Bonecas Russas na iteração l, não temos disponível c(v), para v ∈ {ρ l+1 , . . . , ρ n }. Mesmo assim, podemos aplicar a estratégia de obtenção dos nogoods descrita acima, se atribuirmos a c(v) um limite superior para a clique ponderada máxima em G[ρ 1 , . . . , ρ i = v] para v ∈ {ρ l+1 , . . . , ρ n }.

  Caso seja superior a bound, fixamos a variável associada ao último vértice de R (max{ρ j | ρ j ∈ R}) em zero em U 1 e removemos ele de R.No final do laço, U 1 é um nogood com respeito aos limites dados pelo vetor c. de T. Novamente, ao final do laço, U 2 é um nogood, agora com respeito

	à coloração ponderada.
		O nogood retornado pelo obstáculo híbrido será aquele com o menor número
	de variáveis fixadas. Heuristicamente, o nogood com o menor número de fixações
	explora uma região maior do espaço de busca ainda não explorado.
	Algoritmo 6.17 obstáculo_hibrido(U, record, S)
	1: bound ← oraculo(U )
	2: Se w(C) > record então
	3:	record ← w(C)
	4: Se bound > record então
	10: 5: 6:	Nogood do tipo 1 Senão Se u j = 0 então R ← P
	11: 7:	
		Na segunda parte do obstáculo híbrido, procedemos de maneira semelhante,
	utilizando agora a heurística de coloração ponderada. Aplicamos a heurística de
	coloração ponderada, que devolve uma ordem de coloração π, juntamente com um
	vetor de limites superiores color. Agora o conjunto T faz o papel do conjunto R do

P ← P \ {j} ; 12: j ← max{k | ρ k ∈ P } 13: Retorne w(C) + c(ρ j ) 6.3.2 Obstáculo Híbrido No obstáculo híbrido, vamos gerar dois tipos de nogoods. O primeiro tipo de nogood é obtido utilizando como limite superior o vetor gerado pelo Algoritmo de Bonecas Russas. Analogamente ao obstáculo_modificado, o segundo tipo de nogood é obtido através da heurística de coloração. O obstáculo híbrido começa chamando o novo oráculo, que constrói os conjuntos C e P e calcula um limite superior, que será armazenado em bound. Se bound for maior que record, geramos o nogood U 1 , do primeiro tipo. O conjunto R mantém os vértices de P ainda não analisados. Iterativamente, determinamos o limite superior para a clique máxima ponderada de G[C ∪R]. Esse limite é dado pela soma de w(C) com c[max{ρ j | ρ j ∈ R}]. primeiro tipo de nogood. Enquanto o limite superior para ω(G[T ], w) for menor que record -w(C) e T = ∅, escolhemos o último vértice j ∈ T colorido pela heurística de coloração, fixamos a variável associada ao vértice j em zero em U 2 e removemos o vértice j

  Número médio de colorações ponderadas realizadas para cada grupo (n, p).

	Instância (n,p) (2500,0.10) (5000,0.10) (2500,0.20) (5000,0.20) (2500,0.30) (1200,0.40) (2500,0.40) (600,0.50) (1200,0.50) (600,0.60) (1200,0.60) (400,0.70) (500,0.70) (600,0.70) (300,0.80) (400,0.80) (200,0.90) (300,0.90) (200,0.95) (n,p) (2500,0.10) BITCLIQUE1 BITCLIQUE2 Colorações Ponderada RDS1 RDS2 1.82e+04 1.97e+04 4.75e+04 2.88e+04 4.20e+04 2.81e+04 BR1 BR2 1.79e+05 3.16e+05 2.67e+05 3.91e+05 2.46e+05 3.86e+05 1.95e+05 2.91e+05 2.83e+05 3.42e+05 2.43e+05 3.48e+05 3.82e+06 5.96e+06 5.63e+06 6.98e+06 4.75e+06 7.63e+06 3.27e+06 6.99e+06 3.46e+06 9.45e+06 2.87e+06 8.99e+06 1.00e+06 1.90e+06 1.24e+06 2.50e+06 1.02e+06 2.39e+06 6.01e+07 1.34e+08 6.32e+07 1.75e+08 4.88e+07 1.83e+08 2.65e+05 4.07e+05 3.83e+05 5.40e+05 3.03e+05 5.19e+05 1.61e+07 3.49e+07 1.58e+07 4.78e+07 1.24e+07 4.46e+07 2.90e+06 4.83e+06 3.51e+06 6.52e+06 2.58e+06 6.17e+06 5.01e+08 * 10 3.97e+08 * 10 3.01e+08 * 10 2.63e+06 3.35e+06 3.20e+06 4.91e+06 2.23e+06 4.53e+06 1.79e+07 2.84e+07 1.91e+07 3.97e+07 1.34e+07 3.69e+07 7.00e+07 1.28e+08 7.31e+07 1.82e+08 5.25e+07 1.66e+08 6.79e+06 5.95e+06 9.59e+06 8.69e+06 5.96e+06 8.25e+06 1.09e+08 1.22e+08 1.14e+08 1.88e+08 7.07e+07 1.73e+08 2.72e+06 3.40e+05 5.64e+06 5.78e+05 3.17e+06 5.36e+05 7.26e+08 1.53e+08 * 1 2.70e+08 5.03e+08 2.52e+08 1.08e+07 1.16e+05 2.98e+07 2.15e+05 1.27e+07 1.80e+05 Tempo de Execução BITCLIQUE1 BITCLIQUE2 RDS1 RDS2 BR1 BR2 0.77 0.81 0.21 0.18 0.85 0.84 (5000,0.10) 3.25 4.80 1.89 3.18 3.35 5.52 (2500,0.20) 2.00 3.07 1.12 2.30 1.89 3.63 (5000,0.20) 42.11 77.35 36.30 67.07 46.44 123.85 (2500,0.30) 23.46 50.48 15.57 51.77 16.88 73.10 (1200,0.40) 4.94 9.22 3.39 9.56 3.80 12.87 (2500,0.40) 464.34 1094.99 311.57 1090.54 336.76 1926.47 (600,0.50) 0.91 1.39 0.71 1.37 0.86 1.91 (1200,0.50) 79.12 171.66 49.72 187.34 54.19 258.82 (600,0.60) 9.54 16.46 7.35 17.66 7.82 24.72 (1200,0.60) 2730.49 > 3600 1456.73 > 3600 1645.06 > 3600 (400,0.70) 6.75 9.52 5.58 10.91 5.77 15.04 (500,0.70) 53.97 89.38 39.74 101.17 41.94 142.79 (600,0.70) 254.26 484.17 173.01 549.77 175.52 792.54 (300,0.80) 15.42 14.93 15.17 17.95 14.40 27.26 (400,0.80) 313.46 380.15 234.03 467.94 237.37 703.49 (200,0.90) 5.46 1.12 7.97 1.16 6.75 1.77 (300,0.90) 1924.74 480.46 > 3600 704.62 1629.50 1173.66 Tabela 6.10: Instância (200,0.95) 23.75 0.61 49.46 0.51 35.75 0.79

Tabela 6.11: Tempo de execução médio para cada grupo (n, p).

  Tabela 6.13 confirma que a redução do número de colorações promovida por BR1 implicou em uma redução do tempo de execução. Mostrou também que o algoritmo BR1 é bastante competitivo com os demais algoritmos que usam a mesma ordem inicial dos vértices. Já BR2 teve um comportamento muito parecido com RDS2, que por sua vez perdem para BITCLIQUE2.

	Instância	Tempo de Execução
	Nome Com relação ao número de colorações realizadas, a Tabela 6.14 mostra que BR1 (n,p) BITCLIQUER1 BITCLIQUER2 RDS1 RDS2 BR1 BR2
	sanr400 0.5 é bastante competitivo com os demais algoritmos para instâncias até 80%. Além (400,0.50) 0.17 0.18 0.12 0.13 0.19 0.22
	san1000 brock400 1 disso, BR1 reduz o número de colorações realizadas por RDS1 na maioria das (1000,0.50) 2.21 2.57 5.43 2.50 5.18 4.08 (400,0.75) 29.72 38.73 29.45 57.00 26.09 64.43
	). Quando o tempo limite é ultrapassado, tal ocorrência assinalada como * na tabela. Identificamos em negrito o melhor desempenho médio é em cada caso. A Tabela 6.12 revela que BR1 conseguiu reduzir o número de colorações ponderadas realizadas em algumas instâncias da família brock. Nas outras instâncias com densidade até 80%, o algoritmo BR1 conseguiu um número de colorações bastante próximo. Porém, BR2 não conseguiu superar os demais algoritmos em nenhuma classe de instâncias. Colorações Ponderada Nome (n,p) BITCLIQUER1 BITCLIQUER2 RDS1 RDS2 BR1 BR2 sanr400 0.5 (400,0.50) 2.39e+04 3.08e+04 5.13e+04 4.14e+04 4.06e+04 4.14e+04 san1000 (1000,0.50) 2.64e+04 2.21e+04 1.04e+05 4.53e+04 8.83e+04 5.75e+04 brock400 1 (400,0.75) 8.65e+06 1.10e+07 1.14e+07 1.99e+07 7.45e+06 1.64e+07 brock400 2 (400,0.75) 1.02e+07 1.55e+07 1.68e+07 2.73e+07 8.64e+06 2.27e+07 brock400 3 (400,0.75) 7.81e+06 1.15e+07 1.11e+07 1.55e+07 7.35e+06 1.57e+07 brock400 4 (400,0.75) 3.53e+06 5.20e+06 1.35e+07 3.27e+07 9.54e+06 2.63e+07 brock800 1 (800,0.65) 5.79e+07 1.47e+08 9.78e+07 2.65e+08 5.10e+07 2.23e+08 brock800 2 (800,0.65) 9.89e+07 2.51e+08 9.99e+07 3.50e+08 7.12e+07 3.30e+08 san400 0.7 1 (400,0.70) 2.32e+05 5.71e+05 3.85e+05 7.07e+05 2.94e+05 1.05e+06 san400 0.7 2 (400,0.70) 3.61e+05 3.99e+05 1.04e+06 2.30e+06 9.01e+05 2.11e+06 san400 0.7 3 (400,0.70) 2.72e+05 6.25e+04 1.19e+06 1.41e+05 7.56e+05 1.32e+05 p hat500-2 (500,0.50) 6.70e+04 4.12e+03 4.40e+05 7.59e+03 3.15e+05 7.57e+03 p hat700-2 (700,0.50) 2.36e+06 1.57e+04 7.07e+06 2.36e+04 2.92e+06 2.36e+04 p hat1000-2 (1000,0.49) 6.60e+07 6.48e+05 1.17e+08 9.19e+05 4.12e+07 9.17e+05 p hat1500-2 (1500,0.51) * 2.59e+07 * 3.75e+07 * 3.74e+07 p hat300-3 (300,0.74) 1.47e+05 1.50e+04 6.04e+05 2.33e+04 4.13e+05 2.33e+04 p hat500-3 (500,0.75) 5.12e+07 6.97e+05 1.03e+08 1.11e+06 5.76e+07 1.10e+06 gen200 p0.9 44 (200,0.90) 1.09e+06 6.20e+04 2.40e+06 1.41e+05 1.54e+06 1.35e+05 gen200 p0.9 55 (200,0.90) 3.13e+05 1.71e+04 5.04e+06 1.01e+05 1.62e+06 6.94e+04 gen400 p0.9 55 (400,0.90) * 5.73e+08 * * * * gen400 p0.9 65 (400,0.90) * * * * * * gen400 p0.9 75 (400,0.90) * 4.96e+07 * 7.89e+08 * 7.09e+08 C250.9 (250,0.90) 6.19e+06 9.62e+05 2.37e+07 2.55e+06 8.51e+06 2.14e+06 san200 0.9 1 (200,0.90) 1.45e+04 1.20e+02 4.67e+05 7.29e+03 2.90e+05 6.92e+03 san200 0.9 2 (200,0.90) 6.76e+04 2.85e+04 5.65e+05 3.87e+06 5.31e+05 1.83e+06 san200 0.9 3 (200,0.90) 3.14e+06 4.15e+05 6.31e+06 7.23e+05 4.69e+06 7.90e+05 san400 0.9 1 (400,0.90) 9.79e+06 * 1.05e+08 5.79e+08 1.03e+08 * sanr200 0.9 (200,0.90) 1.83e+06 2.27e+05 7.15e+06 3.63e+05 3.01e+06 3.50e+05 hamming10-2 (1024,0.99) 1.80e+01 * 3.11e+05 * 8.77e+05 * MANN a27 (378,0.99) * 1.82e+04 * 7.17e+04 * 6.64e+04 brock400 2 (400,0.75) 39.61 58.49 48.49 79.25 35.20 instâncias. Em algumas instâncias, BR1 obtém o menor número de colorações 87.13 brock400 3 (400,0.75) 30.53 43.56 30.97 49.89 25.70 77.78 brock400 4 (400,0.75) 16.29 23.02 36.38 91.16 33.07 91.82 brock800 1 (800,0.65) 400.76 946.47 428.67 1268.82 253.16 1209.56 brock800 2 (800,0.65) 640.83 1458.54 434.19 1656.72 410.82 2237.91 brock800 3 (800,0.65) 470.91 1064.17 445.39 1275.23 320.50 1436.51 brock800 4 (800,0.65) 644.40 1539.57 509.33 1759.07 461.69 2319.97 sanr400 0.7 (400,0.70) 6.26 8.90 6.56 11.68 5.98 12.46 san400 0.7 1 (400,0.70) 2.36 5.19 2.54 4.09 2.13 8.23 san400 0.7 2 (400,0.70) 3.35 4.73 6.65 16.07 6.22 19.11 san400 0.7 3 (400,0.70) 2.34 0.86 6.66 1.18 4.24 1.30 p hat1500-2 (1500,0.51) > 3600 624.42 > 3600 329.62 > 3600 335.99 p hat300-3 (300,0.74) 0.66 0.11 1.45 0.08 1.12 0.12 p hat500-3 (500,0.75) 328.54 5.17 427.52 5.58 241.42 5.91 gen200 p0.9 44 (200,0.90) 3.24 0.52 5.05 0.38 4.87 0.50 gen200 p0.9 55 (200,0.90) 1.26 0.37 9.38 0.28 3.50 0.22 gen400 p0.9 55 (400,0.90) > 3600 3595.54 > 3600 > 3600 > 3600 > 3600 gen400 p0.9 65 (400,0.90) > 3600 > 3600 > 3600 > 3600 > 3600 > 3600 gen400 p0.9 75 (400,0.90) > 3600 363.60 > 3600 3384.94 > 3600 3061.18 C250.9 (250,0.90) 21.52 4.20 59.04 8.01 28.22 8.30 san200 0.9 1 (200,0.90) 0.58 0.50 0.98 0.01 0.73 0.06 san200 0.9 2 (200,0.90) 0.55 0.49 1.05 8.09 1.20 3.88 san200 0.9 3 (200,0.90) 8.25 1.64 11.93 1.93 12.89 3.76 san400 0.9 1 (400,0.90) 78.08 > 3600 459.00 2534.88 485.89 > 3600 sanr200 0.9 (200,0.90) 4.69 1.08 13.04 0.91 8.27 1.35 hamming10-2 (1024,0.99) 0.66 > 3600 1.67 > 3600 60.89 > 3600 MANN a27 (378,0.99) > 3600 1.28 > 3600 0.30 > 3600 0.53 Tabela 6.13: Tempo de execução dos algoritmos nas instâncias DIMACS-W. ponderada dentre todas. Já BR2 não superou nenhum algoritmo com respeito ao número de colorações em nenhuma instância. A Tabela 6.15 apresenta o tempo de execução de cada algoritmo proposto. Mesmo com o número de colorações comparáveis, BR1 e BR2 tiveram um tempo de execução bastante distante dos algoritmos RDS1 e RDS2, indicando que o algoritmo de Busca por Resolução demandou um esforço computacional considerável para estas instâncias, que talvez possa ser reduzido pela combinação de outras estratégias de mergulho e recomeço. Já a Instância brock800 3 (800,0.65) 7.31e+07 1.79e+08 1.04e+08 2.73e+08 6.12e+07 2.36e+08 brock800 4 (800,0.65) 1.07e+08 2.75e+08 p hat500-2 (500,0.50) 0.59 0.10 1.78 0.03 1.52 0.08 Instância (n,p) Colorações Ponderadas 1.18e+08 3.94e+08 8.33e+07 3.63e+08 sanr400 0.7 (400,0.70) 1.68e+06 2.39e+06 p hat1000-2 (1000,0.49) 750.75 10.09 1055.14 5.70 361.84 5.51 2.81e+06 4.00e+06 2.06e+06 3.52e+06 p hat700-2 (700,0.50) 19.67 0.29 45.71 0.13 19.62 0.20 BITCLIQUER1 BITCLIQUER2 RDS1 RDS2 BR1 BR2

Tabela 6.12: Número médio de colorações ponderadas realizadas pelo algoritmo nas instâncias DIMACS-W.

EXACTCOLOR

Para as instâncias EXACTCOLOR, o tempo limite para a resolução de cada instância é 2h (7200s). Quando o tempo limite é ultrapassado, tal ocorrência é assinalada como * na tabela. Identificamos em negrito o melhor desempenho em cada caso.

  Número de colorações ponderadas para cada instância EXACTCOLOR Tempo de execução dos algoritmos para cada instância EXACTCOLOR.Neste capítulo, apresentamos o método de Busca por Resolução proposto em[Chvátal 1997]. Depois, mostramos como usar a heurística BITCOLOR no procedimento obstáculo para obter um nogood. Em seguida, realizamos alguns testes computacionais para justificar a nossa escolha para a política de recomeço. O algoritmo obtido realizou menos chamadas ao oráculo que o Algoritmo BITCLIQUE, que utiliza a mesma ordem; Todavia essa redução não resultou em uma diminuição no tempo de execução, sugerindo que a "gerência" do método demandou grande esforço computacional. Com a perspectiva de melhorarmos o desempenho, pensamos em uma cooperação entre o algoritmo de Bonecas Russas e Busca por Resolução. Essa cooperação mostrou-se bem sucedida em reduzir o número de chamadas à heurística de coloração ponderada em comparação ao algoritmo de Bonecas Russas. Porém, o tempo de execução não acompanhou essa redução, indicando que o algoritmo de Busca por Resolução demandou um esforço computacional considerável para estas instâncias, que talvez possa ser reduzido pela combinação de outras estratégias de mergulho e recomeço. proposição de algoritmos cada vez mais eficientes para CLIQUE PONDERADA é um imperativo dada a sua importância e recorrência. Um exemplo disso acontece no processo de geração de colunas para a coloração de grafos. Neste caso, métodos exatos e heurísticas são utilizados para a resolução consecutiva de várias instâncias de CLIQUE PONDERADA [Mehrotra e Trick 1996, Gualandi e Malucelli 2012, Held, Cook e Sewell 2012]. Note que pequenos ganhos em desempenho são potencializados dada a recorrência do problema. A partir dessa motivação, apresentamos três algoritmos exatos para CLIQUE PONDERADA usando abordagens diferentes. O primeiro algoritmo, denominado BITCLIQUE, mostrou-se mais eficiente que os demais algoritmos do estado da arte. Seu melhor desempenho ocorre em grafos com a densidade superior ou igual 90%. Nesta faixa, a variante BITCLIQUE2 obteve os melhores resultados. O segundo algoritmo, denominado BITRDS, pode ser entendido como uma extensão do algoritmo CLIQUER, incorporando uma estratégia de poda e ramificação baseada na coloração ponderada. Nos testes computacionais realizados, CLIQUER confirmou a sua eficiência para grafos esparsos, com a densidade entre 10% e 40%. Por outro lado, para grafos com a densidade entre 50% e 80%, a variação BITRDS1 apresentou o melhor desempenho computacional nas instâncias analisadas. Por fim, apresentamos um algoritmo híbrido, denominado BITBR, que combina o método de Bonecas Russas e o método de Busca por Resolução. Essa integração é apresentada e testada pela primeira vez neste trabalho. O novo algoritmo consegue reduzir o número de chamadas à heurística de coloração ponderada, que é o procedimento mais dispendioso do processo. Porém, o tempo de execução não é reduzido. Acreditamos que o esforço computacional do método de Busca por Resolução possa ser decrescido com o desenvolvimento de novas estratégias de mergulho e recomeço mais apropriadas.Os algoritmos apresentados nesta tese abre várias direções de pesquisas promissoras. Uma delas é a utilização dos algoritmos em problemas que exijam a resolução de várias instâncias de CLIQUE PONDERADA, como ocorre no processo de geração de colunas ou na geração de cortes de cliques para problemas de programação inteira.Outro rumo é o desenvolvimento de algoritmos de Bonecas Russas para diversas variações do problema da clique[McClosky e Hicks 2012, Trukhanov et al. 2013, Gschwind et al. 2015[START_REF] Miao | An exact algorithm for the maximum probabilistic clique problem[END_REF], Malladi 2014]. Uma vez que vimos que o algoritmo de Bonecas Russas pode incorporar com sucesso novas estratégias de poda e ramificação.

	DSJR500.1c r1000.1c DSJC250.9 DSJC500.9 DSJC1000.9 DSJC250.5 DSJC500.5 DSJC1000.5 C2000.5.1029 flat300 28 0 flat1000 50 0 flat1000 60 0 flat1000 76 0 school1 DSJC250.1 DSJC500.1.117 DSJC1000.1.3915 (998,0.90) (189,0.02) (511,0.03) (250,0.10) (500,0.10) (1000,0.10) (250,0.50) (500,0.50) (1000,0.50) (2000,0.50) (300,0.52) (967,0.51) (999,0.51) (1000,0.51) (336,0.71) (241,0.89) (494,0.90) 2-Insertions 4 (149,0.95) 1-Insertions 6 (527,0.96) 2-Insertions 5 (369,0.97) 3-Insertions 4 (208,0.97) 4-Insertions 4 (295,0.98) 3-Insertions 5 (460,0.98) (n,p) latin square 10 (90,0.00) r1000.5 (234,0.00) DSJR500.1c (189,0.02) r1000.1c (511,0.03) DSJC250.9 (250,0.10) DSJC500.9 (500,0.10) DSJC1000.9 (1000,0.10) DSJC250.5 (250,0.50) flat300 28 0 (300,0.52) flat1000 50 0 (967,0.51) flat1000 60 0 (999,0.51) flat1000 76 0 (1000,0.51) school1 (336,0.71) DSJC250.1 (241,0.89) DSJC500.1.117 (494,0.90) DSJC1000.1.3915 (998,0.90) 2-Insertions 4 (149,0.95) 1-Insertions 6 (527,0.96) 2-Insertions 5 (369,0.97) 3-Insertions 4 (208,0.97) 4-Insertions 4 (295,0.98) 3-Insertions 5 (460,0.98) Tabela 6.15: 6.4 Conclusão Capítulo 7 Tabela 6.14: Instancia DSJC500.5 (500,0.50) DSJC1000.5 (1000,0.50) C2000.5.1029 (2000,0.50) Conclusão e Direções Futuras 4.60e+01 4.10e+01 1.31e+02 1.77e+02 1.32e+02 1.78e+02 3.76e+02 3.56e+02 7.33e+02 6.29e+02 7.30e+02 6.30e+02 4.07e+02 4.04e+02 4.87e+02 4.49e+02 4.88e+02 4.50e+02 1.96e+03 1.95e+03 2.06e+03 2.00e+03 2.06e+03 2.00e+03 1.28e+04 1.42e+04 1.31e+04 1.44e+04 1.31e+04 1.44e+04 5.18e+04 5.23e+04 5.65e+04 5.29e+04 5.60e+04 5.29e+04 2.22e+06 2.26e+06 2.24e+06 2.28e+06 2.23e+06 2.28e+06 1.80e+08 1.83e+08 1.78e+08 1.83e+08 1.77e+08 1.83e+08 * * * * * * 1.91e+05 2.01e+05 1.98e+05 2.05e+05 1.97e+05 2.05e+05 9.68e+06 2.00e+07 7.72e+06 2.28e+07 7.31e+06 2.25e+07 4.50e+07 6.55e+07 3.45e+07 7.08e+07 3.25e+07 7.07e+07 2.30e+08 2.30e+08 2.25e+08 2.30e+08 2.24e+08 2.30e+08 3.05e+05 1.14e+05 4.03e+05 1.28e+05 3.73e+05 1.68e+05 3.34e+08 2.75e+08 5.77e+08 3.85e+08 4.60e+08 3.98e+08 * * * * * * * * * * * * 1.53e+04 6.86e+04 2.14e+04 7.16e+04 2.10e+04 7.15e+04 1.17e+05 2.06e+06 2.23e+07 4.60e+06 1.95e+07 4.15e+06 9.38e+05 9.78e+05 1.46e+07 7.12e+05 1.02e+07 7.18e+05 2.99e+05 7.68e+03 2.34e+06 1.85e+04 1.54e+06 1.62e+04 6.83e+05 1.38e+07 1.10e+07 5.18e+06 8.16e+06 5.20e+06 2.18e+08 * * 3.93e+07 * 3.97e+07 Tempo de Execução BITCLIQUER1 BITCLIQUER2 RDS1 RDS2 BR1 BR2 0.08 0.09 0.00 0.00 0.09 0.08 0.18 0.18 0.00 0.00 0.19 0.19 0.16 0.15 0.00 0.00 0.15 0.16 0.16 0.16 0.00 0.00 0.16 0.25 0.07 0.07 0.00 0.00 0.07 0.07 0.22 0.15 0.01 0.01 0.20 0.14 0.29 0.28 0.03 0.03 0.30 0.29 0.10 0.10 0.05 0.05 0.14 0.14 0.30 0.30 0.21 0.21 0.46 0.54 58.27 103.87 36.44 103.99 55.08 153.28 194.60 252.23 130.11 245.43 219.94 410.02 586.53 572.81 534.42 530.53 1132.91 1095.70 2.45 0.67 3.21 0.62 3.86 1.42 717.33 592.85 1059.60 753.20 1522.98 1750.34 * * * * * * * * * * * * 0.20 0.30 0.03 0.11 0.10 0.38 1.78 24.36 156.03 50.89 136.31 71.81 7.03 6.53 74.19 4.32 66.45 8.10 1.09 0.26 4.85 0.04 7.01 0.09 4.16 67.19 42.54 25.57 41.38 56.44 1887.79 * * 404.22 * 693.26 3.26 3.30 3.33 3.27 6.02 5.64 449.52 458.15 423.38 422.89 873.09 853.38 * * * * * *

A

  Poggi 2015], um procedimento de construção do grafo de conflitos é apresentado. Com esse procedimento, os autores geraram um total de 7292 instâncias, sendo 399 instâncias a partir do conjunto MIPLIB, 3804 de INRC, 3085 de Telebus e 4 de Uchoa . A Tabela A.1 mostra a densidade mínima, máxima e média dos grafos de conflitos. . Densidade mínima, máxima e média das instâncias do problema de detecção de cliques A Tabela A.2 mostra o tempo reportado em [Boas, Santos e Brito 2015] para enumeração de todas as cliques violadas para todas as instâncias de cada grupo. Tabela A.2: Tempo para enumerar todas as cliques violadas para todas as instâncias de cada grupo [Boas, Santos e Brito 2015]Propomos aqui uma variante do Algoritmo de BK, denominada BITBKC, que utiliza a heurística de coloração ponderada como procedimento de limite superior e como estratégia de pivoteamento. Além disso, o conjunto P e X são representado por vetores de bits(bitmap). A ordem inicial ρ é a ordem não decrescente dos grau modificados. No algoritmo original BK, em cada chamada recursiva, a ordem em que os vértices de P são escolhidos para entrar na clique atual C não é especificada.Nessa versão, seguimos a ordem inicial dos vértices ρ. A estratégia de pivoteamento utilizada será escolher o último vértice colorido pela heurística de coloração como pivô (Ver Algoritmo A.3). As instruções em caixas são aquelas simplificadas pela utilização de vetores de bits.

	Algoritmo A.3 Algoritmo BITBKC MIPLIB INRC Telebus Uchoa 1: função MAIN
	2:	Densidada Mínima 0.01	0.01	0.01	0.11
		Densidade Máxima 0.84	0.07	0.37	0.21
		Densidade Média	0.14	0.01	0.04	0.16
	Tabela A.1: MIPLIB INRC Telebus Uchoa
		Tempo de Execução			
		em segundos	65.25	54.17	39.17	18.75

  BITBKA foi mais efetivo que BITBKC no grupo de instâncias INRC, Telebus e Uchoa, tendo acontecido a situação inversa nas instâncias MIPLIB. Isso indica que a estratégia de pivoteamento de BITBKC foi mais efetiva que a de BITBKA para instâncias MIPLIB.

		MIPLIB INRC Telebus Uchoa
	BKA	78.75	71.44	67.19	25.04
	BKC	7.89	60.64	34.63	3.82
	BITBKA 17.56	31.67 23.97	2.81

13:

X ← X ∪ {v} A Tabela A.4 mostra que tanto BITBKC quanto BITBKA reduziram o tempo para enumerar todas as cliques em relação ao algoritmo BKA. Além disso,

  Tabela A.8). O algoritmo BITCLIQUE1 teve o melhor desempenho em três das quatro instâncias do conjunto.Na próxima seção, comparamos o desempenho computacional do algoritmo BITRDS1 e BITBKA M AX em grafos gerados aleatoriamente. Resultados computacionais para instâncias UCHOAD Testes com Grafos AleatóriosEm nosso experimento, geramos 10 grafos aleatórios para cada combinação n (número de vértices) e p (probabilidade de existência de cada aresta). Os pesos são distribuídos uniformemente entre 1 e 10. Consideramos 8 combinações, levando a 80 instâncias no total. Para cada par (n, p), calculamos a média do tempo consumido pelas 10 instâncias para cada algoritmo. O número de vértices varia entre 600 até 5000, enquanto a densidade varia entre 10% e 60%. A comparação computacional entre BITRDS1 e BITBKA M AX nas instâncias aleatórias é apresentada na Tabela A.9, mostrando que, para essa faixa de densidade e dimensão do problema, a segunda abordagem (de enumeração "exaustiva" das cliques maximais) não é competitiva.

	Número de			
	Instância	vértices	densidade BKA M AX BIT BKA M AX BITRDS1
	pdistuchoa cut 1 500	0.211	0.73	0.08	0.01
	pdistuchoa cut 2 310	0.116	0.009	0.002	0.003
	pdistuchoa cut 3 371	0.145	0.030	0.015	0.007
	pdistuchoa cut 4 428	0.169	0.064	0.025	0.010
	Total			0.83	0.12	0.03
	Número de Instâncias densidade < 0.1 275 densidade ≤ 0.5 79 densidade > 0.5 45 Total Tabela A.5: Resultados computacionais para instâncias MIPLIB Média de número de vértices BKA M AX BIT BKA M AX BITRDS1 807.37 7.52 2.30 5.17 2810.46 2.38 1.34 0.56 75.64 0.19 0.084 0.13 10,09 3.72 5.86 Número de Instâncias Média de número de vértices BKA M AX BIT BKA M AX BITRDS1 densidade < 0.1 3804 820.07 61.27 27.66 56.47 Tabela A.6: Resultados computacionais para instâncias INRC Tabela A.8: Instancia Tempo de Execução
		(n,p)		
	Número de	Média de número	
	Instâncias	de vértices	BKA M AX BIT BKA M AX BITRDS1
	densidade < 0.1 2821	686.93		64.14	21.71	31.82
	densidade ≤ 0.5 254		7656.38		0.11	0.11	0.19
	Total				64.25	21.82	32.01
	Tabela A.7: Resultados computacionais para instâncias Telebus