Universidade Federal do ABC - Pós

Transcrição

UNIVERSIDADE FEDERAL DO ABC
Centro de Matemática, Computação e Cognição (CMCC)
Curso de Pós-Graduação em Ciência da Computação
Dissertação de Mestrado
Eduardo Batista Gomes Moreira
ALGORITMOS PARALELOS EM GPUS PARA PROBLEMAS DE
PROGRAMAÇÃO QUADRÁTICA BINÁRIA IRRESTRITA
Santo André - SP
2013
Dissertação de Mestrado
Trabalho apresentado como requisito parcial
para obtenção do tı́tulo de Mestre em Ciência
da Computação, sob orientação do Prof. Dr.
Cláudio Nogueira de Meneses.
Santo André - SP
2013
Este exemplar foi revisado e alterado em relação à versão original,
de acordo com as observações levantadas pela banca no dia da defesa, sob responsabilidade única do autor e com a anuência de seu
orientador.
Santo André, 21 de outubro de 2013.
Assinatura do autor:
Assinatura do orientador:
Centro de Matemática, Computação e Cognição (CMCC)
Outubro de 2013
BANCA EXAMINADORA:
• Prof. Dr. Cláudio Nogueira de Meneses (Presidente)
(CMCC) Universidade Federal do ABC - UFABC
• Prof. Dr. Alexandre Cláudio Botazzo Delbem
(ICMC) Universidade de São Paulo - USP
• Prof. Dr. Raphael Yokoingawa de Camargo
• Prof. Dr. Daniel Morgato Martin (Suplente)
• Prof.a Dr.a Maristela Oliveira dos Santos (Suplente)
(ICMC) Universidade de São Paulo - USP
Este trabalho contou com o auxı́lio financeiro das seguintes entidades:
• Universidade Federal do ABC - UFABC (bolsa de mestrado, institucional), de outubro/2011 a março/2012;
• Coordenação de Aperfeiçoamento de Pessoal de Nı́vel Superior - CAPES (bolsa de
mestrado, demanda social), de abril/2012 a maio/2012;
• Fundação de Amparo à Pesquisa do Estado de São Paulo - FAPESP (bolsa de
mestrado), de junho/2012 a maio/2013.
Resumo
Consideramos o problema de otimização global: maximize f (x) = xT Qx, onde x ∈ {0, 1}n
e Q é uma matriz assimétrica de dimensão n × n com coeficientes racionais. Este problema é comumente denominado problema de programação quadrática binária irrestrita
(em inglês, Unconstrained binary Quadratic Problem - UQP) e tem sido muito estudado
nos últimos 50 anos. Este problema tem diversas aplicações. Em economia, um exemplo
bem conhecido é o de determinar um portfólio de investimento; uma aplicação tı́pica em
estatı́stica é o problema de regressão linear; em otimização combinatória, uma aplicação
é o problema de encontrar um clique máximo em um grafo. Nosso estudo se concentra:
(1) no desenvolvimento de implementações paralelas de métodos heurı́sticos e exatos, que
objetivam resolver instâncias do UQP e (2) na criação de fórmulas para recalcular o valor
função objetivo, visto que o desempenho das implementações dependem significativamente
da quantidade de vezes que o valor da função objetivo é calculado. As implementações
usam unidades de processamento gráfico (em inglês, Graphics Processing Units - GPUs)
e o ambiente de programação CUDA (Compute Unified Device Architecture). GPUs são
dispositivos do tipo SIMT (Single Instruction, Multiple Thread) em computação paralela.
Nossos resultados computacionais sobre instâncias do UQP, obtidas da literatura, evidenciam a robustez e eficácia das nossas abordagens. Com os métodos heurı́sticos tentamos
resolver instâncias com até 2.500 variáveis e com o método exato foi possı́vel resolver
instâncias com até 100 variáveis.
2
Abstract
We consider the global optimization problem: maximize f (x) = xT Qx, where x ∈ {0, 1}n
and Q is an asymmetric (n × n)-matrix with rational coefficients. This problem is commonly known as unconstrained binary quadratic problem (UQP) and has been studied for
at least 50 years. It has many diverse applications. In economics, a well-known example arises from portfolio theory; a typical application in statistics is the linear regression
problem; in combinatorial optimization, an application is the problem of finding a maximum clique in a graph (the maximum clique problem). Our work focus on: (1) parallel
implementations of heuristic and exact methods to solve the UQP and (2) finding closed formulae to recompute the objective function values, since the performance of the
implementations depend on the number of times the objective function value is computed. The implementations use modern programmable Graphic Processing Units (GPU)
and the NVIDIA’s GPU programming framework, “Compute Unified Device Architecture”
(CUDA). GPUs are SIMT (Single Instruction, Multiple Thread) devices that are dataparallel. Our computational results were done over a number of publically available data
sets. The heuristics methods were tested on instances involving up to 2,500 variables and
the exact method was able to solve instances with up to 100 variables.
3
Agradecimentos
Expressar meus sentimentos de gratidão de forma adequada a todos que os merecem,
requerem palavras e ações que não cabem no papel. Os próximos parágrafos mostram
uma tentativa de sintetizar estes sentimentos.
Agradeço a Deus pela minha saúde e pela oportunidade de continuar meus estudos.
Agradeço profundamente a minha mãe, Angela, ao meu pai, Orlando, e a minha irmã,
Dayane, pelo amor e carinho que sempre me deram, pela motivação, compreensão e apoio
nos momentos mais difı́ceis e por todos momentos que passamos juntos. Viram, batalhei
e consegui! Obrigado por sempre depositarem suas esperanças em mim.
Agradeço imensamente ao Prof. Cláudio Meneses pelos ensinamentos, ajuda e colaboração com o meu trabalho, pelas conversas e conselhos ao longo do perı́odo do mestrado,
mas acima de tudo, por ser um amigo.
A todos os professores pelas novas experiências, pelos desafios que me foram apresentados e pelos conhecimentos adquiridos. Em especial aos professores Daniel Martin,
Raphael Camargo, Ronaldo Prati e Siang Song.
A meus amigos Fábio Beraldo, Omar Latorre e Grasielle Roberta por sempre me
motivar e torcer por mim.
Aos amigos do Clube de Anime da UFABC pelos momentos agradáveis que passamos
juntos.
Agradeço a CAPES, FAPESP e UFABC pelos financiamentos, em bolsas, para o desenvolvimento desta pesquisa.
E por fim, agradeço a todos que um dia acreditaram em mim.
4
Sumário
1 Introdução
16
2 Definições
20
2.1
Definições Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2
Definições sobre Computação Paralela
3 Trabalhos Anteriores
. . . . . . . . . . . . . . . . . . . . 23
26
3.1
Programação Quadrática . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2
Programação Quadrática Binária Irrestrita . . . . . . . . . . . . . . . . . . 27
3.3
Artigos na Literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.1
Métodos Heurı́sticos . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.2
Métodos Exatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4
UQP Linearizado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.5
Lista de Problemas Modelados na Forma UQP . . . . . . . . . . . . . . . . 30
3.6
Transformações Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.7
Problemas de Otimização Combinatória Modelados na Forma UQP . . . . 34
3.7.1
Empacotamento de Conjuntos (Set Packing Problem) . . . . . . . . 34
3.7.2
Particionamento de Conjuntos (Set Partitioning) . . . . . . . . . . 36
3.7.3
Coloração de Vértices em um Grafo com no máximo K Cores (KColoring) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.7.4
Conjunto Independente Generalizado (Generalized Independent Set
Problem) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.7.5
Carregamento de Objetos em Estrados (Manufacturer’s Pallet Loading Problem) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5
SUMÁRIO
3.8
3.9
6
Métodos Heurı́sticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.8.1
Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.8.2
Busca Local
3.8.3
Variable Neighborhood Search . . . . . . . . . . . . . . . . . . . . . 46
3.8.4
Gradient Midpoint Method . . . . . . . . . . . . . . . . . . . . . . . 46
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Métodos Exatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.9.1
Limitantes e Regras para Determinar Valores das Variáveis em uma
Solução Ótima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.9.2
Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4 Programação Paralela com GPUs
55
4.1
CPUs e GPUs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2
Multicore e Manycore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3
Histórico das GPUs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4
Arquitetura CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.5
Arquitetura Kepler GK104 . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.5.1
Visão Geral da Arquitetura Kepler . . . . . . . . . . . . . . . . . . 59
4.6
Memórias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.7
Limitações da Arquitetura CUDA . . . . . . . . . . . . . . . . . . . . . . . 62
4.8
Compilação do Código em CUDA . . . . . . . . . . . . . . . . . . . . . . . 63
4.9
Linguagem OpenCL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5 Contribuições e Implementações Paralelas
5.1
65
Cálculos do Valor da Função Objetivo e Limitantes Inferiores . . . . . . . . 65
5.1.1
Cálculo do Valor da Função Objetivo na Forma Básica . . . . . . . 66
5.1.2
Recálculo do Valor da Função Objetivo com Mudança do Valor de
Uma Variável . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.1.3
Recálculo do Valor da Função Objetivo com Mudança do Valor em
Duas Variáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.1.4
Cálculos do Limitante Inferior à f (x) no Branch and Bound . . . . 73
SUMÁRIO
5.1.5
5.2
7
Resumo dos Métodos de Cálculo e Recálculo do Valor da Função
Objetivo e do Limitante Inferior à f (x) . . . . . . . . . . . . . . . . 81
Implementações Paralelas . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.2.1
Tabu Search na Forma Paralela . . . . . . . . . . . . . . . . . . . . 82
5.2.2
Branch and Bound na Forma Paralela . . . . . . . . . . . . . . . . . 87
6 Experimentos Computacionais
102
6.1
Ambiente dos Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.2
Instâncias de Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.3
6.4
6.2.1
Instâncias da OR Library
. . . . . . . . . . . . . . . . . . . . . . . 103
6.2.2
Classe Difı́cil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Resultados Obtidos por Heurı́sticas . . . . . . . . . . . . . . . . . . . . . . 104
6.3.1
Comparação entre as implementações do Tabu Search e do VNS . . 105
6.3.2
Comparações entre as implementações do Tabu Search Sequencial e
Paralelo utilizando Recálculo com Mudança de uma Variável . . . . 106
6.3.3
Comparações entre as implementações do Tabu Search Sequencial e
Paralelo com Cálculo do Valor da Função Objetivo na Forma Básica 110
Resultados Obtidos pelos Métodos Exatos . . . . . . . . . . . . . . . . . . 113
6.4.1
Resultados com o Solver CPLEX . . . . . . . . . . . . . . . . . . . 113
6.4.2
Comparações entre as implementações do Branch and
Bound Sequencial e Paralelo com Cálculo do Valor da Função Objetivo na Forma Básica . . . . . . . . . . . . . . . . . . . . . . . . . 114
7 Comentários Finais e Trabalhos Futuros
120
7.1
Comentários Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
7.2
Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Lista de Figuras
3.1
Grafo de Exemplo para o Problema de Coloração em Vértices . . . . . . . 40
3.2
Grafo de Exemplo para o Problema do Conjunto Independente Generalizado 42
3.3
Iterações de um Tabu Search para a instância no Exemplo 3.5 . . . . . . . 45
3.4
Exemplo de uma árvore de enumeração do Branch and Bound . . . . . . . 53
4.1
Multicore e Manycore. Fonte: NVIDIA [42] . . . . . . . . . . . . . . . . . . 56
4.2
Evolução das GPUs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3
GeForce GTX 680 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4
Diagrama da arquitetura Kepler GK104 . . . . . . . . . . . . . . . . . . . 60
4.5
Compilação de código CUDA . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1
Índices da matriz Q para o cálculo de f (y) . . . . . . . . . . . . . . . . . . 72
5.2
Comparação entre os valores de g1 (x) e g2 (x) ao longo da execução do
Branch and Bound para a instância bqp50.6 . . . . . . . . . . . . . . . . . 77
5.3
Acesso a i-ésima linha e coluna da matriz Q . . . . . . . . . . . . . . . . . 87
5.4
Exemplo de operação de redução . . . . . . . . . . . . . . . . . . . . . . . 88
5.5
Matriz Linearizada Alocada com o Comando cudaMallocPitch . . . . . . . 93
5.6
Armazenamento da Pilha em Memória . . . . . . . . . . . . . . . . . . . . 96
6.1
Comparação entre as implementações sequencial e paralela do Tabu Search,
com recálculo do valor da função objetivo. . . . . . . . . . . . . . . . . . . 106
6.2
Métrica speedup para a implementação do Tabu Search, com recálculo do
valor da função objetivo com mudança no valor de uma variável. . . . . . . 109
6.3
Métrica speedup para a implementação do TS com cálculo do valor da
função objetivo na forma básica. . . . . . . . . . . . . . . . . . . . . . . . . 112
8
LISTA DE FIGURAS
9
6.4
Speedup da implementação do B&B para instâncias da OR Library. . . . . 116
6.5
Speedup da implementação do B&B para instâncias da classe difı́cil. . . . . 117
6.6
Número de subproblemas resolvidos na implementação do B&B para instâncias da classe difı́cil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Lista de Tabelas
4.1
Detalhes da arquitetura Kepler GK104. . . . . . . . . . . . . . . . . . . . . 60
4.2
Detalhes das Memórias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.1
Resumo do número de operações nos recálculos do valor da função objetivo. 81
5.2
Resumo do número de operações nos recálculos do valor do limitante inferior
à f (x). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.1
Densidades das instâncias do UQP. . . . . . . . . . . . . . . . . . . . . . . 104
6.2
Comparação entre valores de soluções ótimas e de soluções obtidas por
metaheurı́sticas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.3
Comparação entre valores de soluções obtidas por metaheurı́sticas, considerando as implementações sequenciais. . . . . . . . . . . . . . . . . . . . . 107
6.4
Comparação entre as implementações sequencial e paralela do Tabu Search,
com recálculo do valor da função objetivo com mudança no valor de uma
variável. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.5
Métricas para o TS com Recálculo com Mudança de uma Variável. . . . . . 108
6.6
Valores utilizados para os cálculos nas Lei de Amdahl da Tabela 6.5. Os
tempos são dados em milissegundos. . . . . . . . . . . . . . . . . . . . . . . 110
6.7
Comparação entre as Implementações Sequencial e Paralela do TS com
cálculo do valor da função objetivo na forma básica. . . . . . . . . . . . . . 111
6.8
Métricas para o TS com cálculo do valor da função objetivo na forma básica.111
6.9
Métricas para o TS com cálculo do valor da função objetivo na forma básica
com memória compartilhada. . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.10 Lei de Amdahl para o TS com cálculo do valor da função objetivo na forma
básica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.11 Valores utilizados na Tabela 6.10 para o cálculo dos valores na Lei de Amdahl.113
10
LISTA DE TABELAS
11
6.12 Soluções e tempos obtidos pelo CPLEX. . . . . . . . . . . . . . . . . . . . 114
6.13 Médias e desvios padrão dos tempos de execução do CPLEX. . . . . . . . . 114
6.14 Resultados das implementações sequencial e paralelo do método Branch
and Bound, com cálculo do valor da função objetivo na forma básica. . . . 116
6.15 Métricas para o B&B com cálculo do valor da função objetivo na forma
básica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
Lista de Algoritmos
3.8.1 Pseudo-código do método básico do Tabu Search para o UQP . . . . . . . . 44
3.8.2 Pseudo-código da busca local TS do Algoritmo 3.8.1 . . . . . . . . . . . 46
3.8.3 Pseudo-código do método básico do VNS
. . . . . . . . . . . . . . . . . . . 47
3.8.4 Pseudo-código da busca local VNS do Algoritmo 3.8.3 . . . . . . . . . . 47
3.8.5 Gradient Midpoint Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.9.1 Método Branch and Bound com busca em profundidade . . . . . . . . . . . 54
5.2.1 Pseudo-código do método Tabu Search paralelo com GPUs . . . . . . . . . 83
5.2.2 Pseudo-código do Kernel do Tabu Search . . . . . . . . . . . . . . . . . . . . 84
5.2.3 Pseudo-código do ReductionMax no Kernel do Tabu Search . . . . . . . . . 84
5.2.4 Pseudo-código do método Branch and Bound em paralelo com GPUs . . . . 90
12
Lista de Códigos-Fonte
5.1
Cópias de Dados e Chamada do Kernel no Tabu Search . . . . . . . . . . . 85
5.2
Kernel do Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.3
Função ReductionMax() . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.4
Cópias de Dados e Chamada do Kernel no Branch and Bound . . . . . . . 92
5.5
Kernel do Branch and Bound Parte 1 . . . . . . . . . . . . . . . . . . . . . 94
5.6
5.7
5.8
5.9
5.10 Função calculaBounds do Kernel no Branch and Bound . . . . . . . . . . . 99
5.11 Função calculaG cuda do Kernel no Branch and Bound . . . . . . . . . . . 100
5.12 Função calculaG aux cuda do Kernel no Branch and Bound . . . . . . . . 101
13
Lista de Sı́mbolos
Sı́mbolo
Descrição
U
Conjunto universo
N
Conjunto dos números naturais
N∗
Conjunto dos números naturais excluindo o zero
Q
Conjunto dos números racionais
Q∗+
Conjunto dos números racionais positivos
Qm×n
R
Conjunto das matrizes de coeficientes racionais de dimensões m × n
Conjunto dos números reais
∂f (x)
∂xi
Derivada parcial da função f (x) com relação a variável xi
∇f (x)
Vetor gradiente da função f (x)
0
Vetor nulo 0T = [0, 0, . . . , 0]
1
Vetor unitário 1T = [1, 1, . . . , 1]
x∗
Solução viável ótima
14
Lista de Siglas
Sigla
B&B
Descrição
Branch and Bound
CPLEX
Solver da IBM
CUDA
Compute Unified Device Architecture
MIP
Módulo de Programação Linear Inteira Mista do CPLEX
QIP
Módulo de Programação Quadrática Inteira do CPLEX
TS
Tabu Search
VNS
Variable Neighborhood Search
UQP
Unconstrained binary Quadratic Program
15
Capı́tulo 1
Introdução
Conforme Bixby [12], um problema de otimização combinatória é definido da seguinte
maneira: Sejam E um conjunto finito, S uma famı́lia de subconjuntos de E e w ∈ R|E|
uma função peso de valores reais definida sobre os elementos de E. O problema de
otimização combinatória associado à tripla (E, S, w) é encontrar um conjunto S ∗ ∈ S tal
que
w(S ∗ ) = max w(S)
S∈S
onde w(S) =
P
w(e).
e∈S
Problemas de otimização combinatória são estudados em várias áreas de conhecimento
como engenharia, administração, logı́stica, economia, biologia, finanças, marketing, planejamento entre outras. Estas áreas estudam maneiras para otimizar suas operações,
mas comumente encontram dificuldades em aplicar os modelos desenvolvidos a problemas
reais, pois estes envolvem muitas variáveis de decisão. Com o avanço da informática,
os computadores tornaram-se ferramentas indispensáveis para a realização dos inúmeros
cálculos, que a resolução dos problemas de otimização combinatória requerem.
Um problema de muito interesse na área de otimização combinatória é o de empacotar
itens (caixas) em objetos maiores (pallets). O manufacturer’s pallet loading problem é o
problema de empacotar itens de dimensões idênticas. Este problema é equivalente ao de
encontrar um conjunto independente máximo em um grafo finito particular. Conforme
descrito na Seção 3.7.5, este pode ser posto na forma UQP.
Um problema de otimização combinatória pode, normalmente, ser modelado de diversas maneiras. Para cada modelo podem existir várias técnicas que melhor o resolve.
Cabe à pessoa que está solucionando o problema decidir qual técnica e modelo utilizar.
Estas várias possibilidades podem tornar difı́cil o processo de resolução do problema.
Portanto, seria interessante desenvolver um modelo unificado, que pudesse representar
diversos problemas de otimização combinatória. Um modelo deste tipo existe e é definido
16
CAPÍTULO 1. INTRODUÇÃO
17
como segue. O problema quadrático binário irrestrito (em inglês, Unconstrained binary
Quadratic Program - UQP) pode ser escrito na forma:
max f (x) = xT Qx
sujeito a:
x ∈ {0, 1}n
onde Q ∈ Qn×n e f : {0, 1}n → Q. Por Q e Qn×n queremos dizer: o conjunto dos
números racionais e o conjunto das matrizes de coeficientes racionais de dimensão n × n,
respectivamente. Outros sı́mbolos utilizados nesta dissertação aparecem na Tabela de
Sı́mbolos na Página 15.
Em termos de complexidade computacional, o UQP pertence a classe NP-difı́cil [50].
Conforme dito em [10], este problema recebe vários nomes na literatura, a saber:
1.
2.
3.
4.
5.
6.
7.
Unconstrained Quadratic Bivalent Programming Problem;
Unconstrained Quadratic Zero-One Programming Problem;
Quadratic Zero-One Programming Problem;
Unconstrained Pseudo-Boolean Quadratic Problem;
Unconstrained Pseudo-Boolean Quadratic Zero-One Programming Problem;
Boolean Quadratic Programming Problem;
Binary Quadratic Program.
As primeiras publicações sobre o UQP apareceram na década de 1960 [23]. Desde lá
foram encontrados diversos problemas que podem ser modelados na forma desse problema.
Alguns exemplos são: resolução de problemas de satisfatibilidade [13], predição de ataques
epiléticos [30], determinação de cliques máximos em grafos [13, 45, 46] e escalonamento
de máquinas [8].
Existem vários métodos que resolvem (i.e. métodos exatos), ou tentam resolver (i.e.
métodos heurı́sticos), instâncias do UQP. Neste trabalho, desenvolvemos versões sequenciais e paralelas de implementações de métodos para o UQP. As versões paralelas utilizam
unidades de processamento gráfico (em inglês, Graphics Processing Units - GPUs) da NVIDIA e a arquitetura CUDA. GPUs são dispositivos com muitos núcleos de processamento,
que podem ser utilizados para processamento paralelo.
Devido a escassez de estudos neste tema, que é investigar o desempenho de implementações de métodos para resolver o UQP com GPUs, estabelecemos os seguintes objetivos
nesta pesquisa:
• Criar implementações sequenciais de heurı́sticas e de métodos exatos para resolver
o UQP;
18
• Criar implementações paralelas utilizando GPUs, tanto para métodos existentes na
literatura bem como para métodos que desenvolvemos;
• Realizar um estudo computacional comparativo dos resultados gerados pelos métodos implementados.
Alguns resultados produzidos neste trabalho foram apresentados nos seguintes eventos:
1. XVI ELAVIO 2012. Tı́tulo do trabalho: Implementações Paralelas de Métodos de
Programação Quadrática Irrestrita usando GPUs. O UQP foi resolvido usando a
metaheurı́stica Tabu Search e as implementações usaram CPU para o processamento
sequencial e GPUs para realizar o paralelismo da aplicação. Os resultados mostraram que é possı́vel obter uma aceleração de até 8 vezes no tempo de processamento
da implementação, com o uso de paralelismo com GPUs.
2. III ERAD 2012. Tı́tulo do trabalho: Explorando o Espaço de Soluções do UQP
por Meio de um VNS Paralelo Usando Propriedades de um Hipercubo. O espaço de
solução do UQP foi visto como um hipercubo, que foi explorado pela metaheurı́stica
Variable Neighborhood Search. A implementação foi sequencial e verificamos que
o método possui bons resultados quando comparados às soluções encontradas por
algoritmos exatos.
3. XVI CLAIO / XLIV SBPO 2012. Tı́tulo do trabalho: Algoritmos Paralelos em
GPUs para Problemas de Programação Quadrática Binária Irrestrita. Apresentamos
o UQP como um framework e mostramos como é possı́vel converter várias classes
de problemas de otimização combinatória para o modelo UQP. Demonstramos uma
forma rápida de recálculo do valor da função objetivo. Um Tabu Search e um
Variable Neighborhood Search foram implementados. Os resultados mostraram que
a implementação de um Tabu Search obteve melhores resultados e consumiu menos
tempo de computação.
Os próximos parágrafos resumem os conteúdos dos capı́tulos desta dissertação.
No Capı́tulo 2 apresentamos definições gerais incluindo algumas especı́ficas sobre paralelismo, que são utilizadas ao longo do texto.
No Capı́tulo 3 apresentamos os problemas de Programação Quadrática e o de Programação Quadrática Binária Irrestrita, sendo este último o foco desta dissertação. Descrevemos trabalhos anteriores, que buscaram resolver instâncias do UQP. Mostramos como
converter o UQP para um problema linear inteiro. Exibimos seis transformações que podem ser utilizadas para converter problemas de otimização combinatória para a forma
UQP. Especificamente convertemos os problemas Empacotamento de Conjuntos, Partição
19
de Conjuntos, Coloração de Vértices em um Grafo com K Cores, Conjunto Independente
Generalizado e Carregamento de Objetos em Estrados. Mostramos os métodos heurı́sticos que tentam resolver o UQP, Tabu Search, Variable Neighborhood Search, Gradient
Midpoint Method e uma Busca Local. Apresentamos um Branch and Bound para resolver
o UQP de maneira exata.
No Capı́tulo 4 definimos alguns conceitos sobre programação paralela com GPUs.
Apresentamos o que são GPUs, detalhes da arquitetura de placas da NVIDIA, e o que nos
motivou a estudar GPUs para acelerar a execução dos métodos discutidos no Capı́tulo 3.
No Capı́tulo 5 mostramos como realizar o cálculo do valor da função objetivo do UQP,
f (x) = xT Qx, na forma básica e algumas maneiras de recalcular f (x) quando o vetor x
sofre pequenas alterações. Estas maneiras são: (1) o recálculo com mudança do valor de
uma variável, (2) o recálculo com mudança do valor de uma variável sem alteração do
vetor de solução e (3) o recálculo com mudança dos valores em várias variáveis em um
dado intervalo. Apresentamos também o cálculo do limitante inferior à f (x) na forma
básica, utilizado no método Branch and Bound. Mostramos também uma maneira de
efetuar o recálculo do valor do limitante inferior à f (x) de forma eficiente, quando há
mudança do valor de uma variável.
No Capı́tulo 6 apresentamos os experimentos computacionais. Primeiro descrevemos o
ambiente de testes, depois as instâncias testadas e os resultados obtidos, tanto por heurı́sticas quanto por métodos exatos. Comparamos os resultados obtidos entre as implementações de um Tabu Search e de um Variable Neighborhood Search. Também comparamos
as implementações sequencial com a paralela de um Tabu Search. Exibimos os resultados
de métricas de desempenho, obtidos com o paralelismo das implementações dos métodos
Tabu Search e Branch and Bound utilizando GPUs.
Finalmente, no Capı́tulo 7 apresentamos algumas conclusões e possı́veis trabalhos futuros.
Capı́tulo 2
Definições
Este capı́tulo apresenta as definições que são utilizadas ao longo desta dissertação, servindo
inicialmente como um alicerce de conhecimento e posteriormente como uma fonte rápida
de consulta. Dividimos as definições em duas seções, as definições gerais e as que mais se
relacionam com paralelismo.
2.1
Definições Gerais
Nesta seção apresentamos definições e conceitos gerais.
Definição 2.1. Sejam I um intervalo de R com mais de
um ponto
e f : I → R uma
∂f (x)
função. Diz-se que f é continuamente diferenciável
se f for derivável no
∂(x)
intervalo I e sua derivada de primeira ordem for contı́nua.
Definição 2.2. Se um subconjunto A ⊂ R estiver contido em um intervalo [a, +∞), diz-se
que A é limitado inferiormente. Se A estiver contido em um intervalo (−∞, b], diz-se que
A é limitado superiormente. Se A ⊆ [a, b], para a < b, então, A é limitado superiormente
e inferiormente. Nesse caso diz-se que A é um conjunto limitado.
Definição 2.3 (Referência [32]). Diz-se que o ponto a é interior ao conjunto A ⊂ R, se
existe um escalar > 0 tal que o intervalo aberto (a − , a + ) está contido em A. O
conjunto dos pontos interiores a A é chamado interior do conjunto A e representado pela
notação int(A). A ⊂ R é chamado conjunto aberto se A = int(A), isto é, quando todos
os pontos de A são interiores a A.
Definição 2.4 (Referência [32]). Diz-se que um ponto a é aderente ao conjunto X ⊂ R
quando a é limite de alguma sequência de pontos xn ∈ X. Evidentemente, todo ponto
a ∈ X é aderente a X: basta tomar todos os xn = a.
Chama-se fecho de um conjunto X ao conjunto X formado por todos os pontos aderentes a X. Tem-se X ⊂ X. Se X ⊂ Y então X ⊂ Y . Um conjunto X é chamado de
20
CAPÍTULO 2. DEFINIÇÕES
21
conjunto fechado quando X = X, isto é, quando todo ponto aderente a X pertence a
X.
Definição 2.5. Um conjunto A ⊆ R chama-se conjunto compacto se ele é limitado e
fechado.
Definição 2.6. Um conjunto A ⊆ Rn é chamado conjunto convexo se todo segmento
de reta ligando quaisquer dois elementos de A está contido em A. De maneira precisa,
∀x, y ∈ A e ∀t ∈ [0, 1] tem-se que: (1 − t)x + ty ∈ A
Definição 2.7. Se x ∈ Rn e f : Rn → R for uma função, então o vetor gradiente de
f (x) é definido como
 ∂f (x) 
∂x
1

 ∂f (x)
 ∂x2 

∇f (x) = 
 .. 
 . 
∂f (x)
∂xn
Definição 2.8. Em um problema de otimização combinatória, a função objetivo é uma
função que se deseja minimizar ou maximizar: f : X → V , onde X e V são respectivamente o conjunto domı́nio e o contradomı́nio da função.
Definição 2.9. Espaço de soluções, X, de um problema de otimização combinatória é
o espaço com todas as soluções viáveis.
Definição 2.10. O espaço de soluções X = {x ∈ Qn : 0 ≤ x ≤ 1} é chamado de cubo
unitário.
Definição 2.11. Soluções ótimas são todas as soluções pertencentes ao espaço de soluções, que maximizam/minimizam o valor de uma função objetivo.
Definição 2.12. Uma função de vizinhança permite alcançar uma outra solução, dentro do espaço de soluções, seguindo um procedimento sistemático.
Exemplo 2.1. Em um espaço de soluções, cujas soluções são representadas por vetores
binários, uma função de vizinhança, Fv , chamada 1-Flip é o conjunto de soluções obtidas
da seguinte maneira:
Fv (x, i) = 1 − xi para algum i ∈ {1, ..., n}, onde x ∈ {0, 1}n
Definição 2.13. Vizinhança de uma solução s, denotada por N (s), é um subespaço do
espaço de soluções, onde a partir desta solução pode-se gerar este subespaço por meio de
uma função de vizinhança Fv .
Exemplo 2.2. N (s) = Fv (s, i) para algum i ∈ {1, 2, ..., n}, onde n é o número de variáveis
do vetor solução.
22
Definição 2.14. Uma vizinhança k-Flip de uma solução s é formada por vetores que são
diferentes de s em exatamente k posições.
Definição 2.15. Um ótimo local, é uma solução s que tem o maior ou menor valor em
uma vizinhança N (s), dependendo se o problema é de maximização ou de minimização.
Definição 2.16. Heurı́stica é definida por um conjunto de regras e métodos que têm
como objetivo resolver determinados problemas, mas sem garantias de se encontrar soluções ótimas.
Definição 2.17. Metaheurı́stica é definida por um conjunto de regras e métodos que
podem ser aplicados para resolver várias classes de problemas, mas sem garantias de
encontrar soluções ótimas.
Definição 2.18. Método exato é definido por um conjunto de regras aplicadas de
forma sistemática a solucionar um problema. Com um método exato tem-se a garantia
de encontrar soluções ótimas.
Definição 2.19. |C| representa a cardinalidade do conjunto finito C, ou seja, é o número
de elementos do conjunto.
Definição 2.20. Denotamos por Xk a famı́lia de todos os subconjuntos de X com k
elementos, isto é:
X
= {A : A ⊆ X e |A| = k}
k
Definição 2.21. Um grafo é um objeto matemático G = (V, E), onde V é um conjunto
finito não vazio de elementos denominados vértices e E é um conjunto de pares não
ordenados de elementos distintos de V denominados arestas, ou seja, E ⊆ V2 . Cada
aresta indica que dois vértices possuem uma relação ou estão ligados.
Definição 2.22. Dado um grafo G = (V, E), um caminho em um grafo é uma sequência de vértices v1 , v2 , ..., vk tal que (vi , vi+1 ) ∈ E ∀ 1 ≤ i ≤ k − 1.
Definição 2.23. Um hipercubo n-dimensional é um grafo não-orientado contendo 2n
vértices rotulados de forma binária, de 0 a 2n − 1, contendo arestas entre dois vértices se
e somente se seus rótulos binários diferem em apenas um bit [53]. Um hipercubo satisfaz
as seguintes propriedades:
1. Um vértice é ligado a outro através de uma aresta se e somente se as suas numerações,
em binário, diferem em apenas um bit.
2. Dados dois vértices quaisquer do hipercubo n-dimensional, existe um caminho entre
eles contendo no máximo n arestas.
3. É sempre possı́vel, a partir de um hipercubo com n dimensões, para n > 1, criar
dois novos hipercubos com dimensão (n − 1), removendo 2(n−1) arestas.
23
4. Dois vértices adjacentes não compartilham um outro vértice em sua vizinhança.
As figuras abaixo mostram exemplares de hipercubos.
1110
1011
1111
1010
110
111
0110
010
0010
011
0111
0011
0100
0000
100
0101
0001
101
1101
000
001
1000
1100
1001
Como o espaço de solução do UQP é um hipercubo n-dimensional, podemos utilizar as
propriedades acima para definir estruturas de vizinhança e explorá-las de forma paralela.
Outras propriedades sobre hipercubos podem ser vistas na referência [53]. As metaheurı́sticas Tabu Search e Variable Neighborhood Search apresentadas, respectivamente, nas
Seções 3.8.1 e 3.8.3, utilizam essas propriedades para “caminhar” pelos hipercubos dos
espaços de soluções.
Uma outra maneira de tentar resolver instâncias do UQP é via um método exato, que
apresentamos na Seção 3.9.2.
2.2
Definições sobre Computação Paralela
Nesta seção apresentamos definições e conceitos relacionados ao paralelismo das implementações. Definimos métricas e termos utilizados para analisar programas paralelos. Existem
várias métricas que permitem avaliar o desempenho de aplicações paralelas, tendo como
base a comparação entre a execução com múltiplos processadores e a execução com um
só processador. Algumas delas levam em consideração aspectos que são desconsiderados
por outras, como por exemplo, o tempo de comunicação entre processos. No Capı́tulo 6,
de experimentos computacionais, usamos as definições destas métricas para analisar os
resultados obtidos com as implementações dos algoritmos apresentados nesta dissertação.
Definição 2.24 (Referência [54]). Processo é um programa de computador em execução.
Definição 2.25. Uma thread pode ser vista como a forma de um processo dividir-se em
duas ou mais tarefas, que podem ser executadas de forma concorrente.
Segundo Tanenbaum [54], um processo de um sistema operacional tem uma única linha
de controle e um contador de programa para cada processo. Entretanto, alguns sistemas
24
operacionais modernos fornecem suporte para múltiplas linhas de controle dentro de um
processo. Essas linhas de controle são chamadas de threads ou processos leves.
Definição 2.26. O speedup mede quantas vezes mais rápido é a execução de um programa em paralelo em relação ao sequencial. Formalmente temos:
S(p) =
T (1)
,
T (p)
onde T (1) é o tempo de execução com 1 processador e T (p) é o tempo de execução com
p processadores.
De forma geral: 0 ≤ S(p) ≤ p. Se S(p) = p então o speedup é chamado de linear. É
raro ocorrer speedup linear, pois na maioria das aplicações paralelas há perda de tempo de
processamento devido a sobrecargas, que podem ocorrer devido à distribuição dos dados
e pela comunicação entre os processos.
Algumas situações podem ocorrer com o speedup em aplicações paralelas, a saber:
(a) Slowdown: T (1) < T (p) e portanto S(p) < 1.
(b) Sublinear: 1 < S(p) < p.
(c) Linear: S(p) = p.
(d) Supralinear: p < S(p).
A situação (a) é indesejável, (b) é o comportamento mais comum, (c) é a situação ideal,
mas só ocorre se não houver sobrecarga e (d) é possı́vel. Um speedup supralinear ocorre,
por exemplo, quando um programa sequencial não consegue armazenar todos os dados
necessários para o processamento na memóra RAM, enquanto a versão distribuı́da consegue, ao utilizar mais computadores em que cada computador resolve parte do problema
sem a necessidade de acessar o disco rı́gido novamente durante sua execução.
Definição 2.27. A Eficiência mede o aproveitamento dos recursos computacionais disponı́veis. Ela é a razão entre o speedup S(p) e o número de processadores utilizados.
Formalmente temos:
T (1)
S(p)
=
E(p) =
p
p × T (p)
Definição 2.28. O Trabalho de um programa é a soma dos tempos de execução de cada
processo. Formalmente:
W (p) = pT (p)
Definição 2.29. Sobrecarga é a diferença entre o trabalho realizado por um programa
paralelo e sua versão sequencial. Formalmente:
T0 = pT (p) − T (1)
25
Definição 2.30. A Lei de Amdahl diz: Seja 0 ≤ f ≤ 1 a fração da computação que só
pode ser realizada sequencialmente, o speedup máximo que uma aplicação paralela com p
processadores pode obter é:
1
S(p) ≤
f + 1−f
p
O Capı́tulo 3 apresenta trabalhos anteriores, que tratam de técnicas que foram propostas para o problema estudado nesta dissertação.
Capı́tulo 3
Trabalhos Anteriores
A área de pesquisa que desenvolve métodos para resolver o UQP recebe grande atenção
há mais de 50 anos [23]. Esta área se mantém ativa em virtude do vasto número de
problemas, de otimização combinatória, que podem ser expressos na forma UQP. Assim,
criar um bom método para resolver o UQP, pode significar criar uma boa maneira de
solucionar vários problemas de otimização combinatória.
A lista de trabalhos de pesquisa sobre UQP é extensa e pode ser dividida pelo tipo
de método proposto: heurı́stico [2, 10, 35, 36, 37, 38, 44] ou exato [11, 14, 17, 28, 45, 56].
Esta é uma pequena lista do que foi publicado sobre o assunto.
3.1
Programação Quadrática
Na sua forma geral, um problema de programação quadrática é representado da seguinte
forma:
1
max f (x) = cT x + xT Qx
2
sujeito a:
Ax ≤ b, Bx = d
x≥0
onde Q ∈ Qn×n , A ∈ Qm×n , B ∈ Qk×n , c ∈ Qn , b ∈ Qm , d ∈ Qk e x é um vetor com
variáveis de decisão em Qn .
Um problema de otimização expresso por uma função objetivo quadrática e restrições
lineares é denominado problema de programação quadrática. A programação quadrática tem uma grande importância dentro dos estudos de otimização combinatória, pois é
possı́vel modelar diversos tipos de problemas dessa forma.
26
CAPÍTULO 3. TRABALHOS ANTERIORES
3.2
27
Programação Quadrática Binária Irrestrita
Uma classe de problemas de programação quadrática que não contém restrições é chamada de programação quadrática irrestrita. Se nestes problemas as variáveis são binárias
então eles são chamados problema de programação quadrática binária irrestrita, que chamaremos de UQP nesta dissertação. É possı́vel converter um problema de programação
quadrática com restrições para um sem restrições, adicionando à função objetivo uma
função de penalidade. Isto é explicado em detalhes na Seção 3.6.
O problema quadrático binário irrestrito pode ser escrito na seguinte forma:
max f (x) = cT x + 21 xT Qx
onde c ∈ Qn , Q ∈ Qn×n e x ∈ {0, 1}n .
Na próxima seção apresentamos uma breve revisão da literatura sobre métodos heurı́sticos e exatos que tratam o UQP.
s
3.3
Artigos na Literatura
A quantidade de trabalhos sobre o UQP apresentada na literatura é consideravelmente
grande. Nesta seção fazemos uma revisão dos trabalhos que consideramos os mais relacionados à nossa pesquisa. As publicações desta revisão são separadas de acordo com o
tipo de método abordado, heurı́stico ou exato.
3.3.1
Métodos Heurı́sticos
Beasley [10] apresenta duas heurı́sticas para tentar resolver o UQP, um Tabu Search que
se baseia em uma lista de restrições que buscam evitar com que o método fique preso em
um ótimo local e um Simulated Annealing. As instâncias de teste estão disponı́veis na OR
Library (ver Seção 6.2.1) e possuem tamanhos de até 2.500 variáveis.
Bahram et al. [2] apresentam várias heurı́sticas “one-pass” para tentar resolver o
UQP. Em seus resultados computacionais, eles apresentam estudos com instâncias de até
9.000 variáveis. Eles afirmam que estas heurı́sticas fornecem bons pontos de partida para
métodos mais sofisticados.
Merz e Freisleben [36] apresentam uma heurı́stica gulosa e duas heurı́sticas de busca
local, 1-opt e k-opt, e informam que estes métodos também podem ser incorporados a
28
metaheurı́sticas. Esses métodos foram testados em 115 instâncias de até 2.500 variáveis,
apresentando soluções cujos valores são próximos aos melhores conhecidos.
Merz e Freisleben [35] descrevem um algoritmo genético. Eles afirmam que para instâncias pequenas, um crossover uniforme é suficiente para encontrar soluções ótimas ou
com valores iguais às melhores conhecidas. Para instâncias com mais de 200 variáveis, se
faz necessário incorporar uma estratégia de busca local. Em seus estudos computacionais
foram testadas instâncias de até 2.500 variáveis. Eles comparam o algoritmo com outros
métodos, como Simulated Annealing e Tabu Search.
Bahram et al. [4] discutem o uso do UQP como um framework para resolução de vários
problemas. Tais problemas são modelados na forma UQP. Em [3], os autores apresentam
o problema de coloração de vértices modelado como um UQP. Em [5], um novo modelo
para o Number Partitioning Problem é estudado. Em [7], o problema de encontrar um
clique máximo, com peso nas arestas, é modelado com o framework proposto. Em [6],
o problema de encontrar conjuntos independentes generalizado é escrito na forma UQP.
Todos estes artigos utilizam um Tabu Search ou variações deste método para resolver os
problemas.
3.3.2
Métodos Exatos
Palubeckis [44] apresenta um algoritmo de busca em árvore, incorporando soluções fornecidas por uma heurı́stica. Os resultados computacionais são apresentados para instâncias
de até 247 variáveis.
Pardalos e Rodgers [48] apresentam um método Branch and Bound, que usa limitantes
baseados em fixação de variáveis para cada vértice da árvore de enumeração. Este método
utiliza um teste que tenta fixar variáveis e um cálculo de limitantes baseado em um vetor
gradiente da função objetivo. Os autores apresentam uma classe de instâncias que possui
um número exponencial de ótimos locais, bem como dois programas em FORTRAN para
gerar instâncias. Em seus experimentos computacionais foram testadas instâncias de até
200 variáveis.
Billionet e Sutter [11] descrevem um método Branch and Bound. O limitante inferior
é calculado em três fases para cada vértice da árvore de busca. A primeira fase é feita
sobre o problema dual, que pode ser visto em detalhes em [1, 22, 56]. Os resultados
computacionais utilizam instâncias de até 100 variáveis.
Helmberg e Rendl [28] apresentam um método Branch and Bound que combina Relaxação Semidefinida com a técnica de Planos de Corte. Seus experimentos computacionais
mostram que esta é uma técnica robusta e foram testadas instâncias de até 100 variáveis.
Chardaire e Sutter [17] apresentam um método de decomposição para calcular limitan-
29
tes para o UQP. Primeiro mostram que qualquer função quadrática pode ser decomposta
em uma soma particular de funções quadráticas, que podem ser resolvidas facilmente por
um métodos Branch and Bound. Assumindo algumas hipóteses, provam que entre todas
as possı́veis decomposições, a decomposição Lagrangiana (ou Lagrangeana) encontra os
melhores resultados. Seus experimentos computacionais foram realizados para instâncias
de até 100 variáveis.
Pardalos e Rodgers [45] apresentam um método Branch and Bound, com seleção dinâmica de variáveis para fixação para resolver o problema de encontrar cliques máximos
em um grafo. Os resultados computacionais mostram experimentos com instâncias de até
1.000 vértices e 150.000 arestas.
Adams e Dearing [1] apresentam três técnicas para computar limitantes superiores
na função objetivo. Tais limitantes são importantes para reduzir o número de buscas
feitas pela implementação do algoritmo. A primeira técnica gera duas classes de funções
lineares. A segunda resolve uma relaxação contı́nua de um problema de programação
linear inteira mista. A terceira utiliza complementação quadrática de variáveis.
Embora o UQP pertença à classe NP-difı́cil, algumas de suas instâncias podem ser
resolvidas em tempo polinomial, em relação ao número de variáveis. Barahona [9], Chakradhar e Bushnell [16], Gu [21] e Li et al. [31], discutem caracterı́sticas de tais instâncias
e métodos para resolvê-las.
É possı́vel modelar o UQP como um problema de Programação Linear Inteiro, como
é mostrado na Seção 3.4.
3.4
UQP Linearizado
O UQP pode ser transformado em um programa linear binário pela linearização do termo
quadrático, como demonstra Beasley em [10]. Se yij é a variável que representa o produto
xi xj , então o UQP pode ser escrito na seguinte forma:
max f (x) =
n X
n
X
qij yij
i=1 j=1
sujeito a: yij ≤ xi
i = 1, . . . , n; j = 1, . . . , n
(3.1)
yij ≤ xj
i = 1, . . . , n; j = 1, . . . , n
(3.2)
yij ≥ xi + xj − 1
i = 1, . . . , n; j = 1, . . . , n
(3.3)
yij ∈ {0, 1}
i = 1, . . . , n; j = 1, . . . , n
(3.4)
xi ∈ {0, 1}
i = 1, . . . , n
(3.5)
30
As restrições (3.1) e (3.2) garantem que se xi ou xj tiver valor zero, yij também deverá
ter seu valor igual a zero. A restrição (3.3) garante que yij somente terá seu valor igual
a um, se ambos xi e xj tiverem valor igual à um. As restrições (3.4) e (3.5) são de
integralidade.
As vantagens de se linearizar o UQP são: pode-se utilizar solvers disponı́veis para
programação linear inteira e também fazer um estudo poliédrico do problema. A desvantagem é que o número de variáveis cresce rapidamente neste modelo linearizado, a saber
na ordem de n2 , onde n é o número de variáveis no problema quadrático.
Na próxima seção apresentamos uma lista de problemas que podem ser modelados na
forma UQP.
3.5
Lista de Problemas Modelados na Forma UQP
Vários problemas de otimização combinatória podem ser modelados na forma UQP, utilizando as transformações descritas na Seção 3.6. Dentre eles, citamos os problemas
apresentados na referência [4]:
Quadratic Assignment Problems
Multiple Knapsack Problems
Maximum Diversity Problems
Asymmetric Assignment Problems
Side Constrained Assignment Problems
Constraint Satisfaction Problems
Fixed Charge Warehouse Location Problems
Maximum Independent Set Problems
Graph Coloring Problems
Number Partitioning Problems
Linear Ordering problems
3.6
Capital Budgeting Problems
Task Allocation Problems
P-Median Problems
Symmetric Assignment Problems
Quadratic Knapsack Problems
Set Partitioning Problems
Maximum Clique Problems
Maximum Cut Problems
Graph Partitioning Problems
Linear Ordering Problems
Satisfiability Problems
Transformações Gerais
Um fato que torna o UQP muito útil é o de que diversos problemas de otimização combinatória podem ser convertidos em sua forma, via transformações simples. Há alguns
artigos na literatura que mostram algumas maneiras de transformar problemas de otimização combinatória para a forma UQP (ver referências [3, 5, 7, 6]). O que apresentamos
nessa seção é uma sı́ntese, de forma padronizada, das transformações utilizadas nestes trabalhos. Isso pode, eventualmente, possibilitar ao leitor desta dissertação, tentar converter
outros problemas para a forma UQP.
31
Transformação 1
Em muitos problemas de otimização combinatória a função objetivo, ou parte dela, é dada
em uma forma linear com variáveis binárias:
aT x
min / max
onde a ∈ Qn e x ∈ {0, 1}n . Por min / max queremos dizer que deseja-se minimizar ou
maximizar a função. Este problema também pode ser escrito como:
n
X
min / max
ai xi
i=1
Para converter estes problemas para o formato UQP, basta utilizar o mesmo vetor x
de variáveis e construir a matriz Q ∈ Qn×n da seguinte forma:
(
qi,j =
ai se i = j
0 caso contrário.
A prova de que o problema min / max aT x é equivalente ao problema min / max xT Qx,
sendo Q uma matriz diagonal contendo os valores qii = ai é feita por meio dos seguintes
argumentos:
n X
n
X
T
x Qx =
qi,j xi xj
i=1 j=1
n
X
aT x =
ai x i
i=1
Como qi,j = 0 para i 6= j e x2i = xi pois xi ∈ {0, 1} para 1 ≤ i ≤ n, temos que
n X
n
X
i=1 j=1
qi,j xi xj =
n
X
qi,i x2i
i=1
=
n
X
qi,i xi =
i=1
n
X
ai x i
i=1
Transformação 2
Vários problemas de otimização combinatória podem ser escritos na forma:
min / max
xT Qx
sujeito a:
Ax = b
x ∈ {0, 1}n
32
onde Q ∈ Qn×n , A ∈ Qm×n e b ∈ Qm .
A seguinte transformação consiste em adicionar uma função de penalidade à função
objetivo. Isto é, adicionando uma função de penalidade quadrática multiplicada por um
escalar P , sendo P > 0 se o problema é de minimização e P < 0 se o problema é de
maximização [23]. O modelo resultante para a transformação é
xT Qx + P (Ax − b)T (Ax − b)
min / max
sujeito a:
x ∈ {0, 1}n
Lembramos que dadas duas matrizes, C e D de dimensões apropriadas, as operações
(C − D)T = C T − DT e (CD)T = DT C T são válidas. Assim
xT Qx + P (Ax − b)T (Ax − b) = xT Qx + P ((Ax)T − bT )(Ax − b)
= xT Qx + P (xT AT − bT )(Ax − b)
= xT Qx + P (xT AT Ax − xT AT b − bT Ax + bT b)
= xT Qx + P (xT AT Ax − (Ax)T b − bT Ax + bT b) (3.6)
= xT Qx + P (xT AT Ax − 2bT Ax + bT b)
= xT Qx + P xT AT Ax − 2P bT Ax + P bT b
= xT Qx + xT P AT Ax − v T x + P bT b
onde v T = 2P bT A. Note que em (3.6), (Ax)T b = bT (Ax), pois se fizermos z = Ax, então
(Ax)T b = z T b = bT z = bT (Ax).
Como o vetor x é binário, segue que v T x = xT U x para a matriz U ∈ Qn×n construı́da
da seguinte maneira:
(
vi se i = j
ui,j =
0 caso contrário.
Assim,
xT Qx + xT P AT Ax − v T x + P bT b =
=
=
=
xT Qx + xT P AT Ax − xT U x + P bT b
xT Qx + xT (P AT A − U )x + P bT b
xT (Q + P AT A − U )x + c
xT Q̂x + c
onde Q̂ = Q + P AT A − U e c = P bT b. Portanto, podemos finalmente escrever o problema
na forma UQP:
min / max xT Q̂x
33
onde x ∈ {0, 1}n e Q̂ ∈ Qn×n .
Transformação 3
Alguns problemas de otimização combinatória possuem restrições do tipo: xi + xj ≤ 1
para 1 ≤ i, j ≤ n, com i 6= j e x ∈ {0, 1}n . Neste caso adicionamos P xi xj à função
objetivo para 1 ≤ i, j ≤ n. Isto pode ser escrito usando uma matriz simétrica D ∈ Qn×n
com coeficientes:
(
1
se existe a restrição do tipo xi + xj ≤ 1, com i 6= j
2
di,j =
0 caso contrário
Então, a Transformação 3 consiste em adicionar xT P Dx à função objetivo. Na Seção 3.7.2 mostramos um exemplo do uso da Transformação 3 quando modelamos o
problema Set Partitioning.
Transformação 4
De forma similar ao que foi visto na Transformação 3, podemos transformar restrições
da forma xi ≤ xj . Neste caso precisamos adicionar à função objetivo o produto P xi (1−xj ).
Definimos uma matriz simétrica M da seguinte maneira
mi,j



t se i = j e existir a restrição xi ≤ xk , para algum k
=
− 1 se existir a restrição xi ≤ xj
 2

0 caso contrário
Onde 1 ≤ i, j, k ≤ n e t é a quantidade de restrições existentes para xi . Exemplo: Se
existirem duas restrições para xi (xi ≤ xj e xi ≤ xk ) então t = 2.
Assim, a Transformação 4 consiste em adicionar xT P M x à função objetivo.
Transformação 5
Suponha que o problema tem restrições em variáveis binárias de forma que x ∈ {0, 1}n×m .
Neste caso x é uma matriz e a transformamos em um vetor da seguinte maneira:
x̂k = x̂(i−1)m+j = xi,j
(1 ≤ i ≤ n) e (1 ≤ j ≤ m) .
onde k = (i − 1)m + j.
Esta transformação permite utilizar um vetor, com as variáveis de decisão, ao invés
34
de uma matriz.
Transformação 6
Há casos em que existem mais de um vetor de variáveis binárias. Suponha que temos
x ∈ {0, 1}n e y ∈ {0, 1}m . Podemos associá-los da seguinte maneira:
(
x̂i =
xi
se 1 ≤ i ≤ n
yi−n se n + 1 ≤ i ≤ n + m
De acordo com Kochenberger e Glover [4], é sempre possı́vel escolher um escalar P
suficientemente grande ou pequeno, de tal forma que o conjunto de soluções ótimas são
iguais tanto para o problema original quanto para o problema o quadrático, após a sua
transformação.
Na Seção 3.7 mostramos exemplos, de problemas de otimização combinatória, que
podem ser modelados na forma UQP utilizando as transformações descritas nesta seção.
3.7
Problemas de Otimização Combinatória Modelados na Forma UQP
Nesta seção mostramos como transformar para a forma UQP alguns problemas de otimização combinatória. Nominalmente convertemos os seguintes problemas para a forma
UQP: Empacotamento de Conjuntos [4], Partição de Conjuntos [4], Coloração de Vértices
em um Grafo com K Cores [4], Conjunto Independente Generalizado [6] e Carregamento
de Objetos em Estrados [18, 39].
3.7.1
Empacotamento de Conjuntos (Set Packing Problem)
Este problema tem inúmeras aplicações. Em [55] apresenta um extensivo survey do problema de empacotamento de conjuntos e modelos relacionados.
Definição 3.1. Sejam A um conjunto finito não vazio, F um conjunto não vazio de
subconjuntos de A. A cada elemento f ∈ F está associado um custo cf ∈ Q∗+ . O
problema de empacotamento de conjuntos consiste em encontrar uma coleção de
conjuntos disjuntos em F cuja a soma dos custos seja máxima.
Uma formulação, em programação linear inteira, para o problema de empacotamento
35
de conjuntos é:
max f (x) = cT x
Ax ≤ 1
Sujeito a:
x ∈ {0, 1}n
onde c ∈ Qn+ e Am×n é uma matriz de coeficientes 0/1.
Para mostrar como podemos transformar o modelo acima para o formato UQP, utilizaremos a Transformação 1 na função objetivo e a Transformação 3 em cada restrição.
Assim a função objetivo pode ser reescrita da seguinte forma:
T
c x=
n
X
cj x j =
n X
n
X
j=1
qij xi xj = xT Qx
i=1 j=1
onde qjj = cj e qij = 0 para i 6= j, e as restrições podem ser reescritas da seguinte maneira:
n
X
aij xj ≤ 1
para i = 1, 2, . . . , m
j=1
Considerando somente as parcelas em que aij = 1 para i = 1, 2, . . . , m e j = 1, 2, . . . , n
temos
n
X
xj ≤ 1
j=1
que pode ser escrita como uma função de penalidade, que é adicionada a função objetivo
P
n−1 X
n
X
xi xj
i=1 j=i+1
sendo P < 0 para problemas de maximização.
Exemplo 3.1 (Referência [4]). Encontrar variáveis que resolvem:
max f (x)
Sujeito a:
=
x1 + x2 + x3 + x4
x1 + x3 + x4 ≤ 1
x1 + x2 ≤ 1
x ∈ {0, 1}4
Reescrevendo o problema na forma UQP e utilizando P = −2M onde M ∈ Q, temos:
max f (x) = x1 + x2 + x3 + x4 − 2M x1 x3 − 2M x1 x4 − 2M x3 x4 − 2M x1 x2
que pode ser escrito como
36
 

 

x1
0 −M −M −M
x1
1 0 0 0
 

 

 x2 
 −M
0 1 0 0 x2 
0
0
0
 

 
max f (x) = [x1 , x2 , x3 , x4 ] 
 
0 0 1 0 x  + [x1 , x2 , x3 , x4 ]  −M
0
0 −M 
 x3 

  3

x4
−M
0 −M
0
x4
0 0 0 1
  
 

x1
0 −M −M −M
1 0 0 0
  
 

 x2 
0 1 0 0  −M
0
0
0
  
 

= [x1 , x2 , x3 , x4 ] 
 x 
0 0 1 0 +  −M
0
0
−M
  3 
 

x4
−M
0 −M
0
0 0 0 1
 

x1
1 −M −M −M
 

 x2 
 −M
1
0
0
 
= [x1 , x2 , x3 , x4 ] 
 x 
 −M
0
1
−M
  3

x4
−M
0 −M
1
3.7.2
Particionamento de Conjuntos (Set Partitioning)
Nesta subseção mostramos como transformar o problema de particionamento de conjuntos para forma UQP. Primeiro definimos o que é uma partição de conjuntos e depois
apresentamos formalmente o problema em questão. A transformação é feita em seguida.
Definição 3.2. Seja A um conjunto finito e não vazio. Uma partição de A é uma famı́lia
de subconjuntos não vazios A1 , A2 , . . . , An tais que:
1.
n
S
Ai = A;
i=1
2. Ai ∩ Aj = ∅, se i 6= j.
Definição 3.3. Sejam A um conjunto finito não vazio, F um conjunto não vazio de
subconjuntos de A. A cada elemento f ∈ F está associado um custo cf ∈ Q∗+ . O
problema de particionamento de conjuntos consiste em encontrar um subconjunto
de F que defina uma partição de A, cuja a soma dos custos seja mı́nima.
Uma formulação, em programação linear inteira, para o problema de Particionamento
de Conjuntos é:
min f (x) = cT x
Sujeito a:
Ax = 1
x ∈ {0, 1}n
onde c ∈ Qn+ e A é uma matriz de coeficientes 0/1.
37
Para mostrar como podemos transformar o modelo acima para o formato UQP, utilizaremos a Transformação 1 na função objetivo e a Transformação 2 nas restrições.
Assim a função objetivo pode ser reescrita da seguinte forma:
T
c x=
n
X
cj x j =
j=1
n X
n
X
qij xi xj = xT Qx
i=1 j=1
onde qjj = cj e qij = 0 para i 6= j.
As restrições podem ser reescritas sob a forma de uma função de penalidade, que é
adicionada à função objetivo da seguinte maneira:
P (Ax − 1)T (Ax − 1)
sendo P > 0 para problemas de minimização.
Desta forma o problema acima torna-se:
min f (x) = xT Q̂x
Sujeito a:
x ∈ {0, 1}n
Exemplo 3.2 (Referência [4]). Encontrar variáveis que resolvem:
min f (x)
Sujeito a:
=
3x1 + 2x2 + x3 + x4 + 3x5 + 2x6
x1 + x3 + x6 = 1
x2 + x3 + x5 + x6 = 1
x3 + x4 + x5 = 1
x1 + x2 + x4 + x6 = 1
x ∈ {0, 1}6
Reescrevendo o problema na forma UQP
f (x) = xT Q̂x + c
onde Q̂ = Q + P AT A − U , c = P bT b, v = 2P bT A e U é uma matriz diagonal tal que uii = vi para
i = 1, 2, . . . , n e uij = 0 para i =
6 j.

1


0



1


T 
min f (x) = x Q + P 
0



0



1


2P


P



P


T 
= x Q + 
P



0



2P

3 0 0

0 2 0

0 0 1

= xT 
0 0 0

0 0 0

0 0 0


−2P + 3

 P

 P

= xT 

P


0

2P
0
1
1
0
1
1
0
0
1
1
1
0
P
2P
P
P
P
2P
0
0
0
1
0
0

1 

1
 1
0
0



1
 0
0
 1
1
0
1
0
1
P
P
3P
P
2P
2P
0
0
0
0
3
0
1
1
1
0
P
0
P
P
P 2P
2P P
P 2P
P
P
 
−2P
0
 
 P
0
 

0
  P
+

0
  P

0 
 0
2P
2
P
−2P + 2
P
P
P
2P
P
P
−3P + 1
P
2P
2P
38

4


0
0 0 1


0
0 1 1
−P 

0
1 1 0


0
1 0 1

0
 
4P
0
2P
 


2P   0 4P

0
2P 
 0
−
0
0
P
 


0
P 0
0
0
3P
P
−2P
P
P
P
2P
P
P
−3P
P
2P
2P
P
P
P
−2P + 1
P
P
0
4
0
0
0
0
0
0
6P
0
0
0
P
P
P
−2P
P
P
0
P
2P
P
−2P + 3
P
0
0
6
0
0
0
0
0
0
4P
0
0
0
P
2P
P
−2P
P
0
0
0
4
0
0
0
0
0
0
4
0
0
0
0
0
4P
0

0


0


0

 x + 4P

0


0

6

0


0


0 

 x + 4P

0


0 

6P

2P


2P 


2P 

 x + 4P

P 


P 

−3P

2P

2P 

2P 

 x + 4P

P


P

−3P + 2
Utilizando P = 10, temos:
min f (x)
=

 
−17 10
10
10
0
20
x1

 
 10 −18 10


10
10
20  x2 


 10
 
10 −29 10
20
20 

 x3 
[x1 , x2 , x3 , x4 , x5 , x6 ] 
   + 40
 10
 
10
10 −19 10
10 

 x4 
 0


10
20
10 −17 10  

x5 
20
20
20
10
10 −28
x6
3.7.3
39
Coloração de Vértices em um Grafo com no máximo K
Cores (K-Coloring)
Nesta subseção tratamos o problema de coloração de vértices em um grafo. Primeiro,
formulamos o problema geral, em seguida apresentamos o problema para o caso em que
o número de cores é fixo.
Definição 3.4. Dado um grafo não dirigido G = (V, E), onde V é o conjunto finito não
vazio de vértices e E é o conjunto de arestas. Deseja-se atribuir cores para os vértices de G,
de forma que os vértices adjacentes recebam cores diferentes. O problema de coloração
de vértices com no máximo K cores em G consiste encontrar uma coloração que utilize
até K cores, onde k ≤ |V |.
As variáveis do modelo são definidas como segue:
(
1 Se a cor p for utilizada na coloração
0 Caso contrário
(
1 Se a cor p é atribuı́da ao vértice i
0 Caso contrário
yp =
xip =
Este problema pode ser modelado, em programação linear inteira, da seguinte maneira:
min f (x) =
k
X
yp
p=1
Sujeito a:
k
X
xip = 1
i = 1, 2, . . . , n
(3.7)
∀(i, j) ∈ E e p = 1, 2, . . . , k
(3.8)
∀i ∈ V e p = 1, 2, . . . , k
(3.9)
p=1
xip + xjp ≤ 1
xip ≤ yp
x ∈ {0, 1}n×k
y ∈ {0, 1}k
onde k é o número máximo de cores permitidas na coloração e n = |V |.
A restrição (3.7) garante que cada vértice será colorido com exatamente uma cor. A
restrição (3.8) garante uma coloração viável. A restrição (3.9) diz que um vértice somente
poderá ser colorido com uma cor se esta estiver sido escolhida para a coloração.
Obtemos o modelo no formato UQP aplicando a seguinte sequência de operações:
Transformação 1 para a função objetivo, a Transformação 2 para as restrições (3.7),
a Transformação 3 para as restrições (3.8) e a Transformação 4 para as restrições
(3.9).
40
Agora tratamos o caso especı́fico do problema, em que o número de cores é fixo.
Definição 3.5. Dado um grafo não dirigido G = (V, E), onde V é o conjunto finito não
vazio de vértices e E é o conjunto de arestas. Deseja-se atribuir cores para os vértices
de G, de forma que os vértices adjacentes recebam cores diferentes. No problema de
coloração de vértices, em um grafo, com exatamente K cores consiste em encontrar
uma atribuição que utilize k cores, onde K ≤ |V |.
O conjunto de restrições para este problema pode ser modelado, em programação
linear inteira, da seguinte maneira:
K
X
xip = 1
i = 1, 2, . . . , n
p=1
xip + xjp ≤ 1
∀(i, j) ∈ E e p = 1, 2, . . . , K
x ∈ {0, 1}n×K
onde n = |V |.
Note que as restrições são similares àquelas para o modelo geral, com diferença de que
o número máximo de cores, K, é conhecido e que não há função objetivo. Para converter
as restrições acima para o formato UQP, utilizamos as mesmas operações indicadas no
caso geral.
Exemplo 3.3 (Referência [4]). Considere o grafo na Figura 3.1 e assuma que desejamos encontrar
uma coloração dos vértices utilizando 3 cores.
1
5
2
4
3
Figura 3.1: Grafo de Exemplo para o Problema de Coloração em Vértices
O conjunto de restrições a serem satisfeitas são:
xi1 + xi2 + xi3 = 1 i = 1, 2, . . . , 5
xip + xip ≤ 1
p = 1, 2, 3
O problema no formato UQP torna-se:
min f (x) = xT Q̂x
∀(i, j) ∈ E
41
onde Q̂ é:

















Q̂ = 















−4
4
4
4
0
0
0
0
0
0
0
0
4
0
0
4
4
4
0
0
0
0
0
0
0
0
4
0
0
−4
4
0
4
0
0
0
0
0
0
0
0
4
0
4 −4
0
0
4
0
0
0
0
0
0
0
0
4
0
0 −4
4
4
4
0
0
4
0
0
4
0
0
4
0
4 −4
4
0
4
0
0
4
0
0
4
0
0
4
4
4 −4
0
0
4
0
0
4
0
0
4
0
0
4
0
0 −4
4
4
4
0
0
0
0
0
0
0
0
4
0
4 −4
4
0
4
0
0
0
0
0
0
0
0
4
4
4 −4
0
0
4
0
0
0
0
0
4
0
0
4
0
0 −4
4
4
4
0
0
0
0
0
4
0
0
4
0
4 −4
4
0
4
0
0
0
0
0
4
0
0
4
4
4 −4
0
0
4
0
0
4
0
0
0
0
0
4
0
0 −4
4
4
4
0
0
4
0
0
0
0
0
4
0
4 −4
4
0
4
0
0
4
0
0
0
0
0
4
4
0 −4

































3.7.4
Conjunto Independente Generalizado (Generalized Independent Set Problem)
Agora descrevemos uma generalização do problema do conjunto independente em um
grafo.
Definição 3.6. Sejam G = (V, E) um grafo não dirigido, onde V é o conjunto de vértices
e E o conjunto de arestas, um custo wi > 0 é associado a cada vértice i ∈ V e um custo
cij > 0 é associado a cada aresta (i, j) ∈ E. O problema do conjunto independente
generalizado consiste em encontrar um subconjunto de vértices S ⊆ V que maximiza a
diferença entre a soma dos custos dos vértices em S e a soma dos custos daquelas arestas
que têm ambos os vértices em S.
As variáveis do modelo são definidas como:
(
1 Se o vértice i ∈ S
xi =
0 Caso contrário
Uma formulação, em programação quadrática binária irrestrita, para o problema do conjunto independente generalizado é:
max f (x) =
X
wi xi −
i∈V
x ∈ {0, 1}
X
(i,j)∈E
n
cij xi xj
42
Exemplo 3.4. Neste exemplo apresentamos um grafo para o problema do conjunto independente
generalizado e o modelo no formato UQP.
2
1
8
5
7
4
2
10
6
5
10
2
2
4
3
6
3
4
Figura 3.2: Grafo de Exemplo para o Problema do Conjunto Independente Generalizado
Encontrar as variáveis que resolvem:
max f (x)
=
2x1 + 5x2 + 4x3 + 3x4 + 7x5
−(8x1 x2 + 10x1 x4 + 6x1 x5 + 2x2 x3 + 4x2 x5 + 6x3 x4 + 10x3 x5 + 2x4 x5 )
x ∈ {0, 1}5
No formato com matrizes temos:
max f (x)
=
=
=

2

0

xT 
0

0
0

2

0

xT 
0

0
0
[x1 ,
0
5
0
0
0
0
0
4
0
0
0
5
0
0
0
0
0
4
0
0
x2
x3



0
0 8 0 10 6



0 0 2 0 4 
0



T 

0
 x + x 0 0 0 6 10 x



0
0 0 0 0 2 
7
0 0 0 0 0



0 0
0 4 0 5 3



4 0 1 0 2
0 0



T 

0 0
 x + x 0 1 0 3 5 x



3 0
5 0 3 0 1
0 7
3 2 5 1 0

 
2 4 0 5 3
x1

 
4 5 1 0 2 x2 

 
 
x4 x5 ] 
0 1 4 3 5 x3 

 
5 0 3 3 1 x4 
3 2 5 1 7
x5
0
0
0
3
0
3.7.5
43
Carregamento de Objetos em Estrados (Manufacturer’s
Pallet Loading Problem)
Em [39], Morabito e Morales afirmam que o processo de empacotamento de objetos (caixas) em objetos maiores (estrados, em inglês pallets) é similar ao processo de cortes de
objetos em itens menores. Se todas as caixas tiverem as mesmas dimensões, tem-se o
problema de carregamento de estrado, em inglês Manufacturer’s Pallet Loading Problem
(MPL).
Em [18], Dowsland apresenta uma abordagem para o MPL que consiste em encontrar
um conjunto independente máximo de um grafo particular, onde os vértices representam
as possı́veis posições das caixas, no estrado, tal que dois vértices são adjacentes se as
posições das caixas se sobrepõem. A abordagem é baseada na observação de que existe
uma correspondência biunı́voca entre conjuntos independentes máximos e layouts ótimos
do MPL. Seguindo as ideias descritas na Seção 3.7.4, o MPL pode ser modelado na forma
UQP.
3.8
Métodos Heurı́sticos
Nesta seção descrevemos algumas heurı́sticas que foram desenvolvidas para tentar resolver
instâncias do UQP.
3.8.1
Tabu Search
Segundo Glover [20], o método Tabu Search (TS) é uma estratégia que ajuda heurı́sticas a
escaparem de ótimos locais, ao tentar resolver problemas de otimização combinatória. O
TS impõe restrições para guiar o processo de busca, com a finalidade de explorar regiões
difı́ceis de se alcançar por meio de heurı́sticas. As restrições de busca no espaço de soluções
no TS são criadas com o auxı́lio de uma lista tabu. Uma lista tabu, L, para o UQP é um
vetor, com a mesma quantidade de elementos que o vetor solução x, onde Li > 0 para
1 ≤ i ≤ n representa que xi não pode ser modificado por uma quantidade K, constante
pré-definida, de iterações.
O Algoritmo 3.8.1 apresenta o esquema básico do TS sequencial. Neste algoritmo: Q
é a matriz de entrada para o UQP, x representa uma solução viável para o problema, x∗
representa a melhor solução encontrada pelo algoritmo, L é uma lista tabu e K é um valor
que representa a quantidade de iterações nas quais a variável xi não sofrerá alterações. O
Algoritmo 3.8.2 descreve o pseudo-código do procedimento busca local TS.
Algoritmo 3.8.1: Pseudo-código do método básico do Tabu Search para o UQP
1
2
3
4
5
6
7
8
9
10
Entrada: n ∈ N∗ , Q ∈ Qn×n , K ∈ Z, Solução Inicial ∈ {0, 1}n
Saı́da: x∗ ∈ {0, 1}n , f (x) ∈ Q
inı́cio
x ← Solução Inicial
x∗ ← x
Li ← 0 para i = 1, 2, . . . , n
enquanto critério de parada não for satisfeito faça
para i = 1 até n faça
se Li = 0 então
x0 ← x
x0i ← 1 − x0i
n
P
f (x0 ) ← f (x) + (1 − 2xi ) qii + (qij + qji )xj
j=1
j6=i
se f (x0 ) > f (x) então
x ← x0
t←i
fim
11
12
13
14
fim
fim
xt = 1 − xt
se Li > 0 então
Li ← Li − 1
fim
fim
Lt ← K
se f (x) > f (x∗ ) então
x ← busca local TS(n, Q, x, f (x∗ ))
x∗ ← x
fim
15
16
17
18
19
20
21
22
23
24
25
26
27
fim
28
29
fim
44
45
Exemplo 3.5. A Figura 3.3 mostra um exemplo com quatro iterações de um TS. É fornecido um
vetor solução inicial x, neste exemplo x = [1, 0, 1, 0], uma lista tabu L = [0, 0, 0, 0], inicialmente vazia, e
K = 2. Escolhe-se um conjunto de soluções na vizinhança N (x) e avalia-se as mesmas de acordo com a
n P
n
P
função objetivo, f (x) = xT Qx =
(−1)i (i + j)xi xj e n = 4. A matriz do UQP que representa esta
i=1 j=1
função é dada por:



Q=


Iteração 1
−2 3
−3 4
−4 5
−5 6
L(x)

−4 5

−5 6 

−6 7 

−7 8
x
0
0
0
0
0
0
1
0
1
N(x)
1
f(x) = -6
Iteração 2
1
1
0
0
0
0
1
1
1
0
1
0
f(x) = -8
f(x) = -2
x
0
2
0
0
0
0
1
N(x)
0
1
0
1
0
0
0
f(x) = -2
0
1
f(x) = 2
f(x) = 0
L(x)
0
f(x) = 6
x
0
0
1
2
0
0
0
1
1
N(x)
1
0
1
0
0
f(x) = 6
1
1
f(x) = 22
f(x) = 8
Iteração 4
1
f(x) = -12
L(x)
0
Iteração 3
1
0
0
f(x) = -16
L(x)
x
0
2
0
1
1
0
1
1
N(x)
0
f(x) = 24
0
1
1
f(x) = 22
1
x
0
1
0
1
1
1
f(x) = 8
1
f(x) = 24
Figura 3.3: Iterações de um Tabu Search para a instância no Exemplo 3.5
Em cada iteração investiga-se a vizinhança N (x), escolhe-se uma solução com o melhor valor de
função objetivo, atualiza-se a lista tabu L fazendo com que Li ← Li − 1 para Li > 0 e define-se Lt = K,
onde t é a posição da lista tabu referente ao vizinho com o melhor valor de solução. Este procedimento é
repetido a cada iteração até que a condição de parada seja satisfeita.
3.8.2
Busca Local
Nesta seção apresentamos o pseudo-código da função busca local TS que aparece em
[10], aqui descrita no Algoritmo 3.8.2 e utilizada no método Tabu Search exibido no
46
Algoritmo 3.8.1. Nesta busca local usa-se a função de vizinhança 1-Flip.
Algoritmo 3.8.2: Pseudo-código da busca local TS do Algoritmo 3.8.1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Entrada: n ∈ N∗ , Q ∈ Qn×n , x ∈ {0, 1}n , V ∗ ∈ Q
Saı́da: x ∈ {0, 1}n
inı́cio
repita
melhorou ← f also
para t = 1 até n faça
xt ← 1 − xt
se f (x) > V ∗ então
V ∗ ← f (x)
melhorou ← verdadeiro
senão
xt = 1 − xt
fim
fim
até melhorou = falso
fim
3.8.3
Variable Neighborhood Search
Variable Neighborhood Search (VNS) [26, 27] é uma metaheurı́stica, que é muito utilizada
para tentar resolver problemas de otimização combinatória. Esta técnica baseia-se na
mudança sistemática de vizinhanças junto com uma estratégia de busca local. O VNS foi
utilizado com sucesso na resolução de vários problemas [15, 25, 51]. Devido ao excelente
desempenho do VNS na resolução de diversos problemas, decidimos aplicá-lo para tentar
resolver instâncias do UQP.
O VNS permite que se crie, de forma flexı́vel, uma estrutura de vizinhança que seja
adequada para o problema a ser resolvido. Nos estudos apresentados nesta dissertação,
utilizamos a estrutura de vizinhança k-Flip. Denotamos por Nk (x) o conjunto de soluções
diferentes de x em exatamente k posições. Esta estrutura de vizinhança tem relação direta
com as propriedades 1 e 2 de um hipercubo, enunciadas na Seção 2.23.
O Algoritmo 3.8.3 descreve o pseudo-código do VNS e o Algoritmo 3.8.4 apresenta
a função busca local VNS utilizado no Algoritmo 3.8.3. Nesse algoritmo é possı́vel
utilizar dois tipos de vizinhança, 1-Flip e 2-Flip controlados pelo valor da variável k
fornecida na entrada.
3.8.4
Gradient Midpoint Method
Pardalos et al. [29] apresenta a heurı́stica Gradient Midpoint Method que utiliza informações do vetor gradiente de f (x) para gerar, rapidamente, uma solução para o UQP. Dada
Algoritmo 3.8.3: Pseudo-código do método básico do VNS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Entrada: n ∈ N∗ , Q ∈ Qn×n , kmax ∈ Z, Solução inicial ∈ {0, 1}n
Saı́da: x ∈ {0, 1}n , f (x) ∈ Q
inı́cio
x ← Solução inicial
k←1
enquanto k 6= kmax faça
x0 ← Vetor solução aleatório na vizinhança Nk (x)
x00 ← busca local VNS(n, Q, k, x0 )
se f (x00 ) > f (x) então
x ← x00
k←1
senão
k ←k+1
fim
fim
fim
fim
Algoritmo 3.8.4: Pseudo-código da busca local VNS do Algoritmo 3.8.3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Entrada: n ∈ N∗ , Q ∈ Qn×n , k ∈ Q, x ∈ {0, 1}n
Saı́da: x ∈ {0, 1}n
inı́cio
F local ← f (x)
Ind0 ← −1, Ind1 ← −1
se k = 1 então
xi ← 1 − xi
se f (x) > F local então
F local ← f (x)
Ind0 ← i
fim
xi ← 1 − xi
fim
senão
para i = 1 até n − 1 faça
xi ← 1 − xi
para j = i + 1 até n faça
xj ← 1 − xj
se f (x) > F local então
F local ← f (x)
Ind0 ← i
Ind1 ← j
fim
xj ← 1 − xj
fim
xi ← 1 − xi
fim
fim
se Ind0 6= −1 então xInd0 ← 1 − xInd0
se Ind1 6= −1 então xInd1 ← 1 − xInd1
fim
47
48
que f (x) = xT Qx, calcula-se os limitantes inferiores e superiores para o vetor gradiente,
que denotamos por a ∈ Qn e b ∈ Qn , da seguinte maneira:
ai =
n
X
qij− ,
j=1
bi =
n
X
qij+
i = 1, . . . , n.
(3.10)
j=1
onde qij− = min(qij , 0) e qij+ = max(qij , 0) para i = 1, 2, . . . , n e j = 1, 2, . . . , n.
Se 21 (ai + bi ) ≥ 0, então a variável correspondente xi terá seu valor igual a 0, caso
contrário xi terá seu valor igual a 1.
De acordo com os autores do artigo na referência [29], esta heurı́stica é capaz de
resolver uma classe difı́cil de instâncias do UQP. Vemos estas instâncias na Seção 6.2.2.
O Algoritmo 3.8.5 apresenta o pseudo-código do Gradient Midpoint Method. Note que ele
é muito simples.
Algoritmo 3.8.5: Gradient Midpoint Method
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Entrada: n ∈ N∗ , Q ∈ Qn×n
Saı́da: x ∈ {0, 1}n , f (x) ∈ Q
inı́cio
ai ← 0; bi ← 0
para j = 1 até n faça
ai ← ai + min(qij , 0)
bi ← bi + max(qij , 0)
fim
fim
se (ai + bi )/2 ≥ 0 então
xi ← 0
senão
xi ← 1
fim
fim
c←0
para j = 1 até n faça
c ← c + qij xi xj
fim
fim
f (x) ← c
fim
3.9
Métodos Exatos
Nesta seção apresentamos como calcular limitantes para instâncias do UQP e regras para
determinar os valores das variáveis em uma solução ótima. Mostramos também o Branch
49
and Bound (B&B), que é um método exato baseado em enumeração implı́cita das soluções
no espaço de soluções.
As referências [29, 48, 49] são as fontes principais do texto desta seção.
3.9.1
Limitantes e Regras para Determinar Valores das Variáveis em uma Solução Ótima
Nesta seção apresentamos um método para se calcular limitantes, que é útil para diminuir
o número de vértices explorados na árvore de enumeração do método Branch and Bound.
Teorema 3.1. [48] Sejam f uma função continuamente diferenciável em um conjunto
aberto que contém um conjunto compacto e convexo S ⊂ Qn e x∗ uma solução ótima
para o problema
min
sujeito a:
f (x) = xT Qx
x ∈ S.
(3.11)
Então x∗ é uma solução ótima para o problema
min
sujeito a:
xT ∇f (x∗ )
x ∈ S.
(3.12)
Suponha que S = {x ∈ Qn : 0 ≤ x ≤ 1} é um cubo unitário e x∗ é uma solução ótima
n
P
∂f (x∗ )
para (3.11) e (3.12). Como xT ∇f (x∗ ) =
xi
, podemos concluir que
∂xi
i=1
x∗i =

∂f (x∗ )


0
se
≥ 0



∂xi
para i = 1, 2, . . . , n.


∂f (x∗ )


 1 se
< 0
∂xi
Isto é verdade porque
T
∗
min{x ∇f (x ) : 0 ≤ x ≤ 1} =
n
X
i=1
min{xi
∂f (x∗ )
: 0 ≤ xi ≤ 1}
∂xi
Como a função xT ∇f (x∗ ) é linear, pois a função f (x) é quadrática, o problema
min
xT ∇f (x∗ )
sujeito a:
0≤x≤1
(3.13)
50
é um problema de programação linear. Assim, uma solução ótima para ele é um dos
vértices do poliedro S = {x : 0 ≤ x ≤ 1}. Portanto,
min{xT ∇f (x∗ ) : 0 ≤ x ≤ 1} = min{xT ∇f (x∗ ) : x ∈ {0, 1}n }.
De fato, não assumimos que uma solução ótima x∗ é conhecida. Mas se pudermos encontrar limitantes ai e bi tais que
ai ≤
então
(
x∗i =
∂f (x)
≤ bi
∂xi
0 se ai ≥ 0
1 se bi < 0
∀x ∈ S = [0, 1]n
para i = 1, 2, . . . , n.
(3.14)
n
P
∂f (x)
=
(qij + qji )xj . Os
∂xi
j=1
valores dos limitantes podem ser determinados da seguinte maneira:
Sendo f (x) = xT Qx, onde Q é uma matriz assimétrica e
ai = qii +
n
X
−
(qij− + qji
) para i = 1, 2, . . . , n
j=1
bi = qii +
n
X
+
(qij+ + qji
) para i = 1, 2, . . . , n
j=1
−
onde qij− = min{qij , 0}, qji
= min{qji , 0}, qij+ = max{qij , 0} e qij+ = max{qij , 0} para
i = 1, 2, . . . , n e j = 1, 2, . . . , n.
n
P
∂f (x)
Se a matriz Q for simétrica, então
= 2
qij xj . Os valores dos limitantes
∂xi
j=1
podem ser determinados da seguinte maneira:
ai = qii + 2
bi = qii + 2
n
X
j=1
n
X
qij−
para i = 1, 2, . . . , n
qij+
para i = 1, 2, . . . , n
j=1
Estes limitantes são utilizados no método B&B mostrado no Algoritmo 3.9.1.
Exemplo 3.6. Sejam

f (x) = xT Qx
1

e Q =  −2
3

−2
3

4
5 
5 −6
51
Calculam-se os limitantes da seguinte maneira:
a1
a2
a3
= 1 + 2(−2),
= 4 + 2(−2),
= −6,
b1
b2
b3
= 1 + 2(3)
= 4 + 2(5)
= −6 + 2(3 + 5)
ou seja,

−3


a= 0 
−6


x∗2
e

7


b =  14 
10
A partir das condicionais em (3.14), concluı́mos que uma solução ótima para este exemplo, tem
= 0.
3.9.2
Branch and Bound
Branch and Bound (B&B) é um esquema que permite encontrar soluções ótimas para
problemas de otimização combinatória, fazendo uso de uma busca em árvore com uma
estratégia de divisão e conquista. O B&B divide o problema em vários subproblemas
disjuntos, de forma que ao resolvê-los encontra-se também uma solução para o problema
original. A decomposição em subproblemas pode ser visualizada como uma árvore de
enumeração, onde o vértice raiz representa o problema original, cada vértice interno, na
árvore de enumeração, é um subproblema e os vértices folhas fornecem soluções viáveis
para o problema original. Uma caracterı́stica deste método é que pode-se encontrar limitantes, superiores ou inferiores, para os subproblemas e, ao utilizá-los, pode-se descartar
parte da enumeração.
É possı́vel implementar o método B&B fazendo busca em profundidade, em largura ou
uma combinação destas. O Algoritmo 3.9.1 é um método B&B que utiliza uma busca em
profundidade. Neste algoritmo considera-se que o problema UQP é de minimização. Vale
ressaltar que este método aparece na referência [48], implementado em paralelo utilizando
MPI (Message Passing Interface), usando um modelo mestre-escravo. Na Seção 5.2.2 (no
capı́tulo de contribuições) apresentamos uma implementação paralela deste método B&B
com GPUs, utilizando um modelo fork-join.
No restante desta seção assumimos que a matriz Q é simétrica, tal como foi assumido
na referência [48].
Uma solução inicial é gerada pelo método Gradient Midpoint Method (Algoritmo 3.8.4),
então melhorada pelo método Tabu Search (Algoritmo 3.8.1) e fornecida como entrada
para o método B&B, apresentado no Algoritmo 3.9.1, através do vetor x∗ e tem OP T =
f (x∗ ). Denotamos por qij− = min{qij , 0} e qij+ = max{qij , 0} para i = 1, 2, . . . , n e j =
52
1, 2, . . . , n. As seguintes variáveis e constantes são usadas na descrição do Algoritmo 3.9.1.
qij
n
OP T
x∗
lev
p1 , . . . , plev
plev+1 , . . . , pn
xp1 , xp2 , . . . , xplev
g
lb
ub
p
N SU BP
Coeficientes na linha i e coluna j na matriz Q;
Número de variáveis de uma instância;
Valor da melhor solução encontrada até o momento;
Melhor solução encontrada até o momento;
Nı́vel atual da árvore de enumeração do B&B;
Índices das variáveis fixadas no subproblema atual;
Índices das variáveis livres no subproblema atual;
Variáveis fixadas;
Limitante inferior para f (x);
Limitante inferior à ∇f (x) ∈ [0, 1]n ;
Limitante superior à ∇f (x) ∈ [0, 1]n ;
Vetor de permutações;
Número de subproblemas resolvidos.
Cada iteração do loop na Linha 5 trabalha com um vértice da árvore de enumeração
do B&B. Uma pilha, estrutura de dados, é utilizada para armazenar informações de
subproblemas quando um branching (ramificação da árvore) é necessário. Na Linha 2,
a pilha é iniciada com o valor −1 para a variável lev, que indica que a pilha está vazia.
O algoritmo termina quando este valor é desempilhado.
Na Linha 4, mostramos como calcular os limitantes do gradiente da função f (x) =
x Qx. Na Linha 6, calcula-se o limitante inferior para o valor de uma solução ótima para
o subproblema corrente. A fórmula utilizada é a seguinte:
T
n X
n
X
g =
i=1 j=1
+
lev X
lev
X
qij−
lev
lev X
n
X
X
−
− 2
qpi pj (1 − xpi ) +
qp−i pj (1 − xpi )
i=1 j=i+1
qp+i pj xpi xpj
i=1
(3.15)
i=1 j=1
Na Linha 7, verificamos se é possı́vel podar um vértice interno, g ≥ OP T , ou um
vértice folha é encontrado, lev = n. No último caso, uma nova solução foi encontrada
e é avaliada na Linha 8. Na Linha 10 desempilha-se as informações de um subproblema
ainda não resolvido. Na Linha 11, altera-se o valor da variável xplev para resolver um
outro subproblema. O número de subproblemas resolvidos, N SU BP , é incrementado na
Linha 13. Este valor é usado somente para medidas estatı́sticas, mas também pode ser
utilizado como critério de parada como apresentado em [49].
Se nenhuma das condições da Linha 7 for satisfeita, uma busca em profundidade é
iniciada na Linha 15. Se o nı́vel de profundidade na árvore de anumeração é diferente de
zero (lev 6= 0), então atualiza-se os limitantes dos gradientes da função. Da Linha 15 até
53
a Linha 21, é feita uma atualização eficiente, com complexidade computacional linear, dos
limitantes do vetor gradiente para as variáveis ainda não fixadas (isto é, variáveis livres).
Esta atualização leva em consideração o valor da última variável fixada. Esses limitantes
são testados na Linha 24, verificando se alguma variável pode ter seu valor fixado. Se
algum limitante inferior, lbi , for maior ou igual a zero ou um limitante superior, ubi , for
menor ou igual a zero, então a variável correspondente, xi , tem seu valor fixado como
apresentam as Linhas de 25 até 29. Uma vez que a diferença entre os limitantes vão
diminuindo a cada nı́vel que se desce na árvore de enumeração, as variáveis são fixadas de
maneira dinâmica. Este processo é chamado pelos autores de pré-processamento dinâmico.
Se nenhuma variável pode ser fixada, então a regra da Linha 35 é utilizada. A regra
define a próxima variável livre a ser fixada. A variável livre escolhida é aquela que possivelmente não conseguirá ser fixada nos nı́veis subsequentes da árvore de enumeração. Por
isso as variáveis que têm maior possibilidade de serem fixadas em iterações seguintes, são
deixadas livres. Depois que a variável é escolhida, o seu valor é determinado nas Linhas
36 a 43, definindo o valor que menos incrementa o limitante inferior. Este procedimento
escolhe um subproblema que será resolvido e o outro subproblema é armazenado na pilha,
Linha 44, para posterior análise. Na Linha 46, a variável que controla a altura da árvore
de enumeração, lev, é incrementada. Na Linha 47, é feita uma troca de valores no vetor
de permutação.
s
x0 = 0
s
x1 = 0
s
3
0
x0 = 1
s
1
x1 = 0
x1 = 1
s
4
s
5
2
x1 = 1
s
6
Figura 3.4: Exemplo de uma árvore de enumeração do Branch and Bound
A Figura 3.4 apresenta um exemplo de uma árvore de enumeração para um B&B. Nesta
árvore o nó raiz S0 representa o problema original, os nós folhas S3 , S4 , S5 e S6 representam
soluções viáveis para o problema. O algoritmo percorre esta árvore calculando limitantes
para cada nó explorado e verificando a viabilidade de explorar os nós filhos.
Algoritmo 3.9.1: Método Branch and Bound com busca em profundidade
1
2
3
4
5
6
7
8
Entrada: n ∈ N∗ , Q ∈ Qn×n simétrica, x∗ ∈ Qn , OP T ∈ Q
Saı́da: x ∈ {0, 1}n , f (x) ∈ Q
pi ← i para i = 1, . . . , n
empilha({-1,-,-,-},stack)
lev ← 0, N SU BP ← 0
n
n
P
P
−
+
lbi ← 2
qij
+ qii , ubi ← 2
qij
+ qii para i = 1, . . . , n
j=1
j=1
j6=i
j6=i
enquanto lev 6= −1 faça
g ← Calcula o limitante inferior g
se g ≥ OP T ou lev = n então
se g < OP T então OP T ← g,
x∗ ← x
9
desempilha({lev, lb, ub, g},stack)
se lev 6= −1 então xplev ← 1 − xplev
10
11
12
N SU BP ← N SU BP + 1
senão
se lev 6= 0 então
se xplev = 1 então
lbpi ← lbpi + 2qp+i plev
para i = lev + 1, . . . , n
ubpi ← ubpi + 2qp−i plev para i = lev + 1, . . . , n
senão
lbpi ← lbpi − 2qp−i plev
para i = lev + 1, . . . , n
ubpi ← ubpi − 2qp+i plev para i = lev + 1, . . . , n
fim
fim
entrou = falso
para i = lev até n faça
se lbpi ≥ 0 ou ubpi ≤ 0 então
se ubpi ≤ 0 então
x pi ← 1
senão
x pi ← 0
fim
entrou = verdadeiro
Sai do loop
fim
fim
se entrou = falso então
i ← j onde δj = max{min(−lbpt , ubpt )} para t = lev + 1, . . . , n
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
t
x pi ← 0
gAux ← Calcula o limitante inferior g
x pi ← 1
g ← Calcula o limitante inferior g
se gAux < g então
x pi ← 0
g ← gAux
fim
empilha({lev+1, lb, ub, g},stack)
36
37
38
39
40
41
42
43
44
fim
lev ← lev + 1
plev ↔ pi %Troca de valores de plev e pi
45
46
47
fim
48
49
fim
54
Capı́tulo 4
Programação Paralela com GPUs
Paralelizar a computação implica na capacidade de dividir o problema em problemas
menores e conseguir resolvê-los de forma eficaz. Alguns problemas têm caracterı́stica paralela, ou seja, são problemas que se adaptam facilmente à computação paralela. Como
exemplo de uma tarefa com caracterı́stica paralela citamos a soma de vetores, onde cada
unidade de processamento pode ser responsável pela soma de uma parte do vetor. Embora o paralelismo nesta situação melhore bastante o desempenho de um algoritmo, há
problemas em que o paralelismo é ineficaz e por vezes a performance do programa paralelo
é pior que a do algoritmo sequencial.
Nas seções que seguem, apresentamos os conceitos sobre computação paralela que
são utilizados nesta dissertação. Na Seção 4.1 apresentamos a distinção entre CPUs e
GPUs. Na Seção 4.2 apresentamos os conceitos de multicore e manycore. Na Seção 4.3
descrevemos um histórico das GPUs, seus motivos de interesse pela comunidade cientı́fica
e a evolução que elas tiveram ao longo dos últimos anos. Na Seção 4.9 tratamos da
arquitetura aberta de programação paralela chamada OpenCL. Na Seção 4.4 discorremos
sobre a arquitetura CUDA criada pela NVIDIA. Finalmente na Seção 4.5 descrevemos
alguns detalhes das GPUs, que utilizam a última geração da arquitetura CUDA.
4.1
CPUs e GPUs
Tradicionalmente, a diferença fundamental entre os processadores (CPUs) as placas gráficas (GPUs) é o fato de que as CPUs são otimizadas para cálculos sequenciais, enquanto
as GPUs são otimizadas para cálculos massivamente paralelos (processando gráficos 3D).
Esta diferença era bem mais clara quando as GPUs começaram a ser comercializadas.
Entretanto, com o inı́cio do uso de shaders (pequenos aplicativos destinados a executar tarefas especı́ficas na composição de cenas) elas ganharam a capacidade de também
executar código sequencial, como os processadores.
55
CAPÍTULO 4. PROGRAMAÇÃO PARALELA COM GPUS
56
Embora as GPUs sejam otimizadas para o processamento de shaders e gráficos 3D,
elas podem ser usadas para várias tarefas computacionais, indo desde a decodificação de
vı́deos a aplicações cientı́ficas.
4.2
Multicore e Manycore
Com o avanço da indústria de materiais tornou-se possı́vel colocar em um chip de silı́cio
cada vez mais transistores, permitindo mais funcionalidades aos processadores. Junto
com esta evolução veio o aumento da velocidade do clock que permitiu processamentos
muito rápidos. Chegou-se a um momento crı́tico, em que uma placa de silı́cio, como
é feita atualmente, não suporta velocidades maiores, pois esquentam muito e rompem
as trilhas. A solução encontrada foi colocar mais núcleos de processamento dentro de
um processador, tornando as tarefas possivelmente mais rápidas, não pela velocidade de
processamento, mas sim pelo aumento da quantidade de núcleos de processamento.
Figura 4.1: Multicore e Manycore. Fonte: NVIDIA [42]
Os processadores podem ser categorizados em Multicore e Manycore dependendo da
quantidade de núcleos de processamento.
O modelo de GPU dedica mais transistores para as unidades de execução, diminuindo
a área de controle e cache.
4.3
Histórico das GPUs
Com o passar dos anos a exigência de aprimoramento no ambiente gráfico computacional
aumentou. Gráficos que antes eram 2D agora são representados em 3D, com uma qualidade melhor. Este fato impulsionou os fabricantes de GPUs a se aprimorarem, o que
gerou uma linha de produtos com uma grande capacidade de processamento paralelo e
tornou as GPUs programáveis.
57
Esforços para explorar as GPUs com aplicações não gráficas, programas de propósito geral, estão em andamento desde 2003 e este tipo de programação é conhecida como
Computação de Propósito Geral com GPUs (em inglês, General-Purpose Computation
on Graphics Processing Units - GPGPU). A GPGPU atraiu a atenção de muitas pessoas
porque apresentou um bom desempenho. A princı́pio esse modo de programar possuiu algumas inconveniências. Primeiro, ela exigiu que os programadores conhecessem muito bem
as APIs (Application Programming Interface) gráficas e a arquitetura da GPU utilizada,
ou seja, apesar de possuir uma linguagem de programação de alto nı́vel, o conhecimento
especı́fico do hardware ainda era necessário. Segundo, a GPU não estava preparada para
computação de propósito geral. Os programas tinham que ser expressos em termos de linguagens gráficas utilizando texturas e coordenadas de vértices, o que deixava o programa
complexo. Terceiro, operações básicas como leituras e escritas aleatórias na memória não
eram suportadas, o que restringia muito a programação. Por último, a falta de suporte
a operações com ponto flutuante de precisão dupla foi algo que impossibilitou que várias
aplicações cientı́ficas fossem executadas com GPUs.
Para superar estas dificuldades, as empresas fabricantes de GPUs incorporaram suporte às necessidades mais básicas para a programação de propósito geral, proporcionando
um grande aumento de interesse dos desenvolvedores de aplicativos de alto desempenho
e de programação paralela. Com a evolução das GPUs, foi possı́vel realizar operações
com pontos flutuantes de maneira rápida, permitindo assim o desenvolvimento de uma
variedade de aplicações cientı́ficas.
Com a finalidade de facilitar e difundir a programação em GPGPU, foram criadas
arquiteturas para dar suporte ao desenvolvimento de softwares utilizando GPUs, dentre
elas surgiram OpenCL e CUDA.
Inicialmente o potencial de processamento das GPUs era só um pouco maior do que
o das CPUs, mas com o passar dos anos as GPUs se desenvolveram e aumentaram largamente esta diferença. A Figura 4.2 mostra um gráfico comparativo entre o potencial
de processamento das GPUs e o das CPUs. Nota-se que em 2003 a diferença entre as
GPUs e as CPUs era relativamente pequena, tanto para o Theoretical GB/s (largura de
banda) como para o Theoretical GFLOP/s (capacidade de processamento). Esta diferença
cresceu significativamente desde então. As dificuldades de processamento com operações
de ponto flutuante de precisão dupla foram superadas com a criação da linha de placas
Tesla C2050 em 2009 [42], que deixou as GPUs com mais que o dobro de GFLOP/s com
relação as CPUs.
Devido a esse poder de processamento, as GPUs se tornaram importantes para a
nova fase de processamento de alto desempenho. Hoje em dia alguns clusters possuem
uma mescla de CPUs e GPUs, objetivando alcançar um melhor poder de processamento.
O futuro da computação de alto desempenho tende a uma programação heterogênea,
58
Theoretical
GFLOP/s
Theoretical
GB/s
3250
200
3000
180
CPU
2750
GPU
2500
160
140
2250
120
2000
NVIDIA GPU Single Precision
NVIDIA GPU Double Precision
Intel CPU Single Precision
Intel CPU Double Precision
1750
100
1500
80
1250
60
1000
750
40
500
20
250
0
2003 2004 2005 2006 2007 2008 2009 2010 2011 2012
0
Sep-01
(a)
Jun-04
Mar-07
Dec-09
Aug-12
(b)
Figura 4.2: (a) Largura de banda da memória. (b) Operações por segundo com ponto
flutuante. Fonte: NVIDIA [42]
envolvendo processadores multicore e manycore.
4.4
Arquitetura CUDA
Compute Unified Device Architecture (CUDA) é uma arquitetura de computação paralela de propósito geral desenvolvida pela empresa NVIDIA. Nesta arquitetura é possı́vel
acelerar o desempenho dos programas, utilizando as GPUs como um co-processador matemático paralelo. A arquitetura CUDA explora este poder de processamento para que
os desenvolvedores de softwares possam resolver problemas, que aparecem não só em aplicações gráficas, incluindo processamento de vı́deos, áudio e simulação de efeitos fı́sicos,
exploração de gás e petróleo, design de produtos, softwares de criptografia, processamento
de imagens na área médica, simulações biológicas e pesquisa cientı́fica.
CUDA apresenta-se ao programador como uma extensão da linguagem C/C++. O
fluxo de processamento de um programa escrito em CUDA não é complexo. No inı́cio do
processamento alguns dados são copiados da memória principal para a memória da GPU.
Depois disto o processamento é feito pela GPU, que então executa as tarefas. Por fim,
alguns dados são copiados da memória da GPU para a memória principal do computador.
CUDA utiliza o padrão SIMT(Single Instruction, Multiple Thread) [42], onde o código
destinado ao kernel (nome dado à função que é executada na GPU) é executado por todas
as threads.
4.5
59
Arquitetura Kepler GK104
A fonte principal do texto desta seção é o Whitepaper NVIDIA GeForce GTX 680 [40] é
a fonte principal do texto desta seção.
Kepler é uma arquitetura da NVIDIA para GPUs, sucessora da Fermi. Ao desenvolver
a Kepler a NVIDIA buscou ter um melhor desempenho por watt, velocidade e prover
mais facilidade de programação. A Figura 4.3 mostra a placa GeForce GTX 680 que é
construı́da com arquitetura Kepler.
Figura 4.3: GeForce GTX 680
4.5.1
Visão Geral da Arquitetura Kepler
A arquitetura Kepler GK104 é construı́da com cerca de 3,5 bilhões de transistores e um
total de 1536 CUDA Cores (núcleos de processamento). Os CUDA Cores são as menores
unidades de computação da GPU e são organizados em 8 unidades chamadas Streaming
Multiprocessor (SMX), que contém 192 CUDA Cores.
Alguns detalhes da arquitetura Kepler GK104 são apresentados na Tabela 4.1, onde
SFU são unidades de funções especiais, destinadas a funções transcendentais (ex: seno,
cosseno, tangente de ângulos) e instruções de interpolação gráficas, LD/ST são unidades
de carga e armazenamento, responsáveis por transportar valores entre as memórias da
GPU, Tex são unidades que realizam o filtro de texturas e Warp Schedular é o tamanho
do escalonador de warp 1 .
4.6
Memórias
As referências [42, 43] são as principais fontes desta seção.
1
Warp é a menor unidade executável de paralelismo em CUDA, ela contém 32 threads que são executadas de forma sincronizadas.
Figura 4.4: Diagrama da arquitetura Kepler GK104
Elementos
CUDA Cores
SFU
LD/ST
Tex
Warp Scheduler
Unidades
1536
256
256
128
32
Tabela 4.1: Detalhes da arquitetura Kepler GK104.
60
61
As GPUs possuem várias áreas de memória, com diferentes caracterı́sticas que podem
influenciar diretamente no desempenho dos programas. As memórias disponı́veis para o
desenvolvedor são: registradores, compartilhada, global, local, constantes e textura como
apresentamos na Tabela 4.2. Em [34], discute-se sobre as vantagens do uso de alguns tipos
de memória em um algoritmo de busca local.
Memória
Registrador
Compartilhada
Global
Local
Constante
Textura
Localização: Dentro
ou fora do chip
Dentro
Dentro
Fora
Fora
Fora
Fora
Cache
n/a
n/a
Sim
Sim
Sim
Sim
Tipo de
Acesso
R/W
R/W
R/W
R/W
R
R
Escopo
1 thread
Todas thread no Bloco
Todas thread + CPU
1 thread
Todas thread + CPU
Todas thread + CPU
Tempo de Vida
Thread
Thread
Thread
Thread
Thread
Thread
Tabela 4.2: Detalhes das Memórias
Registradores
É o espaço reservado para variáveis privadas para uma thread. O acesso a registradores é
extremamente rápido e possui uma latência de poucos ciclos.
Memória Compartilhada
A memória compartilhada é uma memória que é comum entre todas as threads de um
bloco. O acesso a esta memória é rápido e o seu tamanho varia dependendo da arquitetura.
Memória Global
A memória global é a maior área de memória disponı́vel dentro da GPU. Esta é uma memória de acesso lento. Seu acesso pode ser melhorado quando feito um acesso combinado.
Acesso combinado à memória global
Quando as threads de um mesmo warp acessam o mesmo segmento da memória global, os
dados requisitados são reunidos em uma mesma transação e levados para as threads. Esta
é uma forma de se otimizar o acesso à memória global e aumentar a largura de banda. A
memória global é a única que possui este tipo de acesso.
62
Memória Local
Esta memória tem este nome devido ao seu escopo e não por causa da sua localização fı́sica.
De fato, a memória local fica em uma área fora do chip como a memória global. Assim o
acesso à memória local é tão custoso quanto a memória global. A memória local é utilizada
para armazenar variáveis automáticas. Isto é feito pelo compilador nvcc quando determina
que não há espaço suficiente para armazenar as variáveis nos registradores. Grandes
estruturas ou matrizes que consomem muito espaço, são sucetiveis a serem alocadas na
memória local.
Memória de Constante
Esta é uma memória somente de leitura com cache. Ela é uma memória de acesso rápido
e destinada a guardar valores que não serão alterados durante a execução do kernel.
Memória de Textura
Esta é uma memória somente de leitura com cache. Ela é uma memória de acesso rápido
e normalmente é destinada para guardar as texturas em aplicações gráficas. Mas também
é possı́vel utilizá-la para armazenar constantes em aplicações cientı́ficas.
4.7
Limitações da Arquitetura CUDA
A arquitetura CUDA possui limitações que devem ser consideradas. Exemplo disto é o
tempo gasto para realizar cópias entre a memória RAM e a memória interna da GPU, isto
pode diminuir o desempenho dos programas. Entretanto, isto varia com o barramento do
sistema.
Outro problema a ser considerado refere-se à compatibilidade do software desenvolvido
dessa forma. CUDA é uma tecnologia da NVIDIA e só funciona com placas de vı́deo
fabricadas por esta empresa. Uma alternativa para essa limitação é utilizar OpenCL, cujo
desenvolvimento avança mais lentamente que a CUDA por possuir objetivos mais gerais.
Outro fato a ser considerado é que embora desenvolver um programa utilizando CUDA
seja relativamente simples, manter todos os cores ocupados o maior tempo possı́vel pode
exigir muito trabalho. Isto se deve às limitações de memórias de acesso rápido dentro das
GPUs e da própria caracterı́stica dos multiprocessadores utilizados.
4.8
63
Compilação do Código em CUDA
O modelo de programação da arquitetura CUDA é o ANSI C estendido com certas construções e palavras-chave. A GPU é tratada como um co-processador paralelo, a parte
sequencial do código é executada no host (CPU) e a parte paralela no device (GPU).
Os kernels podem ser escritos com um conjunto de instruções da arquitetura CUDA,
chamado PTX (Parallel Thread eXecution). Entretanto, é mais fácil realizar uma programação de alto nı́vel, como em C/C++. Para que o compilador saiba qual parte executar
em cada dispositivo, no código é incluı́do alguns comandos que especificam se a função será
executada no host ou no device, desta forma o compilador (NVCC) sabe como processar
cada parte do código fonte.
O NVCC é um compilador que facilita o processo de compilação do código C/C++
ou PTX, efetuando a chamada de um conjunto de ferramentas que implementam etapas
de compilação diferentes como apresenta a Figura 4.5.
Código PTX
Aplicação
Cuda Driver
GPU
NVCC
Código C
Compilador C
Processador
Figura 4.5: Compilação de código CUDA
4.9
Linguagem OpenCL
Open Computing Language (OpenCL) é uma arquitetura que possui um padrão aberto
para a programação de aplicações paralelas para sistemas heterogêneos, gerido pelo Khronos Group. Esta arquitetura da suporte a uma ampla gama de aplicações para sistemas
embarcados.
A proposta do OpenCL é executar o mesmo código de forma transparente em diversos
tipos de arquiteturas, obtendo uma boa performance do hardware. Dentre os vários tipos
de processadores que o OpenCL dá suporte, encontram-se as GPUs.
Os benefı́cios de uma plataforma unificada são imensos, mas com eles vêm também
os desafios de extrair o melhor desempenho em cada placa gráfica. O avanço do OpenCL
com as GPUs é mais lento do que as arquiteturas, softwares e compiladores distribuı́dos
pelos fabricantes, que contudo não trazem o benefı́cio da generalização.
64
Capı́tulo 5
Contribuições e Implementações
Paralelas
Conforme dito nos Capı́tulo 1, dois dos três objetivos desta pesquisa são: criar métodos
e implementá-los de forma sequencial e paralela, para resolver o seguinte problema de
otimização combinatória.
max f (x) = xT Qx
x ∈ {0, 1}n
sujeito a:
Nos capı́tulos anteriores denotamos este problema pela sigla UQP. Lembramos que o
UQP pertence à classe NP-difı́cil. Neste capı́tulo apresentamos as nossas contribuições ao
desenvolvimento de métodos para resolver instâncias do UQP e descrevemos implementações sequenciais e paralelas com GPUs.
Tanto nas abordagens heurı́sticas quanto nas exatas, faz-se necessário efetuar o cálculo
do valor da função objetivo diversas vezes. Assim, saber fazer este cálculo de maneira
rápida é primordial. A Seção 5.1 trata deste assunto.
5.1
Cálculos do Valor da Função Objetivo e Limitantes Inferiores
Conforme exposto nas Seções 3.8.1, 3.8.2, 3.8.3 e 3.9.2, os métodos Tabu Search, Busca
Local, Variable Neighborhood Search e Branch and Bound, necessitam computar diversas
vezes o valor de f (x) = xT Qx. Esta computação requer O(n2 ) operações e pode ser
determinante para o bom desempenho de um método. No caso do Branch and Bound
precisa-se computar diversas vezes o valor da função g, limitante inferior ao valor de uma
65
CAPÍTULO 5. CONTRIBUIÇÕES E IMPLEMENTAÇÕES PARALELAS
66
solução ótima.
Nesta seção apresentamos a forma básica de se efetuar o cálculo do valor da função
objetivo e também formas mais eficientes, que aproveitam o valor de uma solução já
computada.
5.1.1
Cálculo do Valor da Função Objetivo na Forma Básica
O cálculo de f (x) = xT Qx na forma básica faz:
f (x) = xT Qx =
n X
n
X
i=1
qij xj xi
j=1
É fácil ver que este cálculo de f (x) requer n2 + n operações de multiplicação e (n − 1)2
operações de adição.
Exemplo 5.1. Cálculo do valor da função objetivo f (x) = xT Qx, onde Q é uma matriz
assimétrica.

Se xT = [1,
0,
1

0] e Q =  4
7
Se alterarmos o vetor xT de [1,

f (x)
=
[1,
1,
1

0]  4
7

−2
3

5
6  então f (x) = 1.
−8 −9
0,
0] para [1,
1,
0] então:


1
−2
3


5
6  1 
0
−8 −9

=
[1 × 1 + 1 × 4 + 0 × 7,
1 × (−2) + 1 × 5 + 0 × (−8),

1


1 × 3 + 1 × 6 + 0 × (−9)]  1 
0


1
 
= [5, 3, 9]  1 
0
= 1 × 5 + 1 × 3 + 0 × 9 = 8.
Esta maneira de recálculo utilizou 12 operações de multiplicação e 8 operações de adição, isto é, n2 + n
e n2 − 1 para n = 3. Quando a matriz é simétrica utiliza-se o mesmo número de operações, tanto para
as multiplicações quanto para as adições.
5.1.2
67
Recálculo do Valor da Função Objetivo com Mudança do
Valor de Uma Variável
Esta maneira de recálculo leva em conta o valor da solução x e a variável xi , que foi modificada. Desta maneira, é necessário utilizar apenas uma parte da matriz Q para efetuar
o recálculo. Notamos que o recálculo pode ser feito quando a instância possui matriz
assimétrica ou simétrica. No segundo caso realiza-se menos operações que o primeiro.
Em muitos casos, é útil explorar a vizinhança de uma solução, sem ter que gerar os
vetores solução da vizinhança, como é o caso quando fazemos esta investigação de forma
paralela, onde cada thread teria que alterar o vetor solução. Desta forma seria necessário
replicar o vetor, o que consumiria bastante memória dos registradores (Seção 4.6), que
é escassa nas GPUs ou utilizar a memória global, que tem um acesso mais lento (Seção
4.6).
O que apresentamos nesta subseção é uma forma de efetuar o recálculo do valor da
função objetivo sem alterar o vetor solução, sendo assim o mesmo vetor pode ser compartilhado por todas as threads. O seguinte método efetua o recálculo do valor da função
objetivo sem precisar alterar o vetor solução, quando apenas uma variável, xi , muda de
valor.
Sejam f (x) = xT Qx, x ∈ {0, 1}n e Q ∈ Qn×n . Então:

f (x) =
h
=
h
x1 , x 2 , . . .
x1 , x 2 , . . .
 
q11 q12 . . . q1n
x1
 
i
 q21 q22 . . . q2n   x2 
 
xn 
.. . .
.. 
 ..
 . 
.
.
.   .. 
 .
qn1 qn2 . . . qnn
xn
 n

P
 j=1 q1j xj 
 n

P

i  q2j xj 


xn  j=1



..


.
 n

P


qnj xj
j=1
= x1
n
X
j=1
q1j xj + x2
n
X
j=1
q2j xj + · · · + xn
n
X
qnj xj
j=1
Os resultados apresentados nesta seção foram obtidos de forma independente, embora
a Fórmula (5.1) apareça em [33] sem uma prova.
Proposição 5.1. Sejam f (x) o valor de xT Qx para um dado x ∈ {0, 1}n e Q ∈ Qn×n
uma matriz assimétrica. Se y é um vetor idêntico à x, exceto pela i-ésima posição onde
68
yi = 1 − xi com i ∈ {1, 2, . . . , n}, e se f (x) já estiver calculado, então o valor de f (y) pode
ser determinado, sem utilizar informações do vetor y, da seguinte maneira:
n
X
f (y) = f (x) + (1 − 2xi ) qii +
(qij + qji )xj
(5.1)
j=1
j6=i
Esta maneira de fazer o recálculo utiliza n + 1 operações de multiplicação e 2n operações
de adição.
Prova:
Suponha que x ∈ {0, 1}n , Q ∈ Qn×n é uma matriz assimétrica e y é um
vetor idêntico à x exceto pela i-ésima posição, onde yi = 1 − xi com i ∈ {1, 2, . . . , n}.
Pode-se determinar f (y) a partir do valor de f (x) subtraindo as parcelas que envolvem
xi e adicionando aquelas que envolvem 1 − xi . Como xi ∈ {0, 1}, segue que x2i = xi e
(1 − xi )2 = 1 − xi .
Então:
f (y) = f (x) − xi
+(1 − xi )
= f (x) − xi
n
X
qij xj − xi
n
X
j=1
j=1
j6=i
n
X
j6=i
qji xj − qii x2i
qij xj + (1 − xi )
n
X
j=1
j=1
j6=i
n
X
j6=i
qji xj + qii (1 − xi )2
(qij + qji )xj − qii xi
j=1
+(1 − xi )
j6=i
n
X
(qij + qji )xj + qii (1 − xi )
j=1
j6=i
n
X
= f (x) + (1 − 2xi )
(qij + qji )xj − qii xi + qii − qii xi
j=1
= f (x) + (1 − 2xi )
j6=i
n
X
(qij + qji )xj + qii (1 − 2xi )
j=1
j6=i
n
X
= f (x) + (1 − 2xi ) qii +
(qij + qji )xj
j=1
j6=i
Exemplo 5.2. Se f (x) = xT Qx, x = [1, 0, 0], i = 2

1

Q= 4
7

−2
3

5
6 
−8 −9
e
69
então
f (y)
n
X
= f (x) + (1 − 2xi ) qii +
(qij + qji )xj
j=1
j6=i
=
1 + (1 − 2 × 0) 5 + (4 + (−2)) × 1 + (6 + (−8)) × 0
=
1 + (1)(5 + 2 × 1 + (−2) × 0)
=
1 + (1)(7)
=
8
Esta maneira de fazer o recálculo utilizou 4 multiplicações e 6 adições, que são respectivamente n + 1 e
2n para n = 3, conforme dito anteriormente.
Se a instância do problema possuir uma matriz simétrica, é possı́vel reduzir o número
de operações envolvidas no recálculo do valor da função objetivo.
Corolário 5.1. Sejam f (x) o valor de xT Qx para um dado x ∈ {0, 1}n e Q ∈ Qn×n
uma matriz simétrica. Se y é um vetor idêntico à x exceto pela i-ésima posição, onde
yi = 1 − xi com i ∈ {1, 2, . . . , n}, e f (x) já estiver calculado, então o valor de f (y) pode
ser determinado, sem utilizar informações o vetor y, da seguinte maneira:
n
X
f (y) = f (x) + (1 − 2xi ) qii + 2
qij xj
(5.2)
j=1
j6=i
Esta maneira de fazer o recálculo utiliza n+2 operações de multiplicação e n+1 operações
de adição.
Prova:
Como a matriz Q é simétrica, segue que qij = qji . Então:
f (y) = f (x) + (1 − 2xi ) qii +
n
X
(qij + qji )xj
j=1
j6=i
n
X
= f (x) + (1 − 2xi ) qii + 2
qij xj
j=1
j6=i
Exemplo 5.3. Se f (x) = xT Qx, x = [1, 0, 0], i = 2

1

Q =  −2
3

−2
3

5
6 
6 −9
e
70
Então
f (y)
n
X
= f (x) + (1 − 2xi ) qii + 2
qij xj
j=1
j6=i
=
1 + (1 − 2 × 0) 5 + 2 × ((−2) × 1 + 6 × 0)
=
1 + (1)(5 + (−4))
=
1 + (1)(1)
=
2
Esta maneira de fazer o recálculo utilizou 5 multiplicações e 4 adições, que são respectivamente n + 2 e
n + 1 para n = 3, conforme dito anteriormente.
Em resumo, na Fórmula (5.1) os números de operações são:
Multiplicações:
Adições:
n−1+1+1=n+1
2(n − 1) + 1 + 1 = 2n − 2 + 2 = 2n
Enquanto na Fórmula (5.2), os números de operações são:
n−1+1+1+1=n+2
Multiplicações:
n−1+1+1=n+1
Adições:
5.1.3
Recálculo do Valor da Função Objetivo com Mudança do
Valor em Duas Variáveis
Usando um raciocı́nio similar ao descrito na Seção 5.1.2, podemos obter uma fórmula
geral para o recálculo do valor da função objetivo considerando que várias variáveis têm
seus valores alterados.
Teorema 5.1. Sejam x ∈ {0, 1}n , f (x) = xT Qx e Q ∈ Qn×n uma matriz assimétrica.
Se y é um vetor idêntico à x exceto por duas posições distintas i, k ∈ {1, 2, . . . , n}, onde
yi = 1 − xi e yk = 1 − xk , e f (x) já estiver calculado, então o valor de f (y) pode ser obtido
por:
n
X
f (y) = f (x) + (1 − 2xi ) qii +
(qij + qji )xj
j=1
j6=i,k
n
X
+(1 − 2xk ) qkk +
j=1
j6=i,k
(qkj + qjk )xj + (qik + qik )(1 − xi − xk ) (5.3)
71
Esta maneira de fazer o recálculo utiliza 2n + 1 operações de multiplicação e 4n + 2
operações de adição.
Prova: Sejam x ∈ {0, 1}n , f (x) = xT Qx e Q ∈ Qn×n uma matriz assimétrica. Se y é um
vetor idêntico à x exceto por duas posições distintas i, k ∈ {1, 2, . . . , n}, onde yi = 1 − xi
e yk = 1 − xk , e f (x) já estiver calculado, então pode-se determinar f (y) a partir de f (x)
subtraindo as parcelas que envolvem xi e xk e adicionando aquelas que envolvem (1 − xi )
e (1 − xk ).
A Figura 5.1 mostra os ı́ndices na matriz Q que precisam ser considerados para o
cálculo do valor de f (y). Assim,
f (y) = f (x) − xi
−xk
n
X
qij xj − xi
n
X
j=1
j=1
j6=i,k
n
X
j6=i,k
n
X
qkj xj − xk
j=1
qji xj − qii x2i
qjk xj − qkk x2k − qik xi xk − qki xk xi
j=1
j6=i,k
n
X
j6=i,k
+(1 − xi )
qij xj + (1 − xi )
j=1
+(1 − xk )
n
X
qji xj + qii (1 − xi )2
j=1
j6=i,k
n
X
qkj xj + (1 − xk )
j6=i,k
n
X
j=1
j=1
j6=i,k
j6=i,k
qjk xj + qkk (1 − xk )2
+qki (1 − xi )(1 − xk ) + qik (1 − xi )(1 − xk )
n
n
X
X
= f (x) − xi
(qij + qji )xj − qii xi − xk
(qkj + qjk )xj
j=1
j=1
j6=i,k
j6=i,k
−qkk xk − (qik + qki )xi xk
n
n
X
X
(qkj + qjk )xj
(qij + qji )xj + qii (1 − xi ) + (1 − xk )
+(1 − xi )
j=1
j=1
j6=i,k
j6=i,k
+qkk (1 − xk ) + (qik + qki )(1 − xi )(1 − xk )
n
X
= f (x) + (1 − 2xi )
(qij + qji )xj + qii (1 − 2xi )
j=1
+(1 − 2xk )
j6=i,k
n
X
(qkj + qjk )xj + qkk (1 − 2xk )
j=1
j6=i,k
+(qik + qki )(1 − xi )(1 − xk ) − (qik + qki )xi xk
72
n
X
= f (x) + (1 − 2xi ) qii +
(qij + qji )xj
j=1
j6=i,k
n
X
+(1 − 2xk ) qkk +
(qkj + qjk )xj + (qik + qik )(1 − xi − xk )
j=1
j6=i,k
i
k
i
ii
ik
k
ki
kk
Figura 5.1: Índices da matriz Q para o cálculo de f (y)
Exemplo 5.4. Se f (x) = xT Qx, x = [1, 0, 0], i = 1, k = 2, f (x) = 1 e

1

Q= 4
7

−2
3

5
6 
−8 −9
então:
f (y)
n
X
= f (x) + (1 − 2xi ) qii +
(qij + qji )xj
j=1
j6=i,k
n
X
+(1 − 2xk ) qkk +
(qkj + qjk )xj + (qik + qik )(1 − xi − xk )
j=1
j6=i,k
= 1 + (1 − 2x1 ) q11 + (q13 + q31 )x3
+(1 − 2x2 ) q22 + (q23 + q32 )x3 + (q12 + q21 )(1 − x1 − x2 )
= 1 + (1 − 2 × 1) 1 + (3 + 7) × 0
+(1 − 2 × 0) 5 + (6 + (−8)) × 0 + ((−2) + 4)(1 − 1 − 0)
=
1 − (1) + (5)
=
5
5.1.4
73
Cálculos do Limitante Inferior à f (x) no Branch and Bound
Nesta seção apresentamos um limitante inferior à f (x), Fórmula (5.4), na forma básica
para o método Branch and Bound (B&B) discutido em [48]. Apresentamos também a
nossa contribuição para este cálculo na Fórmula (5.5). Esta fórmula gera limitantes, para
quaisquer instâncias, com valores sempre maiores ou iguais aos encontrados pela Fórmula
(5.4).
Para resolver o UQP por meio de um B&B, utiliza-se uma árvore de enumeração,
B = (P, E), para representar o processo de decomposição. Sejam P um conjunto de
vértices e E um conjunto de arcos. A raiz de B denotada por P0 , representa o problema
original e os subproblemas de P0 são representados por Pi para i ∈ N∗ . O subproblema Pj
é “filho” de Pi quando Pj é gerado a partir de uma decomposição de Pi , assim (Pi , Pj ) ∈ E.
O método B&B tenta resolver P0 examinando vértices em B. Durante este processo,
é feito um teste para verificar se os vértices Pi são incapazes de produzir uma solução
ótima para P0 , podendo assim eliminar este vértice da investigação do método. Este teste
utiliza uma função g : P → Q, que gera limitantes inferiores às soluções ótimas para Pi .
Esta função precisa satisfazer três condições:
1. g(Pi ) ≤ f (Pi ) para Pi ∈ P ;
2. g(Pi ) = f (Pi ) para vértices folha de B;
3. g(Pj ) ≥ g(Pi ) se Pj é um “filho” de Pi em B.
Em [48], Pardalos e Rodgers propõem a função dada na Fórmula 5.4 como um limitante
inferior ao valor de qualquer solução ótima de P0 . A ideia por trás da fórmula é a seguinte:
considere x ∈ {0, 1}n , a função f (x) é simplesmente a soma dos coeficientes qij , onde
xi = xj = 1. Assim uma função que representa o limitante que satisfaz os três critérios de
limitante inferior é: a soma de todos os coeficientes negativos de Q ∈ Qn×n , menos a soma
dos coeficientes negativos que devem ser excluı́dos do valor da função, devido as variáveis
fixadas em 0, mais a soma dos coeficientes positivos que devem ser incluı́dos no valor
da função devido às variáveis fixadas em 1. Sejam lev o nı́vel da árvore de enumeração
(isto é, o número de variáveis com valores fixados em 0 ou 1), p1 , p2 , . . . , plev os ı́ndices
das variáveis fixadas e plev+1 , plev+2 , . . . , pn os ı́ndices das variáveis livres. A função do
limitante inferior g1 (x) é:
n
n X
X
g1 (x) =
i=1 j=1
+
lev X
lev
X
i=1 j=1
qij−
lev X
n
lev
X
X
−
−
− 2
qpi pi (1 − xpi )
i=1 j=i+1
qp+i pj xpi xpj
i=1
(5.4)
74
onde qij− = min{qij , 0} e qij+ = max{qij , 0} são os coeficientes não positivos e não negativos
de Q, respectivamente.
Quando se tem lev = n, o valor da função g1 (x) deveria coincidir com o valor de
f (x) = xT Qx. Mas conforme Exemplo 5.5 isso não ocorre para algumas instâncias.
Fizemos uma alteração na Fórmula (5.4), para que seja possı́vel calcular um limitante
inferior à f (x) do UQP para quaisquer instâncias, que apresentamos na Fórmula (5.5).
Os valores dos limitantes inferiores à f (x) gerados por (5.5) são maiores ou iguais aos
gerados por (5.4), conforme provado na Proposição 5.2.
n X
n
X
g2 (x) =
+
qij−
−
2
lev X
lev
X
i=1 j=1
i=1
lev
X
!
qp−i pi (1 − xpi )
+
i=1
qp−i pj (1
− xpi xpj ) +
j=i+1
lev
lev X
X
n
X
j=lev+1
qp+i pj xpi xpj
(5.5)
i=1 j=1
Exemplo 5.5. Se f (x) = xT Qx, x = [0, 1, 1, 0], p = [1, 2, 3, 4], n = 4, lev = 4 e



Q=



0 28 49
0

28
0 0 −7 

49
0 0
0 

0 −7 0 33
então os valores de f (x), g1 (x) e g2 (x) são:

0 28
h
i
 28
0
f (x) = 0, 1, 1, 0 
 49
0

0 −7
 
0

h
i
1

= 77, 0, 0, −7  

1
0
=
0
 
0
49
0
 
1
0 −7 
 
 
0
0 
 1
0
0 33
g1 (x)
=
4 X
4
X
75
min(qij , 0) − 2 min(q12 , 0)(1 − x1 ) + min(q13 , 0)(1 − x1 ) + min(q14 , 0)(1 − x1 )
i=1 j=1
+ min(q23 , 0)(1 − x2 ) + min(q24 , 0)(1 − x2 ) + min(q34 , 0)(1 − x3 ) + min(q11 , 0)(1 − x1 )
X
4 X
4
+ min(q22 , 0)(1 − x2 ) + min(q33 , 0)(1 − x3 ) + min(q44 , 0)(1 − x4 ) +
max(qij , 0)xi xj
i=1 j=1
=
−14 − 2 0(1 − 0) + 0(1 − 0) + 0(1 − 0) + 0(1 − 1) + (−7)(1 − 1) + 0(1 − 1)
+ 0(1 − 0) + 0(1 − 1) + 0(1 − 1) + 0(1 − 0) + 0
=
−14 − 2(0)
=
−14
g2 (x)
=
4 X
4
X
min(qij , 0) − 2 min(q12 , 0)(1 − x1 x2 ) + min(q13 , 0)(1 − x1 x3 )
i=1 j=1
+ min(q14 , 0)(1 − x1 x4 ) + min(q23 , 0)(1 − x2 x3 ) + min(q24 , 0)(1 − x2 x4 )
+ min(q34 , 0)(1 − x3 x4 ) + min(q11 , 0)(1 − x1 ) + min(q22 , 0)(1 − x2 )
X
4
4 X
max(qij , 0)xi xj
+ min(q33 , 0)(1 − x3 ) + min(q44 , 0)(1 − x4 ) +
i=1 j=1
= −14 − 2 0(1 − 0 × 1) + 0(1 − 0 × 1) + 0(1 − 0 × 0) + 0(1 − 1 × 1)
+(−7)(1 − 1 × 0) + 0(1 − 1 × 0) + 0(1 − 0) + 0(1 − 1) + 0(1 − 1) + 0(1 − 0) + 0
= −14 − 2(−7)
= −14 + 14
=
0
Note que o valor de g2 (x) ≥ g1 (x) e g2 (x) = f (x).
A Proposição 5.2 relaciona as Fórmulas (5.4) e (5.5).
Proposição 5.2. Suponha f (x) = xT Qx, x ∈ {0, 1}n e Q ∈ Qn×n uma matriz simétrica.
As expressões nas Fórmulas (5.4) e (5.5) satisfazem g1 (x) ≤ g2 (x), onde xp1 , xp2 , . . . , xplev
têm seus valores fixados em 0/1 e xplev+1 , xplev+2 , . . . , xpn não têm seus valores fixados.
Prova:
Utilizamos o seguinte fato na demonstração:
max{1 − xpi } ≤ min{1 − xpi xpj }.
O max{1 − xpi } = 1 ocorre quando xpi = 0, neste caso min{1 − xpi xpj } = 1. O min{1 −
xpi xpj } = 0 ocorre quando xpi = xpj = 1, neste caso max{1 − xpi } = 0. Assim, max{1 −
xpi } ≤ min{1 − xpi xpj } com xpi , xpj ∈ {0, 1}.
n X
n
X
g1 (x) =
qij−
lev X
n
lev
X
X
−
− 2
i=1 j=1
+
lev X
lev
X
76
i=1 j=i+1
i=1
qp+i pj xpi xpj
i=1 j=1
n X
n
X
=
+
qij− −
2
lev X
lev
X
i=1 j=1
i=1
lev
X
!
+
i=1
+
qij− −
2
j=lev+1
lev X
lev
X
lev X
lev
X
i=1 j=1
i=1
lev
X
!
i=1
j=i+1
n
X
qp+i pj xpi xpj
i=1 j=1
n X
n
X
≤
qp−i pj (1 − xpi ) +
+
qp−i pj (1 − xpi xpj ) +
j=i+1
lev X
lev
X
n
X
j=lev+1
qp+i pj xpi xpj
i=1 j=1
= g2 (x)
Resolvemos a instância bqp50.6 (sexta instância no arquivo de instâncias com 50 variáveis, ver Seção 6.2.1) utilizando o método Branch and Bound e calculamos os limitantes
com as funções g1 (x) e g2 (x). A Figura 5.2 mostra os valores dos limitantes ao longo de
várias iterações do B&B. Note que g2 (x) sempre forneceu valores maiores ou iguais aos
obtidos por g1 (x).
No texto a seguir, apresentamos como efetuar de maneira rápida o cálculo do limitante
inferior à f (x) para o UQP.
Recálculo do Limitante Inferior à f (x) com Acréscimo de um Nı́vel na Árvore
de Enumeração
O cálculo do limitante inferior à f (x) na sua forma básica tem complexidade computacional O(n2 ). Utilizando o Algoritmo 3.9.1, sempre que se desce na árvore de enumeração do
Branch and Bound aumentando-se o nı́vel em uma unidade, é possı́vel realizar o cálculo
do limitante inferior à f (x) com complexidade O(n).
Proposição 5.3. Sejam f (x) o valor de xT Qx para um dado x ∈ {0, 1}n e Q ∈ Qn×n uma
matriz simétrica. Suponha que lev ∈ {1, 2, . . . , n} é o número de variáveis fixadas em 0 ou
1, em um vértice da árvore de enumeração do Branch and Bound e g2 Anterior é o valor
do limitante inferior à f (x) neste vértice, calculado pela Fórmula (5.5), no nı́vel lev − 1.
77
0
Valores dos limitantes inferiores
-1000
g1
g2
-2000
-3000
-4000
-5000
-6000
-7000
1
16
31
46
61
76
91
106
121
136
151
166
181
196
211
226
241
Número de Iterações no método Branch and Bound
Figura 5.2: Comparação entre os valores de g1 (x) e g2 (x) ao longo da execução do Branch
and Bound para a instância bqp50.6
Então pode-se recalcular o valor do limitante, para o nı́vel lev, da seguinte maneira:
g2 (x) = g2 Anterior + D,
onde D é:
D = (xplev
lev−1
n
X
X
−
−
−
qplev pj + qplev plev
− 1) 2
qpi plev xpi +
i=1
+xplev
lev−1
X
qp+i plev xpi
i=1
j=lev+1
+
lev
X
qp+lev pj xpj
(5.6)
j=1
Assim o recálculo é realizado em tempo O(n).
Prova:
Obtemos uma pxpressão para D realizando uma subtração entre os valores de
g2 (x) calculados nos nı́veis lev e lev − 1. A prova é como segue:
(
D =
n X
n
X
X
lev X
lev
n
X
−
− 2
qpi pj (1 − xpi xpj ) +
qij−
i=1 j=1
i=1
j=i+1
j=lev+1
)
X
lev
lev X
lev
X
+
qp−i pi (1 − xpi ) +
qp+i pj xpi xpj
i=1
(
−
i=1 j=1
n X
n
X
lev−1
n
X lev−1
X
X
−
−
qij − 2
qpi pj (1 − xpi xpj ) +
i=1 j=1
+
i=1
j=i+1
j=lev
lev−1
X
)
lev−1
X lev−1
X
−
+
qpi pi (1 − xpi ) +
qpi pj xpi xpj
i=1
i=1
= −2
lev X
lev
X
j=1
qp−i pj (1 − xpi xpj ) − 2
lev
n
X
X
i=1 j=i+1
+
lev X
lev
X
qp−i pj (1 − xpi ) −
lev
X
i=1 j=lev+1
i=1
qp+i pj xpi xpj
i=1 j=1
+2
lev−1
X lev−1
X
qp−i pj (1 − xpi xpj ) + 2
lev−1
X
−
lev−1
X
i=1
i=1 j=lev
i=1 j=i+1
lev X
lev
X
n
X
qp+i pj xpi xpj
i=1 j=1
=
h
−2
lev X
lev
X
qp−i pj (1
− xp i xp j ) + 2
−2
lev
n
X
X
qp−i pj (1
− xp i ) + 2
lev−1
X
i=1 j=lev+1
h
h
−
+
lev
X
qp−i pi (1
i=1
lev X
lev
X
i=1 j=1
qp−i pj (1
− xp i ) +
n
X
i
i=1 j=lev
lev−1
X
qp+i pj xpi xpj −
qp−i pi (1
i=1
lev−1
X lev−1
X
i=1
i
− xpi ) +
qp+i pj xpi xpj
i
j=1
Agora expandimos as quatro parcelas da fórmula acima:
• Parcela 1:
i
− xp i xp j ) +
i=1 j=i+1
i=1 j=i+1
h
lev−1
X lev−1
X
78
−2
= −2
=
qp−i pj (1 − xpi xpj ) + 2
i=1 j=i+1
lev−1
P lev−1
P
i=1 j=i+1
lev−1
P lev−1
P
qp−i pj (1 − xpi xpj ) −
lev−1
P lev−1
P
qp−i pj (1 − xpi xpj )
i=1 j=i+1
lev−1
P −
2
qpi plev (1
i=1
− xpi xp lev)
qp−i pj (1 − xpi xpj )
i=1 j=i+1
lev−1
P −
qpi plev (1 − xpi xp lev)
−2
i=1
lev−1
P −
2
qpi plev (xpi xp lev − 1)
i=1
+2
=
lev P
lev
P
79
lev
P
Observação: Se i = lev então j = i + 1 > lev, assim
j=lev+1
qp−lev pj (1 − xplev xpj ) não se
aplica.
• Parcela 2:
lev
P
−2
n
P
i=1 j=lev+1
lev−1
n
P P
qp−i pj (1 − xpi ) + 2
n
P
i=1 j=lev
n
P
qp−lev pj (1 − xplev )
j=lev+1
lev−1
P −
qpi plev (1 − xpi )
+2
qp−i pj (1 − xpi ) + 2
i=1
i=1 j=lev+1
lev−1
n
P −
P
qpi plev (1 − xpi )
−2
qp−lev pj (1 − xplev ) + 2
i=1
j=lev+1
= −2
i=1 j=lev+1
lev−1
n
P P
=
lev−1
P
qp−i pj (1 − xpi ) − 2
• Parcela 3:
lev−1
lev
P −
P
qpi pi (1 − xpi )
− qp−i pi (1 − xpi ) +
i=1
= −qp−lev plev (1 − xplev ) −
i=1
lev−1
P
i=1
qp−i pi (1 − xpi ) +
lev−1
P
i=1
= −qp−lev plev (1 − xplev )
• Parcela 4:
lev P
lev
P
=
=
qp+i pj xpi xpj −
i=1 j=1
lev−1
P lev−1
P
lev−1
P lev−1
P
i=1 j=1
lev−1
P
qp+i pj xpi xpj +
qp+i pj xpi xpj
qp+i plev xpi xplev
i=1 j=1
i=1
lev
lev−1
lev−1
P
P
P +
+
qp+lev pj xplev pj −
q p i p j xp i xp j
j=1
i=1 j=1
lev−1
lev
P +
P
qpi plev xpi xplev +
qp+lev pj xplev pj
i=1
j=1
Ao por juntas as quatro expressões obtidas com o desenvolvimento das parcelas acima,
80
obtemos:
= 2
lev−1
X
qp−i plev (xpi xplev
n
X
− 1) − 2
i=1
qp−lev pj (1
lev−1
X
qp+i plev xpi xplev +
i=1
lev−1
X
i=1
n
X
lev−1
X
qp−i plev (xpi xplev
− xp i ) − 2
qp−i plev (1 − xpi )
i=1
qp+i plev xpi +
lev
X
qp+lev pj xpj
j=1
n
X
qp−lev pj (1 − xplev ) − qp−lev plev (1 − xplev )
j=lev+1
+xplev
lev−1
X
qp+i plev xpi
+
i=1
lev−1
X
lev
X
qp+lev pj xpj
j=1
qp−i plev xpi (xplev
− 1) + 2
i=1
n
X
qp−lev pj (xplev − 1) + qp−lev plev (xplev − 1)
j=lev+1
+xplev
lev−1
X
qp+i plev xpi
+
i=1
= (xplev
lev−1
X
j=lev+1
lev−1
X
i=1
= 2
qp+lev pj xplev pj
qp−lev pj (1 − xplev ) + 2
i=1
= 2
lev
X
j=1
qp−i plev (xpi xplev − 1) − 2
−qp−lev plev (1 − xplev ) + xplev
qp−i plev (1 − xpi )
i=1
j=lev+1
−qp−lev plev (1 − xplev ) +
= 2
− xplev ) + 2
lev−1
X
lev
X
qp+lev pj xpj
j=1
lev−1
n
X
X
−
−
−
− 1) 2
qpi plev xpi +
qplev pj + qplev plev
i=1
+xplev
lev−1
X
i=1
j=lev+1
qp+i plev xpi
+
lev
X
qp+lev pj xpj
j=1
A fórmula final poderia ser mais reduzida, mas este formato é útil para implementação
do algoritmo. Note que se xplev = 0 somente a primeira parcela é utilizada para efetuar o
cálculo, caso contrário somente a segunda parcela é utilizada.
Exemplo 5.6. Se f (x) = xT Qx, x = [0, 1, 0, 1], p = [1, 2, 3, 4], n = 4, lev = 3, g2 Anterior = −105 e



Q=



−40 −2
37 −41

−2 −40 −11
40 

37 −11 −42
20 

−41
40
20 −1
81
Então g2 (x):
g2 (x)
lev−1
X
= g2 Anterior + (xplev − 1) 2
qp−i plev xpi +
i=1
+xplev
lev−1
X
qp+i plev xpi +
i=1
lev
X
qp+lev pj xpj
n
X
qp−lev pj + qp−lev plev
j=lev+1
j=1
−
−
−
−
= g2 Anterior + (xp3 − 1) 2 qp1 p3 xp1 + qp2 p3 xp2 + qp3 p4 + qp3 p3
+
+
+
+
+
xp3 qp1 p3 xp1 + qp2 p3 xp2 + qp3 p1 xp1 + qp3 p2 xp2 + qp3 p3 xp3
= −105 + (0 − 1) 2 0 × 0 + (−11) × 1 + 0 + (−42)
h
i
= −105 − − 22 − 42
= −105 + 64
= −41
5.1.5
Resumo dos Métodos de Cálculo e Recálculo do Valor da
Função Objetivo e do Limitante Inferior à f (x)
A Tabela 5.1 apresenta um resumo das quantidades de operações de multiplicação e adição para o recálculo do valor da função objetivo, tanto para matrizes assimétricas quanto
para simétricas. A Tabela 5.2 apresenta um resumo das quantidades de operações de
multiplicação e adição para o recálculo do limitante inferior à f (x) no B&B para matrizes
assimétricas. A coluna Método mostra o nome do método de recálculo, Matriz Assimétrica
e Matriz Simétrica mostram os números de operações para matrizes assimétricas e simétricas respectivamente, Mult. e Adições exibem os números de multiplicações e adições
necessárias para cada método.
Método de Cálculo
Matriz Assimétrica
Mult.
Adições
2
n +n
n2 − 1
Matriz Simétrica
Mult. Adições
n2 + n n2 − 1
Recálculo com mudança no valor
de Uma variável
n+1
2n
n+1
n+1
Recálculo com mudança no valor
de Duas variável
2n + 1
4n + 2
2n + 1
2n + 5
Cálculo na forma básica
Tabela 5.1: Resumo do número de operações nos recálculos do valor da função objetivo.
Método de Cálculo
Cálculo do limitante
Recálculo do limitante com
acréscimo de um nı́vel
82
Matriz Assimétrica
Multiplicações.
Adições
2
2
2lev + nlev + 1 n + lev(2n + 1) − 1 − ~(n, lev)
3lev + 1
2lev + n + 3
Tabela 5.2: Resumo do número de operações nos recálculos do valor do limitante inferior
à f (x) no B&B. Assumimos ~(n, lev) = 1 se n − lev 6= 0 e 0 caso contrário.
5.2
Implementações Paralelas
Nesta seção abordamos os algoritmos que foram paralelizados nesta dissertação e suas implementações em CUDA. O método Tabu Search que foi apresentado na forma sequencial
na Seção 3.8.1, tem sua forma paralela descrita na Seção 5.2.1. Os resultados computacionais comparando as implementações sequencial e a paralela são apresentados nas Seções
6.3.2 e 6.3.3. O método exato Branch and Bound (B&B) que foi apresentado na sua forma
sequencial na Seção 3.9.2, foi implementado de forma paralela, e é apresentado na Seção
5.2.2. Os resultados computacionais do B&B, comparando as implementações sequencial
e a paralela são mostrados na Seção 6.4.2.
5.2.1
Tabu Search na Forma Paralela
A implementação do Tabu Search (TS) sequencial apresentou excelentes resultados, como
descrito nos experimentos computacionais na Seção 6.3.1. Devido a estes resultados,
desenvolvemos uma versão paralela para este método.
O método TS tem uma dependência de dados a cada iteração, pois a variável fixada
na iteração anterior, que é a que forneceu melhor incremento no valor da função objetivo,
deve ter seu valor preservado na próxima iteração. Ao realizar este procedimento, em paralelo, faz-se necessário realizar um sincronismo entre todas as threads, o que em CUDA
significa encerrar o kernel. Por este motivo não paralelizamos todo o método. Identificamos as partes que possivelmente requerem muito esforço computacional, para avaliar a
possibilidade de paralelizá-las. As partes identificadas foram o cálculo do valor da função
objetivo e a busca local.
Como a busca local implementada tem uma grande dependência de dados e pouco
custo computacional em cada iteração, provavelmente sua paralelização não traria ganho
em termos de speedup. Assim, a parte do código paralelizada foi o cálculo do valor da
função objetivo.
O método Tabu Search é explicado em detalhes na Seção 3.8.1, aqui abordamos os
aspectos da versão paralela com GPUs. Explicamos o Algoritmo 5.2.1 a seguir.
83
Na linha 5, aloca-se espaços de memória na GPU para armazenar o vetor solução x,
a lista tabu L, o vetor que armazena o valor da melhor solução de cada bloco V kernel e
o vetor V kernelIndice que guarda os ı́ndices das variáveis xi que ao alterá-las forneceu
a melhor solução para cada bloco. Na linha 7, é feita a cópia dos vetores x e L da CPU
para a GPU. Na linha 8, é feita a chamada do kernel onde calcula-se o valor da função
objetivo em paralelo. Na linha 9, é feita a cópia dos vetores V kernel e V kernelIndice da
GPU para a CPU. Em seguida, percorre-se o vetor V kernel para encontrar o ı́ndice da
variável que fornece o maior valor para a função objetivo e armazena-o na variável k.
Algoritmo 5.2.1: Pseudo-código do método Tabu Search paralelo com GPUs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Entrada: n ∈ N∗ , Q ∈ Qn×n , Solução Inicial ∈ {0, 1}n
Saı́da: x∗ ∈ {0, 1}n
inı́cio
x ← Solução Inicial
x∗ ← x, V ← f (x)
Li ← 0 para i = 1, 2, . . . , n
Cria espaços de memória na GPU para os vetores x, L, V kernel e V kernelIndice
Copia os vetores x e L da CPU para a GPU
Calcula F O Kernel(Q, x, L, V kernel, V kernelIndice, n) %Chamada do kernel
Copia os vetores V kernel e V kernelIndice da GPU para a CPU
V ← V kernel1 ; t ← V kernelIndice1
para i = 2 até Blocos faça
se V kerneli > V então
V ← V kerneli , t ← V kernelIndicei
fim
fim
xt ← 1 − xt
para i = 1 até n e Li > 0 faça
Li ← Li − 1
fim
se f (x) > f (x∗ ) então
x∗ ← busca local(n, Q, x);
Lt ← K
fim
fim
fim
O Algoritmo 5.2.2 apresenta o pseudo-código do kernel. Na linha 4, é utilizada a lista
tabu para selecionar as variáveis que não podem sofrer alterações. Na linha 5, é feito o
recálculo do valor da função objetivo, levando em consideração uma possı́vel alteração
na i-ésima variável, na forma xi = 1 − xi . Na linha 10, é feita uma chamada à função
ReductionM ax(), que é apresentada no Algoritmo 5.2.3. O objetivo desta função é encontrar o maior valor do vetor V , seu ı́ndice correspondente em V indice e copiá-los para os
vetores V kernel e V kernelIndice, na posição correspondente ao bloco atual. Desta maneira, no término, os vetores V kernel e V kernelIndice armazenaram os maiores valores
das soluções e os ı́ndices correspondentes às variáveis que foram alteradas.
Na próxima seção apresentamos trechos dos códigos da implementação do método
Algoritmo 5.2.2: Pseudo-código do Kernel do Tabu Search
1
2
3
4
5
Entrada: n ∈ N∗ , Q ∈ Qn×n , x ∈ {0, 1}n , L ∈ Qn , V kernel ∈ QBlocos , V kernelIndice ∈ QBlocos ,
f (x) ∈ Q
inı́cio
para i = 1 até n EM PARALELO faça
Vi ← −∞;
se Li > 0 então
n
P
Vi ← f (x) + (1 − 2xi ) qii + (qij + qji )xj
j=1
j6=i
V Indicei ← i
6
fim
7
fim
Sincroniza as threads
ReductionM ax(V, V Indice, V kernel, V kernelIndice)
8
9
10
11
fim
Algoritmo 5.2.3: Pseudo-código do ReductionMax no Kernel do Tabu Search
1
2
3
4
5
6
7
8
9
10
11
Entrada: V ∈ Qn , V Indice ∈ Qn , V kernel ∈ QBlocos , V kernelIndice ∈ QBlocos ,
Número do Bloco ∈ N, Tamanho do bloco ∈ N
inı́cio
b ← Número do Bloco
V kernelb ← V1
V KernelIndiceb ← 1
para i = 2 até Tamanho do bloco faça
se Vi > V kernelb então
V kernelb ← Vi
V kernelIndiceb ← i
fim
fim
fim
84
85
Tabu Search paralelizado com GPUs.
Códigos da Implementação do Tabu Search em Paralelo
Nesta seção descrevemos em detalhes, aspectos da implementação e otimizações em CUDA
do método Tabu Search paralelizado com GPUs. Apresentamos trechos dos códigos implementados em Linguagem C / CUDA e em seguida discutimos o código.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
...
//Copia dados da CPU para a GPU
cudaMemcpy(d_X, X, nVars * sizeof(int), cudaMemcpyHostToDevice);
cudaMemcpy(d_L, L, nVars * sizeof(int), cudaMemcpyHostToDevice);
TSKernel<<<Blocos, ThreadsPerBlocks, size>>>(d_Q, d_X, d_L, d_VKernel, d_VKernelIndex,
ValSol, nVars);
//Copia dados da GPU para a CPU
cudaMemcpy(VKernel, d_VKernel, Blocos * sizeof(int), cudaMemcpyDeviceToHost);
cudaMemcpy(VKernelIndice, d_VKernelIndice, Blocos * sizeof(int),
cudaMemcpyDeviceToHost);
V=VKernel[0]; k=VKernelIndice[0];
for(i=1;i<Blocos;i++){
if(V < VKernel[i]){
V = VKernel[i];
k = VKernelIndice[i];
}
}
...
Código 5.1: Cópias de Dados e Chamada do Kernel no Tabu Search
O Código 5.1 apresenta parte do programa que é executado na CPU. Neste trecho
apresentamos como é feita a cópia dos vetores X e L da CPU para a GPU. Em seguida é
feita a chamada do kernel, onde é realizado o cálculo do valor da função objetivo. Depois
é feita a cópia dos vetores VKernel e VKernelIndex da GPU para a CPU. Em VKernel
é armazenado o valor da melhor solução encontrada em cada bloco e em VKernelIndex
o ı́ndice da variável X[i], que ao alterá-la gerou a solução cujo valor foi armazenado em
VKernel.
__global__ void TSKernel(int *Q, int *X, int *L, int *VKernel, int *VKernelIndice,
int ValSol, int nVars){
3
extern __shared__ int Xs[];
4
__shared__ int V[BLOCKSIZE];
5
__shared__ int VIndice[BLOCKSIZE];
6
int tid = (blockIdx.x * blockDim.x) + threadIdx.x;
7
int nThread = threadIdx.x;
8
int i, mult;
1
2
V[threadIdx.x] = -INT_MAX;
9
//Copia o vetor X para memória compartilhada
while (nThread < nVars){
Xs[nThread] = X[nThread];
nThread += BLOCKSIZE;
}
10
11
12
13
14
if((tid < nVars) && (L[tid]==0)){
mul = Xs[tid]==0 ? 1 : -1;
15
16
for(i=0;i<nVars;i++)
ValSol += 2 * Q[i*nVars + tid] * Xs[i] * mult;
ValSol += Q[tid*nVars + tid];
17
18
19
V[threadIdx.x] = ValSol;
VIndice[threadIdx.x] = tid;
20
21
}
__syncthreads();
//Faz uma reduç~
ao no bloco encontrando o maior valor de Vtmp
ReductionMax(VKernel, VKernelIndice, V, VIndice);
22
23
24
25
26
86
}
Código 5.2: Kernel do Tabu Search
O Código 5.2 mostra como é feito o cálculo do valor da função objetivo dentro do kernel.
Como o vetor X é acessado várias vezes por todas as threads com tid < nVars, fazemos
uma cópia de seus dados para o vetor Xs, que está alocado na memória compartilhada,
cujo acesso é mais rápido (ver Seção 4.6). Como o vetor X pode ter tamanhos variáveis
dependendo da instância, criamos o vetor na memória compartilhada passando o seu
tamanho por parâmetro na chamada do kernel. Isto é feito fornecendo o parâmetro size
na chamada do kernel e com o parâmetro extern ao criar a variável Xs dentro do kernel.
Na linha 5 do kernel (Algoritmo 5.2.2), vemos que na fórmula de recálculo do valor da
função objetivo devemos multiplicar a i-ésima linha da matriz Q pelo vetor x. Ao fazer
este cálculo cada thread acessa posições distantes na área de memória global, que é onde
encontra-se a matriz Q. A Figura 5.3(a) ilustra este acesso. Como as matrizes Q das
instâncias utilizadas são simétricas, tem-se que Qi x = xT Qi , onde Qi e Qi são respectivamente a i-ésima linha e a i-ésima coluna da matriz Q. Desta forma multiplicamos o vetor
x pela i-ésima coluna da matriz Q. Assim, é feito um acesso combinado à memória global
ao efetuar o recálculo, como ilustra a Figura 5.3(b).
Antes de se fazer o recálculo do valor da função foi feita uma tentativa de se copiar
a matriz Q para a memória compartilhada, mas tal tentativa não surtiu melhorias no
desempenho do programa, já que o acesso à matriz já é feito de forma combinada. É
interessante utilizar a memória compartilhada para armazenar a matriz Q, quando as
instâncias forem assimétricas, ou se for feito o cálculo do valor da função objetivo na
forma básica.
87
Ao final é feita a chamada à função ReductionMax(), que encontra os maiores valores no vetor V, seu correspondente ı́ndice em VIndice e armazena-os em VKernel e
VKernelIndice.
Th0
Th1
Th0 Th1 Th2 Th3
Th2
Th3
(a)Sem acesso combinado
(b)Com acesso combinado
Figura 5.3: Acesso a i-ésima linha e coluna da matriz Q
__device__ void ReductionMax(int *VKernel, int *VKernelIndice, int *V, int *VIndice){
int qtd = blockDim.x/2;
3
while(qtd > 0){
4
if(threadIdx.x < qtd){
5
if(V[threadIdx.x] < V[threadIdx.x + qtd]){
6
V[threadIdx.x] = V[threadIdx.x + qtd];
7
VIndice[threadIdx.x] = VIndice[threadIdx.x + qtd];
8
}
9
__syncthreads();
10
}
11
qtd /= 2;
12
}
13
if(threadIdx.x == 0){
14
VKernel[blockIdx.x] = V[0];
15
VKernelIndice[blockIdx.x] = VIndice[0];
16
}
17 }
1
2
Código 5.3: Função ReductionMax()
O Código 5.3 encontra o maior valor de V, seu correspondente ı́ndice em VIndice e o
armazena nos vetores VKernel e VKernelIndice na posição correspondente ao seu bloco.
Ou seja, o valor de V referente ao k-ésimo bloco é armazenado em VKernel[k]. O código
ReductionMax foi baseado no código ReductionSum apresentado em [41] na Página 79.
Esta maneira de implementar a redução conta com algumas otimizações, tais como: Faz
acesso combinado a memória global e evita conflito de bancos de memória.
A Figura 5.4 mostra um exemplo da operação de redução feita pelo Código 5.3.
5.2.2
Branch and Bound na Forma Paralela
A referência [49] descreve uma implementação paralela do B&B, utilizando um modelo
mestre-escravo. Nossa implementação paralela utiliza um modelo fork-join.
3
<
1
<
3
7
<
2
0
4
8
4
<
8
4
0
4
8
4
4
8
4
0
4
8
4
4
8
4
0
4
8
4
4
88
<
<
8
<
8
Figura 5.4: Exemplo de operação de redução
Uma solução inicial é gerada pelo método Gradient Midpoint Method (Algoritmo 3.8.4),
que é melhorada pelo método Tabu Search (Algoritmo 3.8.1) e então fornecida como
entrada para o método B&B, apresentado no Algoritmo 5.2.4, através do vetor x∗ e tem
OP T = f (x∗ ). Denotamos por qij− = min{qij , 0} e qij+ = max{qij , 0}. As seguintes
variáveis e constantes são usadas na descrição do Algoritmo 5.2.4.
qij
n
OP T
gOP T0
gOP T1
x∗
levIni
lev
p1 , . . . , plev
plev+1 , . . . , pn
xp1 , xp2 , . . . , xplev
g2
lb
ub
p
N SU BP
T id
Coeficientes na linha i e coluna j na matriz Q;
Número de variáveis de uma instância;
Valor da melhor solução encontrada;
Valor da melhor solução encontrada até o momento;
Posição na memória que contém a melhor solução até o momento;
Melhor solução encontrada até o momento;
Nı́vel inicial na busca da árvore de enumeração do B&B;
Nı́vel atual na árvore de enumeração do B&B;
Índices das variáveis fixadas no subproblema atual;
Índices das variáveis livres no subproblema atual;
Variáveis fixadas;
Limitante inferior à f (x);
Limitante inferior à ∇f (x) ∈ [0, 1]n ;
Limitante superior à ∇f (x) ∈ [0, 1]n ;
Vetor de permutações;
Número de subproblemas resolvidos;
Identificador da thread.
Os valores de gOP T0 e gOP T1 são compartilhados entre todas as threads do kernel.
89
O Algoritmo 5.2.4 inicia fazendo alocações de áreas para dados na GPU e copiando os
dados dos vetores x, x∗ , p, lb, ub, gOP T e da matriz Q da CPU para a GPU. Em seguida,
na Linha 3, é feito um laço com a informação “para cada thread EM PARALELO”, que
significa que cada thread executará uma única vez o conteúdo deste laço. Na Linha 4, um
identificador da thread é atribuı́do a variável nT id.
Cada thread resolverá um subproblema do problema principal. O número de threads
em execução, será sempre um número que é potência de 2. A decomposição dos subproblemas é feita fornecendo um trecho inicial fixo e diferente, de levIni posições, no vetor
x. Desta forma cada thread examinará uma parte da árvore de enumeração. O código
entre as Linhas 5 e 10 preenche as primeiras levIni posições do vetor x, convertendo o
identificador da thread, nT id, em sua representação binária. As demais posições do vetor
são preenchidas com zeros. Na Linha 7, nT id mod 2 representa o resto da divisão de nT id
por 2.
A Linha 12, inicializa-se os limitantes de ∇f (x), lb e ub. Na Linha 13, atualiza estes
limitantes levando em consideração as primeiras levIni posições fixadas do vetor x, da
seguinte maneira:
para i = 1, . . . , lev
lbpj ← lbpj +2 xpi qp+i pj − (1 − xpi )qp−i pj
para i = 1, . . . , lev
ubpj ← ubpj +2 xpi qp−i pj − (1 − xpi )qp+i pj
j = lev + 1, . . . , n
j = lev + 1, . . . , n
O vetor de permutações p é inicializado na Linha 14 e as variáveis lev, N SU BP e gOP T0
são inicializadas na Linha 15.
Uma pilha, estrutura de dados, é utilizada para armazenar informações de subproblemas quando um branching (ramificação da árvore) é necessário. Na Linha 16, a pilha é
inicializada com o valor −1 para a variável lev, que indica que a pilha está vazia. A thread
termina seu trabalho quando este valor é desempilhado. O cálculo do limitante inferior à
f (x) na Linha 18, é feito conforme a Fórmula (5.5).
O restante do código, nas Linhas 17 a 50, faz o mesmo que o método B&B sequencial
descrito no Algoritmo 3.9.1, com algumas pequenas alterações de implementação, mas
não de funcionalidade, que discutiremos a seguir:
• Na Linha 22 o identificador da thread que encontrou a melhor solução é armazenado
na variável gOP T1 .
• Nas Linhas 29 e 30, atualiza-se os valores dos vetores lb e ub. Estas linhas efetuam
o mesmo cálculo que o apresentado no Algoritmo sequencial, porém eliminou-se o
condicional (se), que em CUDA atrapalha o fluxo do programa.
As Linhas 51 e 52 copiam os dados dos vetores gOP T e x∗ da GPU para a CPU.
90
Algoritmo 5.2.4: Pseudo-código do método Branch and Bound em paralelo com
GPUs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Entrada: n ∈ N∗ , Q ∈ Qn×n , x∗ ∈ Qn , OP T ∈ Q, levIni ∈ N, T id ∈ N
Saı́da: x∗ ∈ {0, 1}n , f (x∗ ) ∈ Q
Aloca área de memória na GPU para os vetores x, x∗ , p, lb, ub e gOP T
Aloca área de memória na GPU para a matriz Q e copia os dados da matriz da CPU para a GPU
para cada thread EM PARALELO faça
nT id ← Tid
se i ≤ levIni então
xi ← nT id mod 2, nT id ← nT id/2
senão
xi ← 0
fim
fim
P −
P +
lbi ← 2
qij + qii , ubi ← 2
qij + qii para i = 1, . . . , n
j=1
j=1
j6=i
j6=i
Atualiza limitantes lbi e ubi para i = 1, 2, . . . , n
pi ← i para i = 1, 2, . . . , n
lev ← levIni, N SU BP ← 0, gOP T0 ← OP T
empilha({-1,-,-,-},stack)
enquanto lev 6= −1 faça
g2 ← Calcula o limitante inferior g2
se g2 ≥ gOP T0 ou lev = n então
se g2 < gOP T0 então
gOP T0 ← g
gOP T1 ← Tid
x∗ ← x
fim
desempilha({lev, lb, ub, g},stack)
se lev 6= −1 então xplev ← 1 − xplev
senão
se lev 6= 0 então lbpi ← lbpi + 2 xplev qp+i plev − (1 − xplev )qp−i plev para i = lev + 1, . . . , n
ubpi ← ubpi + 2 xplev qp−i plev − (1 − xplev )qp+i plev para i = lev + 1, . . . , n
29
30
fim
entrou = falso
para i = lev até n faça
se lbpi ≥ 0 ou ubpi ≤ 0 então
se ubpi ≤ 0 então xpi ← 1
senão xpi ← 0
entrou = verdadeiro
Sai do loop
fim
fim
se entrou = falso então
i ← j onde δj = max{min(−lbpt , ubpt ) para t = lev + 1, . . . , n
31
32
33
34
35
36
37
38
39
40
41
42
t
xpi ← 0 ou 1 dependendo do valor que menos incrementa g
empilha({lev+1, lb, ub, g},stack)
43
44
fim
lev ← lev + 1
plev ↔ pi %Troca de valores de plev e pi
45
46
47
fim
48
49
50
51
52
fim
fim
Copia o vetor gOP T da GPU para a CPU
Copia o vetor x∗ iniciando na posição indicada por gOP T1 da GPU para a CPU
91
Códigos da Implementação do Branch and Bound em Paralelo
Nesta seção abordaremos com mais detalhes os aspectos da implementação e otimizações
em CUDA, do método Branch and Bound paralelizado com GPUs. Para isso, apresentamos trechos do código implementado em Linguagem C / CUDA e uma discussão sobre o
código.
O Código 5.4 apresenta parte do código sequencial que faz a alocação de espaço de
memória na GPU, a cópia dos dados da CPU para a GPU, a chamada do kernel e a cópia
dos dados da GPU para a CPU. Os Códigos 5.5 a 5.9 descrevem o kernel da aplicação. O
Código 5.10 apresenta a função que calcula os limitantes de ∇f (x), enquanto os Códigos
5.11 e 5.12 mostram as funções que calculam o limitante inferior g, conforme a Fórmula
(5.5).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
...
size_t
size_t
size_t
size_t
size_t
size_t
size
sizenVars
sizenSubProb
sizeSB
sizeP
sizePlim
=
=
=
=
=
=
92
Inst->nVars * sizeof(int);
Inst->nVars * sizeof(int);
nSubProb * sizeof(int);
nSubProb * Inst->nVars * sizeof(bool);
nSubProb * Inst->nVars * sizeof(Pilha);
nSubProb * Inst->nVars * Inst->nVars * sizeof(int);
//Aloca espaço no device
cudaMalloc((void **)d_gOPT, 2 * sizeof(int));
cudaMalloc((void **)d_x, sizeSB);
cudaMalloc((void **)d_xInc, sizeSB);
cudaMalloc((void **)d_pilha, sizeP);
cudaMalloc((void **)d_pilhaLB, sizePlim);
cudaMalloc((void **)d_pilhaUB, sizePlim);
cudaMallocPitch((void
**)d_Q, &Pitch, sizenVars, Inst->nVars);
**)d_p, &PitchSub, sizenSubProb, Inst->nVars);
**)d_lb, &PitchSub, sizenSubProb, Inst->nVars);
**)d_ub, &PitchSub, sizenSubProb, Inst->nVars);
//Copia dados para o device
cudaMemcpy2D(*d_Q, Pitch, Inst->getMatriz(), size, size, Inst->nVars,
cudaMemcpyHostToDevice);
//Espaço para a matriz Q e para os vetores ilb e iub
int sMem = Inst->nVars * Inst->nVars * sizeof(int) + 2 * Inst->nVars * sizeof(int);
BB_Kernel<<<Blocks,nThreadsPerBlock, sMem>>>(d_Q, Inst->nVars, d_x, d_xInc, d_p,
d_lb, d_ub, *OPT, d_gOPT, d_pilha, d_pilhaLB, d_pilhaUB, pitch / sizeof(int),
pitchsub/ sizeof(int), nSubProb, lev);
cudaMemcpy(gOPT, d_gOPT, 2 * sizeof(int), cudaMemcpyDeviceToHost);
cudaMemcpy(x, d_xInc + gOPT[1] * Inst->nVars, Inst->nVars * sizeof(bool),
cudaMemcpyDeviceToHost);
*OPT = gOPT[0];
...
Código 5.4: Cópias de Dados e Chamada do Kernel no Branch and Bound
O Código 5.4 apresenta parte do programa que é executado na CPU. Neste trecho
apresentamos como alocamos espaços de memória na GPU, com os comandos cudaMalloc
e cudaMallocPitch. Ambos os comandos reservam uma seção contı́gua de memória,
porém o comando cudaMallocPitch é destinado para matrizes. Ele cria um espaço vazio
entre cada linha da matriz, gerando um alinhamento dos dados na memória global, ou
seja, os dados de uma linha da matriz sempre começam em um endereço que é potência
de 2. Com isso pode-se aumentar a performance do programa ao acessar os dados desta
matriz, que inicialmente reside na memória global. O comando cudaMallocPitch retorna
um valor, pitch, que indica o tamanho da área de dados somado a área vazia. A Figura
5.5 mostra um esquema do armazenamento dos dados na memória.
As matrizes d_pilha, d_pilhaLB e d_pilhaUB são armazenadas em matrizes lineari-
93
Pitch
1ª Linha
n-ésima Linha
2ª Linha
Área de dados
Área vazia
Figura 5.5: Matriz Linearizada Alocada com o Comando cudaMallocPitch
zadas sem alinhamento de memória. Enquanto as matrizes d_Q, d_p, d_lb e d_ub são
armazenadas em matrizes linearizadas com alinhamento de memória.
A matriz Q é copiada da CPU para a GPU por meio do comando cudaMemcpy2D, que
faz a cópia de dados para uma área alocada pelo comando cudaMallocPitch. A variável
sMem guarda o valor do tamanho em bytes que será utilizado na memória compartilhada.
Em seguida é feita a chamada do kernel, onde é executado todo o código do B&B. Por
fim é feita a cópia dos vetores d_xInc e gOPT da GPU para a CPU.
É importante notar que cada coluna nas matrizes d_p, d_lb e d_ub representam os
vetores p, lb e ub, que cada thread utiliza individualmente. Os dados foram armazenados
desta forma para possibilitar o acesso combinado à memória global, embora para d_lb e
d_ub nem sempre isto seja possı́vel. Esta forma de armazenamento dos dados gerou um
bom ganho em termos de speedup. A matriz a seguir ilustra o esquema de armazenamento
da matriz d_p, onde n é o número de variáveis da instância, m é o número de subproblemas
nos quais o problema principal foi dividido. Este número é dado por 2levIni e pij representa
o j-ésimo elemento da i-ésima thread.

p11

 p12


d_p =  p13
 .
 ..

p1n
p21 p31
p22 p32
p23 p33
..
..
.
.
p2n p3n
...
...
...
..
.
...

pm1

pm2 

pm3 

.. 
. 

pmn
Portanto, para que a i-ésima thread acesse a j-ésima posição do vetor p, deve-se utilizar
o seguinte comando: p[j * pitch + i].
__global__ void BB_Kernel(int *d_Q, int nVars, bool *d_x, bool *d_xInc, int *p,
int *lb, int *ub, int OPT, int *gOPT, struct Pilha *d_pilha, int *d_pilhaLB,
3 int *d_pilhaUB, int pitch, int pitchsub, int nSubProb, int lev){
4
extern __shared__ int sharedMem[];
5
int *Q
= (int *)&sharedMem[0];
6
int *ilb = (int *)&sharedMem[nVars * nVars];
1
2
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
94
int *iub = (int *)&ilb[nVars];
__shared__ int sOPT;
int tid = blockDim.x * blockIdx.x + threadIdx.x;
int nThread = threadIdx.x;
if(threadIdx.x == 0) sOPT = OPT;
if(tid == 0) *gOPT = OPT;
//Copia a matriz Q para memória compartilhada
while (nThread < nVars * nVars){
int linha = nThread / nVars;
Q[nThread] = d_Q[linha * pitch + (nThread % nVars)];
nThread += blockDim.x;
}
__syncthreads();
//Calcula os limitantes de ∇f (x)
calculaBounds(Q, ilb, iub, nVars);
__syncthreads();
Código 5.5: Kernel do Branch and Bound Parte 1
O Código 5.5 apresenta o inı́cio do kernel. O vetor sharedMem é alocado na memória
compartilhada e armazenará os valores da matriz Q e dos vetores ilb iub. O vetor gOPT
contém duas posições, na primeira é armazenado o valor da melhor solução encontrada
até o momento e na segunda o identificador da thread que encontrou a solução. Este vetor
é armazenado na memória global. Note que gOPT[0] = *gOPT.
Como é necessário acessar o valor de gOPT[0] algumas vezes ao longo do programa, é
feita uma cópia deste valor para a variável sOPT, que reside na memória compartilhada.
Nas Linhas 14 a 18 é feita uma cópia da matriz Q para a memória compartilhada. Na
Linha 21 calcula-se os limitantes, superiores e inferiores, do gradiente da função f (x). O
código da função calculaBounds é mostrado no Código 5.10.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
if(tid < nSubProb){
bool *x
= (bool *)&d_x[tid * nVars];
bool *xInc = (bool *)&d_xInc[tid * nVars];
int i, maior, menor, aux, gAux, g=0, levIni = lev;
int plev, pi, Qaux, lbAux, ubAux, iAux; //Variáveis para otimizaç~
ao de performance
bool xAux, entrou; //Variáveis para otimizaç~
ao e controle
//Inicializa as variáveis para todas as threads (x, xInc, p, lb e ub)
int nTid = tid;
for(i = 0; i < nVars; i++){
if(i < lev){
xInc[lev - i - 1] = x[lev - i - 1] = nTid & 1;
nTid = nTid >> 1;
}else{
xInc[i] = x[i] = 0;
}
p[i * pitchsub + tid] = i; //Define os valores do vetor p
lb[i * pitchsub + tid] = ilb[i]; //Copia o vetor lb para todas as threads
ub[i * pitchsub + tid] = iub[i]; //Copia o vetor ub para todas as threads
17
18
19
}
20
//Ajusta os vetores lb e ub com as variáveis fixadas
for(i = 0; i < lev; i++){
xAux = x[i];
for(int j = lev; j < nVars; j++){
Qaux = Q[i * nVars + j];
lb[j * pitchsub + tid] += 2 * (xAux * positivo_cuda(Qaux)
- (1-xAux) * negativo_cuda(Qaux));
ub[j * pitchsub + tid] += 2 * (xAux * negativo_cuda(Qaux)
- (1-xAux) * positivo_cuda(Qaux));
}
}
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
95
//Ajusta os ponteiros da pilha
struct Pilha *pilha = &d_pilha[tid * nVars];
for(int i = 0; i < nVars; i++){
pilha[i].lb = &d_pilhaLB[tid * nVars * nVars + (i * nVars)];
pilha[i].ub = &d_pilhaUB[tid * nVars * nVars + (i * nVars)];
}
int nElemPilha = 0; //Número de elementos da pilha
//Empilha nó sentinela
pilha[nElemPilha].lev = -1;
pilha[nElemPilha].g = g;
Dentro do kernel foram utilizadas variáveis para otimização de performance, que nada
mais são do que variáveis auxiliares alocadas nos registradores. Quando um valor que
reside na memória global é utilizado mais de uma vez, armazenamos este valor em uma
variável auxiliar e a reutilizamos em seu lugar. No Código 5.6 vemos a declaração destas
variáveis auxiliares.
No Código 5.6, das Linhas 8 a 15 são definidos valores iniciais para o vetor x, que contém nas primeiras levIni posições uma representação binária do identificador da thread,
o que faz com que cada thread tenha um vetor x diferente, e assim trabalhem com um
subproblema diferente. Em seguida o vetor p é iniciado com pi = i para i = 0, 1, . . . , n − 1
e os valores dos vetores ilb e iub são copiados para os vetores lb e ub de todas as threads.
Como as primeiras levIni posições do vetor x foram fixadas, os limitantes lb e ub
são atualizados no trecho do código entre as Linhas 21 à 30. As funções negativo(a) e
positivo(a) equivalem, respectivamente, a max(a, 0) e min(a, 0). A pilha, estrutura de
dados, também é armazenada em uma matriz linearizada. A sua estrutura é dada como
segue: struct Pilha { int g, lev *lb, *ub; };
Das linhas 32 à 37 criam-se o ponteiro para as pilhas de cada thread e inicializam os
ponteiros dos vetores pilha[i].lb e pilha[i].ub para i = 0, 1, . . . , n − 1. Nas Linhas
39 e 40, empilha-se um nó sentinela. O trabalho de cada thread termina quando este nó
96
é desempilhado.
A Figura 5.6 apresenta um diagrama de como os dados da pilha são armazenados na
memória.
pilha[0].lb
pilha[1].lb
* *
* *
* *
pilha[n-1]
pilha[1]
pilha[0]
pilha[0].ub
pilha[n-1].lb
pilha[1].ub
pilha[n-1].ub
g lev *lb
* *ub
*
Célula da Pilha
Figura 5.6: Armazenamento da Pilha em Memória
1
2
3
while(lev != -1){
if(threadIdx.x == 0)
sOPT = *gOPT;
4
g = calculaG_cuda(Q, nVars, lev, x, p, pitchsub, tid);
5
if(g >= sOPT || lev == nVars){
if(g < sOPT){
atomicMin(&sOPT,g); //Atualiza a variável OPT da memória compartilhada
atomicMin(&gOPT[0],g); //Atualiza a variável gOPT da memória global
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
if(gOPT[0] == g)
atomicExch(&gOPT[1], tid);
for(i = 0; i < nVars; i++)
xInc[i] = x[i];
}
//Desempilha nó
lev = pilha[nElemPilha].lev;
g = pilha[nElemPilha].g;
lb[i * pitchsub + tid] = pilha[nElemPilha].lb[i];
ub[i * pitchsub + tid] = pilha[nElemPilha].ub[i];
}
nElemPilha--;
97
if(lev != -1){
plev = p[lev * pitchsub + tid];
xAux = x[plev] = 1 - x[plev];
lev++;
}
22
23
24
25
26
}
27
No Código 5.7, a primeira thread de cada bloco faz uma cópia do valor de *gOPT, que
está na memória global, para a variável sOPT que está na memória compartilhada. Na
Linha 4 é feito o cálculo do limitante inferior, que é apresentado no Código 5.11. Na Linha
5, se g >= sOPT, indica que o subproblema atual pode ser podado e se lev == nVars,
significa que o subproblema atual é um vértice folha da árvore de enumeração, então devese verificar se a solução encontrada é melhor que a melhor encontrada até o momento.
Caso lev == nVars e g < sOPT, os valores de sOPT e gOPT[0] são atualizados utilizando funções atômicas2 e a thread que teve seu valor gravado em gOPT[0] armazenará
em gOPT[1] o seu identificador.
Nas Linhas 11 à 13, cada thread copia os vetores x para o vetor que armazena a
melhor solução encontrada até o momento, xInc. Em seguida retira-se o nó do topo
da pilha e se não for o nó sentinela, altera-se o vetor x na posição lev, fazendo com
que x[lev] = 1 - x[lev]. O valor de x[lev] é armazenado na variável xAux, para ser
reusado sem ter que acessar o vetor x que reside na memória global. Note que plev
também é uma variável de otimização.
else{
entrou = false;
maior = -INT_MAX;
1
2
3
for(i = lev; i < nVars; i++){
pi = p[i * pitchsub + tid];
Qaux = Q[pi * nVars + p[(lev-1) * pitchsub + tid]];
lbAux = lb[pi * pitchsub + tid] + 2 * (xAux
* positivo_cuda(Qaux)
- (1-xAux) * negativo_cuda(Qaux));
ubAux = ub[pi * pitchsub + tid] + 2 * (xAux
* negativo_cuda(Qaux)
- (1-xAux) * positivo_cuda(Qaux));
4
5
6
7
8
9
10
if(lev != levIni){
lb[pi * pitchsub + tid] = lbAux;
ub[pi * pitchsub + tid] = ubAux;
}
11
12
13
14
//Verifica se é possı́vel determinar o valor para xpi
if(!entrou){
if(lbAux >= 0 || ubAux <= 0){
15
16
17
2
Uma função atômica junta operações de leitura e escrita de dados em uma única transação. Quando
duas ou mais threads tentam modificar dados de um mesmo endereço de memória, ela serializa estas
operações. Para maiores informações ver [42]
xAux = x[pi] = ubAux <= 0 ? 1 : 0;
iAux = i;
entrou = true;
goto PULA;
18
19
20
21
22
}
23
//Encontra a variável menos provável a ter seu valor determinado
menor = min(-lbAux, ubAux);
if(menor > maior){
maior = menor;
iAux = i;
}
PULA:;
24
25
26
27
28
29
}
30
31
98
}
O Código 5.8 é executado quando o nó, que está sendo explorado na árvore de enumeração, não pode ser podado e nem é um nó folha.
No Algoritmo 5.2.4, as Linhas 29, 30, 32 e 42 percorrem os vetores lb e ub das posições
plev até pn . No Código 5.8, fazemos essa varredura uma única vez no loop que encontra-se
entre as Linhas 4 e 31.
Nas Linhas de 7 à 14 atualiza-se os limitantes de ∇f (x). Das Linhas 16 à 22, é
verificado se é possı́vel determinar o valor de x[pi] e nas Linhas de 24 à 28 encontra-se
a variável que é menos provável ter seu valor determinado.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
i = iAux;
if(!entrou){
pi = p[i * pitchsub + tid];
x[pi] = 0;
gAux = calculaG_aux_cuda(Q, nVars, lev, x, p, i, pitchsub, tid);
xAux = x[pi] = 1;
g = calculaG_aux_cuda(Q, nVars, lev, x, p, i, pitchsub, tid);
if(gAux < g){
xAux = x[pi] = 0;
g = gAux;
}
//Empilha nó
nElemPilha++;
pilha[nElemPilha].lev = lev;
pilha[nElemPilha].g = g;
for(int k = 0; k < nVars; k++){
pilha[nElemPilha].lb[k] = lb[k * pitchsub + tid];
pilha[nElemPilha].ub[k] = ub[k * pitchsub + tid];
}
}
aux = p[lev * pitchsub + tid];
p[lev * pitchsub + tid] = p[i * pitchsub + tid];
p[i * pitchsub + tid] = aux;
lev++;
23
24
}
25
}
26
}
27
28
99
}
Se não foi possı́vel determinar o valor da variável x[pi] no Código 5.8, então no
Código 5.9, utiliza a informação da variável menos provável a ser determinada e verifica
qual é o valor em x[pi] que menos incrementa o limitante inferior da função objetivo. O
cálculo deste limitante, nesta situação, é feito através da função calculaG_aux_cuda, que
é apresentado no Código 5.12. Como não foi possı́vel determinar o valor de x[pi], este
nó da árvore de enumeração é armazenado na pilha, para ser investigado posteriormente.
Em seguida é feita a troca de valores no vetor de permutações, fixando a variável
x[pi] e incrementa-se em uma unidade a variável lev, que controla a altura da árvore de
enumeração.
__device__ void calculaBounds(int *Q, int *lb, int *ub, int nVars)
{
3
if(threadIdx.x < nVars){
4
lb[threadIdx.x] = ub[threadIdx.x] = 0;
5
for(int j = 0; j < nVars; j++){
6
lb[threadIdx.x] += 2 * negativo_cuda(Q[threadIdx.x * nVars + j]);
7
ub[threadIdx.x] += 2 * positivo_cuda(Q[threadIdx.x * nVars + j]);
8
}
1
2
lb[threadIdx.x] += (
ub[threadIdx.x] += (
-
9
10
11
12
*
*
*
*
nVars
nVars
nVars
nVars
+
+
+
+
threadIdx.x])
threadIdx.x]));
threadIdx.x])
threadIdx.x]));
}
13
14
positivo_cuda(Q[threadIdx.x
negativo_cuda(Q[threadIdx.x
negativo_cuda(Q[threadIdx.x
positivo_cuda(Q[threadIdx.x
}
Código 5.10: Função calculaBounds do Kernel no Branch and Bound
O Código 5.10 calcula os limitantes de ∇f (x) de forma paralela, conforme as equações
lbi = qii + 2
n
X
qij−
para i = 1, 2, . . . , n
qij+
para i = 1, 2, . . . , n
j=1
ubi = qii + 2
j6=i
n
X
j=1
j6=i
onde qij− = min{qij , 0} e qij+ = max{qij , 0}.
100
__host__ __device__ int calculaG_cuda(int *Q, int nVars, int lev, const bool *x,
int *p, int pitchsub, int tid){
3
int i, j, pi, pj, qAux, g = 0;
4
bool xpi, xpj, xpixpj;
5
int *__pi, *__pj, *__Q;
1
2
__pi = p+tid;
pi = *__pi; __pi += pitchsub;
xpi = x[pi];
6
7
8
9
if(i < lev)
g -= negativo_cuda(Q[pi * nVars + pi] * (1 - xpi)); //Terceira parte
10
11
__pj = p+tid;
__Q = &Q[pi * nVars];
for(j = 0; j < nVars; j++){
pj = *__pj; __pj += pitchsub;
xpj = x[pj];
qAux = *(__Q + pj);
xpixpj = xpi * xpj;
12
13
14
15
16
17
18
19
g += negativo_cuda(qAux); //Primeira parte
20
if((i < lev) && (j > i)){
if(j < lev)
g -= 2 * negativo_cuda(qAux * (1 - xpixpj)); //Segunda parte
else
g -= 2 * negativo_cuda(qAux * (1 - xpi)); //Segunda parte
}
if(j < lev)
g += positivo_cuda(qAux * xpixpj); //Quarta parte
21
22
23
24
25
26
27
}
}
return g;
28
29
30
31
}
Código 5.11: Função calculaG cuda do Kernel no Branch and Bound
O Código 5.11 efetua o cálculo do limitante inferior à função objetivo através da
seguinte fórmula:
n X
n
X
g2 =
qij− − 2
i=1 j=1
{z
|
i=1
}
+
|i=1
j=i+1
Segunda P arte
+
lev X
lev
X
j=lev+1
{z
!
n
X
qp−i pj (1 − xpi xpj ) +
|
P rimeira P arte
lev
X
lev X
lev
X
}
qp+i pj xpi xpj
i=1 j=1
{z
T erceira P arte
}
|
{z
Quarta P arte
}
A função calculaG_cuda foi modelada para reduzir o acesso às variáveis que residem
na memória global, utilizando as variáveis auxiliares pi, pj, qAux, xpi, xpj e xpixpj. Os
ponteiros *__pi, *__pj e *__Q auxiliam no acesso às matrizes, reduzindo operações de
101
multiplicação ao acessar os seus elementos.
__host__ __device__ int calculaG_aux_cuda(int *Q, int nVars, int lev, const bool *x,
int *p, int ind, int pitchsub, int tid)
3{
4
int plev, pind, ret;
1
2
8
plev = p[lev * pitchsub
pind = p[ind * pitchsub
p[lev * pitchsub + tid]
p[ind * pitchsub + tid]
9
ret = calculaG_cuda(Q, nVars, lev + 1, x, p, pitchsub, tid);
5
6
7
tid];
tid];
pind;
plev;
p[lev * pitchsub + tid] = plev;
p[ind * pitchsub + tid] = pind;
10
11
return ret;
12
13
+
+
=
=
}
Código 5.12: Função calculaG aux cuda do Kernel no Branch and Bound
Nas Linhas 5 e 7 do Código 5.9 é feita a chamada para a função calculaG_aux_cuda.
Nesse momento, o programa testa qual é o valor para x[pi] que menos incrementa o
valor de g. O cálculo do valor de g é feito pela função calculaG_cuda que é mostrado no
Código 5.11. Esta função presume que as primeiras lev posições dos vetores x e p estão
fixadas, mas não é o que acontece no momento do teste. Para isso é chamada uma função
auxiliar, calculaG_aux_cuda apresentada no Código 5.12, para preparar o vetor p para
o cálculo do limitante inferior. Logo após o cálculo, o vetor p é restaurado.
No Capı́tulo 6 mostramos os experimentos computacionais, que realizamos para analisar as implementações e os resultados teóricos que produzimos nesta dissertação.
Capı́tulo 6
Experimentos Computacionais
Neste capı́tulo apresentamos os resultados computacionais dos métodos que implementamos, para tentar resolver instâncias do UQP. Ao longo deste texto utilizamos a palavra
solver para representar programas comerciais que resolvem problemas. Implementamos
as metaheurı́sticas Tabu Search (TS) e Variable Neighborhood Search (VNS), uma versão
sequencial e outra paralela de um Branch and Bound (B&B) que aparece em [48] .
Este capı́tulo está dividido da seguinte forma. Na Seção 6.1 é apresentado o ambiente
dos experimentos. Na Seção 6.2 indicamos as instâncias utilizadas para testar os métodos.
Na Seção 6.3 apresentamos uma comparação entre as implementações dos métodos TS
e VNS. Na Seção 6.3.2 fazemos uma comparação entre as versões sequencial e paralela
da implementação do TS. Na Seção 6.3.3 fazemos uma comparação entre as versões do
TS sequencial e paralelo com o cálculo do valor da função objetivo na forma básica.
Na Seção 6.4.1 mostramos resultados obtidos utilizando o solver IBM ILOG CPLEX
v12.4. Na Seção 6.4.2 fazemos uma comparação entre as versões sequencial e paralela da
implementação do B&B.
Neste capı́tulo, em algumas tabelas utilizamos os sı́mbolos s, m, h e d para representar
segundos, minutos, horas e dias.
6.1
Ambiente dos Experimentos
Os experimentos computacionais foram todos executados em um computador com a seguinte configuração:
• Computador: Processador Intel Core i7 3930K, 6 Núcleos de 3.2 GHz, 32 GB de
Memória RAM;
• GPU: 2 placas NVIDIA EVGA GeForce GTX 680, 1006 MHz, 64 bits, 8 SMX
(Nova geração de multi-processadores), 1536 Núcleos 2 GB Memória Global;
102
CAPÍTULO 6. EXPERIMENTOS COMPUTACIONAIS
103
• Sistema Operacional: Linux Ubuntu 12.04, 64 bits;
• Compilador: nvcc release 5.0, V0.2.1221 para versão sequencial e paralela.
6.2
Instâncias de Teste
Esta seção apresenta as instâncias que foram utilizadas para testar os métodos discutidos
nesta dissertação. Lembramos que no UQP deseja-se min / max a função f (x) = xT Qx,
onde Q ∈ Qn×n , x ∈ {0, 1}n e n é um número inteiro positivo que representa o número
de variáveis da instância.
6.2.1
Instâncias da OR Library
A OR Library é um acervo que contém vários conjuntos de instâncias para diversos problemas de otimização combinatória. Especificamente, as instâncias do UQP estão disponı́veis
no site: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/bqpinfo.html. Todas estas instâncias são para problemas de maximização.
Cada instância do UQP é identificada por ‘bqpn’, onde bqp significa binary quadratic
programming e n indica o número de variáveis. Assim, bqp50 representa uma instância
do UQP com 50 variáveis.
As instâncias testadas são separadas em conjuntos de 50, 100, 250, 500, 1000 e 2500 variáveis, contendo 10 elementos cada. Para estas instâncias foram calculadas as densidades
da matriz Q, que é dada por:
Densidade =
c
× 100
n2
onde c é o número de elementos diferentes de zero na matriz Q.
A Tabela 6.1 mostra as densidades das instâncias testadas, onde cada coluna representa: Número da Instância é o número da instância em cada grupo de instâncias e
Densidades indicam as densidades das instâncias. Pode-se concluir dos números dessa
tabela, que a matriz Q tem aproximadamente 10% de constantes com valores diferentes
de zero, ou seja, as matrizes das instâncias testadas são esparsas.
6.2.2
Classe Difı́cil
Esta é uma classe de instâncias para problemas de minimização, que segundo Pardalos
e Rodgers [47] são de difı́cil resolução. Elas têm coeficientes inteiros na matriz Q e possuem
Número da
instância
1
2
3
4
5
6
7
8
9
10
bqp50
8,88
9,84
10,88
9,20
11,04
9,20
10,16
11,76
10,32
8,88
bqp100
9,50
9,88
10,10
9,74
9,42
10,56
9,56
9,98
10,22
9,94
Densidades
bqp250 bqp500
9,98
9,94
9,80
9,86
9,90
10,04
10,16
9,86
10,02
9,90
10,26
9,90
9,96
9,96
9,72
9,86
10,14
9,92
9,82
9,96
104
bqp1000
9,92
9,92
9,96
9,94
9,92
10,00
9,90
9,92
9,92
9,82
bqp2500
9,94
9,90
9,90
9,90
9,90
9,88
9,92
9,90
9,92
9,90
Tabela 6.1: Densidades das instâncias do UQP.
um número exponencial de mı́nimos locais. A fórmula geral para estas instâncias é:
min f (x) = −n(n − 1)
n
X
i=1
sujeito a:
xi −
n/2
X
xi + n
i=1
X
xi xj + n
i<j
X
xi xj
i>j
n
x ∈ {0, 1} .
Esta classe de instâncias é interessante, porque a heurı́stica Gradient Midpoint Method
(Seção 3.8.4) sempre encontra uma solução ótima, embora seja muito difı́cil prová-la
com o método Branch and Bound. Toda solução com n/2 variáveis com valor igual a
2n
1 é um dos
mı́nimos locais discretos. Uma solução para a instância é um vetor
n+1
x∗ = [1, . . . , 1, 0, . . . , 0], com as primeiras n/2 variáveis com valor 1 e as demais com valor
−n3 − 2n
0. O valor da solução é dado por
.
4
Estas instâncias são identificadas por ‘cdn’, onde cd significa classe difı́cil e n representa o número de variáveis da instância.
Exemplo 6.1. Instância com seis variáveis (referência [47]).






Q=




6.3
−31
6
6
6
6
6
6 −31
6
6
6
6
6
6 −31
6
6
6
6
6
6 −30
6
6
6
6
6
6 −30
6
6
6
6
6
6 −30











Resultados Obtidos por Heurı́sticas
Nesta seção apresentamos os resultados obtidos com das metaheurı́sticas Tabu Search e
Variable Neighborhood Search, apresentadas nas Seções 3.8.1 e 3.8.3. Fazemos uma análise
comparativa entre as versões sequencial e paralela do Tabu Search, utilizando as métricas
de desempenho definidas na Seção 2.2.
6.3.1
105
Comparação entre as implementações do Tabu Search e
do VNS
Agora realizamos uma análise entre os valores das soluções obtidas e o desempenho das
implementações das metaheurı́sticas TS e VNS. O critério de parada em ambas é de
50.000n vizinhos, onde n é o número de variáveis da instância.
As Tabelas 6.2 e 6.3 mostram as comparações entre os métodos, onde as colunas: Exato
apresenta o valor da solução obtida pelo solver IBM ILOG CPLEX (ver Seção 6.4.1) e
Melhor valor é o melhor valor conhecido apresentado em [10]. As colunas Valor ótimo e
Melhor valor foram incluı́das para fornecer uma referência sobre a qualidade das soluções
obtidas; Tempo até solução é o tempo, em segundos, que o método leva para encontrar a
solução; Tempo total é o tempo, em segundos, que o método consumiu em sua execução
completa; Dif é a diferença entre o valor da solução encontrada pelo método e o valor de
uma solução ótima ou da melhor solução conhecida. O sı́mbolo ‘-’ é usado nesta coluna
para representar que a diferença tem valor zero.
Exato
Dif
TS
Tempo até
solução (s)
Tempo
total (s)
2.098
3.702
4.626
3.544
4.012
3.693
4.520
4.216
3.780
3.507
-
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,00
0,02
0,10
7.970
11.036
12.723
10.368
9.083
10.210
10.125
11.435
11.455
12.565
-
0,02
0,04
0,02
0,00
0,08
0,07
0,06
0,00
0,00
0,00
Instâncias
Valor ótimo
bqp50
1
2
3
4
5
6
7
8
9
10
bqp100
1
2
3
4
5
6
7
8
9
10
Dif
VNS
Tempo até
solução (s)
Tempo
total (s)
0,53
0,52
0,52
0,52
0,52
0,51
0,52
0,52
0,52
0,53
76
-
0,02
0,00
0,03
0,00
0,01
0,00
0,00
0,00
0,01
0,01
0,78
0,77
0,77
0,77
0,77
0,78
0,76
0,78
0,77
0,77
1,58
1,56
1,57
1,58
1,57
1,57
1,57
1,59
1,58
1,57
72
41
8
156
-
1,25
1,82
0,06
0,19
0,57
0,40
0,10
0,09
0,21
1,55
2,86
2,89
2,83
2,84
2,99
2,86
2,86
2,96
2,95
2,85
Tabela 6.2: Comparação entre valores de soluções ótimas e de soluções obtidas por metaheurı́sticas.
Para instâncias com mais de 100 variáveis, não dispomos de soluções ótimas (ver Seção 6.4.1). Portanto, na Tabela 6.3 continuamos a comparação dos métodos utilizando a
coluna Melhor valor, para termos uma referência sobre a qualidade das soluções encon-
106
tradas.
Da Tabela 6.2 inferimos que: o TS gerou soluções ótimas em menos de 1 segundo e que
a implementação do VNS não produziu soluções ótimas para cinco instâncias e consumiu
mais tempo que a do TS.
Da Tabela 6.3 concluı́mos que: o TS encontrou soluções com mesmos valores que
as soluções reportadas em [10] para 22 instâncias e o VNS para uma instância. O TS
encontrou soluções melhores que as reportadas em [10] para 13 instâncias. O TS consumiu
menos tempo que o VNS para todas as instâncias e sempre obteve soluções com valores
melhores ou iguais. Para as instâncias grandes (bqp2500) o TS e o VNS terminaram
suas execuções em menos de 45 minutos, mas o TS encontrou sua melhor solução em até
29 minutos para três instâncias e em até 10 minutos para as outras, enquanto o VNS
encontrou sua melhor solução em um tempo próximo dos 45 minutos.
6.3.2
Comparações entre as implementações do Tabu Search Sequencial e Paralelo utilizando Recálculo com Mudança de
uma Variável
Nesta seção são comparados os tempos de execução das versões sequencial e paralela
das implementações do TS. Na Tabela 6.4 são apresentados resultados para uma análise
dos tempos de execução das duas implementações. Nestes experimentos foi utilizado
uma GPU. As colunas Tempo Médio e Desvio mostram os tempos médios e os desvios
padrão dos tempos de execução, considerando as 10 instâncias com a mesma quantidade
de variáveis.
Da Tabela 6.4 e da Figura 6.1 notamos que para as instâncias pequenas (bqp50 e
bqp100), a implementação sequencial executou mais rápido que a paralela. Para as instâncias bqp250, bqp500, bqp1000 e bqp2500 a implementação paralela foi mais rápida que
Tempo (s)
10000
Programa Sequencial
1000
Programa Paralelo
100
10
1
0,1
bqp50
bqp100
bqp250
bqp500
bqp1000
bqp2500
Figura 6.1: Comparação entre as implementações sequencial e paralela do Tabu Search,
com recálculo do valor da função objetivo com mudança no valor de uma variável. Os
tempos estão em escala logarı́tmica.
Instâncias
bqp250
1
2
3
4
5
6
7
8
9
10
bqp500
1
2
3
4
5
6
7
8
9
10
bqp1000
1
2
3
4
5
6
7
8
9
10
bqp2500
1
2
3
4
5
6
7
8
9
10
Ref. [10]
Melhor
valor
Dif
TS
Tempo até
solução(s)
Tempo
total (s)
45.607
44.810
49.037
41.274
47.961
41.014
46.757
35.726
48.916
40.442
-
0,06
0,05
0,05
0,09
0,03
0,6
0,06
0,39
0,04
0,28
116.586
128.223
130.812
130.097
125.487
121.719
122.201
123.559
120.798
130.619
-116
1
-
371.438
354.932
371.226
370.560
352.736
359.452
370.999
351.836
348.732
351.415
1.515.011
1.468.850
1.413.083
1.506.943
1.491.796
1.468.427
1.478.654
1.484.199
1.482.306
1.482.354
107
Dif
VNS
Tempo até
solução(s)
Tempo
total (s)
8,82
8,95
8,94
8,96
8,99
8,95
8,96
9,01
8,98
8,98
124
707
88
83
6
92
56
1.275
488
-
5,93
6,12
4,41
4,95
6,32
8,63
3,94
4,01
9,00
2,94
8,87
9,00
9,01
9,01
9,05
8,96
8,91
9,01
9,02
8,99
2,68
0,18
0,59
1,33
3,23
0,07
2,5
18,99
0,44
2,18
38,29
38,41
38,47
38,43
38,35
38,35
38,34
38,34
38,38
38,44
3.335
2.923
2.551
2.684
2.292
4.577
4.237
4.932
2.259
2.445
39,87
40,35
38,44
40,34
39,49
39,47
40,28
39,17
40,16
40,24
40,28
40,35
40,46
40,52
40,48
40,47
40,47
40,56
40,57
40,43
-10
-115
-24
-177
-194
-158
-110
-
118,37
15,66
0,74
33,04
59,8
1,49
52,17
198,91
60,78
31,05
299,27
298,42
298,14
298,63
298,33
298,66
298,58
298,4
298,72
298,51
369
4.576
2.549
3.882
542
1.865
2.886
1.169
2.380
2.711
318,51
317,91
319,17
318,25
311,39
318,10
317,74
318,17
320,87
320,95
318,51
318,87
319,17
318,25
318,92
318,10
317,74
318,17
320,87
322,22
-583
-1.629
-693
-758
-20
223
453
2.024
2
173,33
1.394,16
953,61
1.185,58
318,09
373,32
651,73
301,53
469,79
1.708,79
2.640,89
2.648,37
2.645,20
2.644,22
2.643,55
2.644,94
2.644,11
2.649,03
2.646,36
2.644,52
8.120
13.839
8.215
14.108
13.896
6.839
6.963
9.877
7.842
10.372
2.664,05
2.562,67
2.562,97
2.691,09
2.686,51
2.687,05
2.687,58
2.687,28
2.672,16
2.563,33
2.664,05
2.562,67
2.562,97
2.691,09
2.686,51
2.687,05
2.687,58
2.687,28
2.672,16
2.563,33
Tabela 6.3: Comparação entre valores de soluções obtidas por metaheurı́sticas, considerando as implementações sequenciais.
Instâncias
Nome
bqp50
bqp100
bqp250
bqp500
bqp1000
bqp2500
Sequencial
Tempo Médio (s) Desvio (s)
0,52
0,01
1,57
0,01
8,95
0,05
38,38
0,06
298,57
0,30
2.645,12
2,36
108
Paralelo
Tempo Médio (s) Desvio (s)
2,24
0,01
2,60
0,00
3,47
0,01
6,88
0,03
12,48
0,10
59,05
2,54
Tabela 6.4: Comparação entre as implementações sequencial e paralela do Tabu Search,
com recálculo do valor da função objetivo com mudança no valor de uma variável.
a sequencial. A diferença entre os tempos de execução das duas implementações cresceu
quando aumentou-se o número de variáveis. Os desvios padrão dos tempos de execução
são pequenos, considerando todas instâncias nos dois métodos.
Para realizar uma análise dos resultados usamos as métricas: speedup, eficiência, trabalho, sobrecarga e a Lei de Amdahl. As definições destas métricas encontram-se na Seção
2.2.
A Tabela 6.5 apresenta os valores das métricas considerando as implementações sequencial e a paralela do TS. As colunas sob o tı́tulo Métricas apresentam os valores dos
cálculos das métricas para cada classe de instâncias, onde a eficiência é dada em porcentagem e o trabalho e a sobrecarga são dados em minutos, horas e dias; a coluna Lei de
Amdahl 1536 procs. é uma referência do máximo speedup teórico desse algoritmo paralelizado com 1536 processadores;
A análise apresentada na Tabela 6.5 sobre as métricas, é feita para os tempos de execução apresentados na Tabela 6.4. A Lei de Amdahl é calculada com base na porcentagem
não paralelizável do algoritmo, que é apresentada na Tabela 6.6.
Instâncias
Nome
bqp50
bqp100
bqp250
bqp500
bqp1000
bqp2500
Speedup
0,23
0,61
2,58
5,58
23,92
44,79
Métricas
Eficiência (%) Trabalho
0,02
57,46m
0,04
1,11h
0,17
1,48h
0,36
2,94h
1,56
5,33h
2,92
1,05d
Sobrecarga
57,45m
1,11h
1,48h
2,92h
5,24h
1,02d
Lei de Amdahl
1536 procs.
6,69
20,50
82,68
182,42
355,24
243,04
Tabela 6.5: Métricas para o TS com Recálculo com Mudança de uma Variável. Os
sı́mbolos m, h e d significam minutos, horas e dias.
Da Tabela 6.5 percebemos que para as instancias pequenas (bqp50 e bqp100) temos
um speedup do tipo Slowdown. Para as outras instâncias ocorre um speedup Sublinear,
chegando em até 44,79 para as instâncias bqp2500. As eficiências são menores que 3% e
os trabalhos e sobrecarga chegam até 1 dia. De fato a sobrecarga realizada pelo programa
paralelo é muito grande, só se atinge os speedups obtidos devido a grande quantidade de
109
núcleos na GPU. A Figura 6.2 mostra o gráfico para o speedup. As definições sobre os
tipos de speedup encontram-se na Definição 2.26.
Para realizar o cálculo da Lei de Amdahl, apresentado na Tabela 6.5, é necessário
previamente obter o valor da constante f , que representa a fração da computação que
só pode ser realizada sequencialmente, como apresentamos na Definição 2.30. Pode-se
calcular o valor de f de duas maneiras:
• Se o algoritmo tem um fluxo “bem comportado”, é possı́vel fazer uma análise do
algoritmo e determinar qual a porção, número no intervalo [0, 1], do algoritmo que
só pode ser executada sequencialmente;
• Se o fluxo do algoritmo for “complexo”, uma abordagem empı́rica pode ser adotada.
Dentro do programa sequencial criam-se dois contadores: Ts para a parte que só
pode ser executada sequencialmente e Tp para a parte perfeitamente paralelizável.
Atribuı́-se aos contadores a quantidade de tempo despendida para realizar cada
Ts
.
parte do algoritmo. O cálculo é feito da seguinte forma f =
Ts + Tp
A Tabela 6.6 apresenta os valores de Ts, Tp, Total e f que foram obtidos de forma
experimental, onde a coluna Ts, em milissegundos (ms), representa o tempo médio de
execução da parte do algoritmo que só pode ser executada sequencialmente; a coluna
Tp (ms) representa o tempo médio de execução da parte do algoritmo que pode ser
perfeitamente paralelizável; a coluna Total (ms) representa a soma das colunas Tp e Ts;
f representa a porcentagem do algoritmo que só pode ser executada de forma sequencial.
Os valores dos tempos são apresentados em milissegundos para não se perder precisão
numérica ao efetuar o cálculo do valor de f.
Observando os resultados apresentados na Tabela 6.6, nota-se que ao aumentar o
número de variáveis nas instâncias testadas, diminuiu o valor na coluna f, com exceção
para as instâncias bqp2500. Isto ocorreu porque para estas instâncias, a implementação
executou proporcionalmente mais vezes a busca local do que para as outras instâncias.
Speedup
50
40
30
20
10
0
bqp50
bqp100
bqp250
bqp500
bqp1000
bqp2500
Figura 6.2: Métrica speedup para a implementação do Tabu Search, com recálculo do valor
da função objetivo com mudança no valor de uma variável.
110
Como a busca local não foi paralelizada, isto causou um aumento na parte sequencial.
Instâncias
Nome
bqp50
bqp100
bqp250
bqp500
bqp1000
bqp2500
Ts (ms)
77,53
75,77
102,53
185,53
696,69
9.167,57
Tempos
Tp (ms)
442,87
1.497,38
8.850,80
38.195,48
297.868,71
2.635.950,99
Total (ms)
520,40
1.573,15
8.953,34
38.381,01
298.565,39
2.645.118,56
Parte Sequencial
f (%)
14,8982
4,8164
1,1451
0,4833
0,2333
0,3465
Tabela 6.6: Valores utilizados para os cálculos nas Lei de Amdahl da Tabela 6.5. Os
tempos são dados em milissegundos.
6.3.3
Comparações entre as implementações do Tabu Search Sequencial e Paralelo com Cálculo do Valor da Função Objetivo na Forma Básica
De acordo com o que foi definido na Seção 5.1.1, chamamos cálculo na forma básica o
n P
n
P
qij xi xj . Desejamos
cálculo do valor da função objetivo da seguinte maneira:
i=1
j=1
investigar métricas de desempenho com relação às implementações do Tabu Search com
esta forma de cálculo do valor da função objetivo. Esta forma de se calcular o valor da
função objetivo utiliza mais operações que o recálculo, portanto é de se esperar que o
tempo total de execução dos programas sejam maiores. Mas com isto podemos investigar
como as GPUs se comportam ao executar este método com maior número de operações
no kernel. Os demais aspectos da implementação continuam os mesmos.
Para a implementação do TS com o cálculo do valor da função objetivo na forma
básica, não foi possı́vel fazer um acesso combinado à memória global ao buscar os dados
da matriz Q. Portanto, foram implementadas duas versões paralelas para comparação,
uma que mantém a matriz na memória global e outra que efetua uma cópia dessa matriz
para a memória compartilhada.
A Tabela 6.7 exibe informações sobre os tempos de execução das implementações
sequencial e das duas versões do TS paralelo com cálculo do valor da função objetivo na
forma básica. As colunas sob o tı́tulo T. Médio e Desvio apresentam os tempos médios e
os desvios padrão dos tempos de execução, considerando as 10 instâncias com a mesma
quantidade de variáveis. As colunas sob o tı́tulo Sequencial contém valores referentes a
implementação sequencial; As colunas sob os tı́tulos Paralelo Mem. Global e Paralelo
Mem. Comp. contêm valores referentes às implementações paralelas utilizando somente
a memória global para armazenar a matriz Q e a que faz uma cópia da matriz para
a memória compartilhada. O sı́mbolo ‘-’ usado nesta tabela, representa que não foram
coletadas informações para estas instâncias e o sı́mbolo ‘a.u.’ significa amostra única.
Instâncias
Nome
bqp50
bqp100
bqp250
bqp500
bqp1000
bqp2500
Sequencial
T. Médio Desvio
1,23s
0,01s
12,66s
0,02s
3,74m
0,01s
31,16m 0,63m
4,26h
a.u.
-
Paralelo Mem.
T. Médio
2,74s
10,14s
1,04m
4,37m
17,47m
3,64h
Global
Desvio
0,09s
0,00s
0,01s
0,00m
0,00m
a.u.
111
Paralelo Mem.
T. Médio
1,16s
3,71s
21,05s
1,43m
5,68m
1,76h
Comp.
Desvio
0,09s
0,00s
0,00s
0,01m
0,00m
0,00h
Tabela 6.7: Comparação entre as Implementações Sequencial e Paralela do TS com cálculo
do valor da função objetivo na forma básica.
Na Tabela 6.7 podemos observar que para as instâncias bqp50, a implementação sequencial foi mais rápida que as duas paralelas. Os tempos médios da implementação com
memória compartilhada são menores que os daqueles cuja implementação utiliza somente
a memória global. Todos os desvios padrão, apresentados na tabela, são pequenos. Para
a instância bqp2500 a versão paralela que utiliza a memória compartilhada consumiu 1,76
horas, a versão paralela com memória global consumiu 3,64 horas, enquanto a versão
sequencial ultrapassou 10 horas de execução.
A Tabela 6.8 apresenta os valores das métricas considerando as implementações do TS
sequencial e a paralela utilizando somente a memória global da GPU, enquanto a tabela
6.9 considera as implementações sequencial e a paralela utilizando a memória global e a
memória compartilhada da GPU. As colunas dessas tabelas têm os mesmos significados
das que foram mostradas na Tabela 6.5. O sı́mbolo ‘-’ significa que não foram coletados
os tempos para a implementação sequencial.
A análise apresentada nas Tabelas 6.8 e 6.9 sobre as métricas, é feita para os tempos de
execução apresentados na Tabela 6.7. Os valores na coluna Lei de Amdahl foram calculados com base na fração não paralelizável do algoritmo, que é apresentada na Tabela 6.11.
Instâncias
Nome
bqp50
bqp100
bqp250
bqp500
bqp1000
bqp2500
Speedup
0,45
1,25
3,61
7,13
14,64
-
Métricas (Memória Global)
Eficiência (%) Trabalho (s) Sobrecarga (s)
0,03
1,17h
1,17h
0,08
4,33h
4,32h
0,23
1,10d
1,00d
0,46
4,66d
4,64d
0,95
19,73d
19,56d
-
Tabela 6.8: Métricas para o TS com cálculo do valor da função objetivo na forma básica.
Das Tabelas 6.8 e 6.9 e da Figura 6.3 vemos que os speedups e as eficiências da implementação com memória compartilhada são sempre maiores do que os da implementação
com memória global. Notamos também que o trabalho e a sobrecarga da implementação com memória compartilhada são sempre menores do que os da implementação com
memória global.
Instâncias
Nome
bqp50
bqp100
bqp250
bqp500
bqp1000
bqp2500
Speedup
1,06
3,41
10,65
21,78
45,06
-
112
Métricas (Memória Compartilhada)
Eficiência (%) Trabalho (s) Sobrecarga (s)
0,07
29,78m
29,76m
0,22
1,58h
1,58h
0,69
8,98h
8,92h
1,42
1,53d
1,50d
2,93
6,05d
5,88d
-
Tabela 6.9: Métricas para o TS com cálculo do valor da função objetivo na forma básica
com memória compartilhada.
Speedup
45
40
35
30
25
20
15
10
5
0
bqp50
Mem. Compartilhada
Mem. Global
bqp100
bqp250
bqp500
bqp1000
bqp2500
Figura 6.3: Métrica speedup para a implementação do TS com cálculo do valor da função
objetivo na forma básica.
A Tabela 6.10 exibe os valores dos cálculos na Lei de Amdahl, para o TS com cálculo do
valor da função objetivo na forma básica. As colunas 1536 procs. e ∞ procs. representam
os máximos speedups teóricos utilizando respectivamente 1536 e infinitos processadores.
Instâncias
Nome
bqp50
bqp100
bqp250
bqp500
bqp1000
bqp2500
Lei de Amdahl
1536 procs. ∞ procs.
13,89
14,01
45,06
46,39
126,27
137,49
100,57
107,54
81,10
85,56
-
Tabela 6.10: Lei de Amdahl para o TS com cálculo do valor da função objetivo na forma
básica.
Da Tabela 6.10 podemos ver que os valores das colunas 1536 procs. e ∞ procs. são
próximos. Para estas implementações o máximo speedup teórico que pode ser obtido é de
137,49.
Instâncias
Nome
bqp50
bqp100
bqp250
bqp500
bqp1000
bqp2500
Ts (ms)
100,15
276,35
1.577,68
16.761,63
172.109,76
-
Tempos
Tp (ms)
1.302,53
12.542,84
215.331,17
1.785.823,84
14.554.338,11
-
Total (ms)
1.402,68
12.819,19
216.908,84
1.802.585,47
14.726.447,87
-
113
Parte Sequencial
f (%)
7,14
2,1557
0,7273
0,9298
1,1687
-
Tabela 6.11: Valores utilizados na Tabela 6.10 para o cálculo dos valores na Lei de Amdahl.
6.4
Resultados Obtidos pelos Métodos Exatos
Nesta seção apresentamos os resultados dos experimentos computacionais obtidos por
meio de métodos exatos.
6.4.1
Resultados com o Solver CPLEX
Para obter os valores ótimos para algumas instâncias do UQP, utilizamos o solver IBM
ILOG CPLEX versão 12.4 e o método B&B descrito na Seção 3.9.2. Resolvemos as
instâncias utilizando dois módulos desse software: o de Programação Quadrática Inteira
(QIP) e o de Programação Linear Inteira Mista (MIP). Ao longo deste texto denotaremos
por CPLEX o software da IBM.
Os experimentos computacionais desta seção foram executados em uma máquina com
configurações inferiores ao dos demais experimentos. Este computador possui um processador Intel Xeon 64 bits com 4 núcleos de 2.53 GHz e 5.8 GB de memória RAM. O
objetivo desta seção é conhecer os valores de soluções ótimas e não o de competir em
tempo com a implementação da IBM, mesmo porque não implementamos a versão do
Branch and Bound com o recálculo do limitante inferior à ∇f (x) (ver Seção 5.1.4), o que
possivelmente reduziria muito o tempo de execução da implementação do B&B.
Antes de utilizar o módulo MIP tivemos que linearizar o UQP (ver Seção 3.4). Isto é,
transformamos cada programa quadrático em seu correspondente programa linear inteiro,
chamamos este processo de linearização do programa quadrático. Esta transformação é
feita de forma rápida, O(n2 ) e portanto não contabilizamos o tempo da transformação na
Tabela 6.12.
Os resultados obtidos por meio dos módulos QIP e MIP encontram-se na Tabela 6.12,
onde cada coluna representa: Valor e Tempo mostram os valores das soluções ótimas e os
tempos de execução. Os tempos são dados em segundos. Precisa ficar claro que os valores
ótimos obtidos pelos módulos QIP e MIP são iguais.
A Tabela 6.13 mostra as médias dos tempos de execução e seus respectivos desvios
Número da
Instância
1
2
3
4
5
6
7
8
9
10
Instâncias bqp50
Quadrático
Valor Tempo (s)
2.098
0,08
3.702
0,03
4.626
0,02
3.544
0,03
4.012
0,05
3.693
0,02
4.520
0,02
4.216
0,04
3.780
0,08
3.507
0,04
Linearizado
Tempo (s)
0,5
0,64
0,59
0,51
0,43
0,42
0,63
0,7
0,75
0,87
114
Instâncias bqp100
Quadrático
Linearizado
Valor Tempo (s)
Tempo (s)
7.970
137,08
85,58
11.036
43,55
35,6
12.723
8,92
23,84
10.368
8,95
44,07
9.083
14,01
34,74
10.210
249,09
94,68
10.125
495,46
53,1
11.435
19,38
26,28
11.455
1,75
33,79
12.565
6,07
27,97
Tabela 6.12: Soluções e tempos obtidos pelo CPLEX.
padrão para os dados apresentados na Tabela 6.12. Vemos que o tempo médio de execução
do modelo quadrático é menor para as instâncias bqp50, mas para as instâncias bqp100,
isso nem sempre acontece. Vemos que o desvio padrão é grande tanto para o modelo
quadrático como para o linearizado. Isto dá evidências de que a dificuldade de resolução
de uma instância não depende somente do seu número de variáveis, mas também da
estrutura da matriz Q e das várias decisões tomadas pelo método durante sua execução.
Instância
Nome
bqp50
bqp100
Quadrático
Média Desvio
0,04
0,02
98,43 160,59
Linearizado
Média Desvio
0,60
0,14
45,97
24,90
Tabela 6.13: Médias e desvios padrão dos tempos de execução do CPLEX.
Foi possı́vel executar os testes para instâncias com até 100 variáveis. Ao tentar resolver
as instâncias maiores o CPLEX gerou um erro de falta de memória RAM e o processo
foi automaticamente abortado. Vale ressaltar que o CPLEX utilizou os quatro núcleos
disponı́veis no processador.
6.4.2
Comparações entre as implementações do Branch and
Bound Sequencial e Paralelo com Cálculo do Valor da Função Objetivo na Forma Básica
Nesta seção fazemos uma comparação entre as versões sequencial e paralela da implementação do B&B e exibimos métricas de desempenho para estas versões. Não fizemos uma
análise da Lei de Amdahl para estas implementações, pois todo o método foi paralelizado. Assim, os valores para essa métrica são muito próximos ou iguais ao número de
processadores da execução de maneira paralela.
Inicialmente executamos a implementação sequencial do método Gradient Midpoint
115
Method, fornecemos o seu resultado como entrada para a implementação sequencial do
Tabu Search e então executamos o método Branch and Bound fornecendo como entrada
a solução encontrada pelo TS. O critério de parada do TS foi um número máximo de
5.000n iterações ou se não obtiver uma solução melhor que a melhor encontrada por 500n
iterações, onde n é o número de variáveis da instância.
A implementação paralela dividiu o problema principal de cada instância em 214 subproblemas de igual tamanho, que foram resolvidos utilizando o Algoritmo 5.2.4. A quantidade de subproblemas a ser utilizado foi decidida de forma empı́rica e 214 foi a que surtiu
melhores resultados.
A Tabela 6.14 exibe a comparação entre as versões sequencial e paralela do método
B&B executadas para as instâncias de 50 variáveis da OR Library (que são problemas
de maximização, ver Seção 6.2.1) e para instâncias da classe difı́cil (que são problemas
de minimização, ver Seção 6.2.2). A coluna Instâncias indica a instância testada. As
instâncias que começam com “bqp” são as obtidas na OR Library, de forma que bqp50.x
representa a instância de 50 variáveis e x o número da instância. As instâncias que
começam com “cd” são instâncias da classe difı́cil; A coluna GMM contém os valores
das soluções obtidas pelo método Gradient Midpoint Method; A coluna TS contém os
valores das soluções obtidas pelo método Tabu Search; A coluna B&B contém os valores
das soluções obtidas pelo método Branch and Bound; A coluna NSUBP indica o número
de subproblemas resolvidos pelo método B&B sequencial (ver Linha 13 do Algoritmo
3.9.1); A coluna Tempo Sequencial (ms) indica o tempo, em milissegundos, das execuções
da implementação do método B&B sequencial; A coluna Tempo Paralelo (ms) indica o
tempo, em milissegundos, das execuções da implementação do método B&B paralelo;
Da Tabela 6.14 podemos concluir que o método Gradient Midpoint Method forneceu
soluções com valor, em média, aproximadamente 80% do valor de uma solução ótima, para
as instâncias “bqp50.x”. Já para as instâncias da classe difı́cil, esse método encontrou uma
solução ótima, mas não podemos esquecer que esta é uma caracterı́stica especı́fica destas
instâncias, conforme destacada na Seção 3.8.4. O método Tabu Search encontrou soluções
com valores, em média, 99,9% do valor de uma solução ótima. Para as instâncias bqp50.x,
a implementação sequencial do método B&B foi mais rápida que a paralela e a instância
que precisou resolver mais subproblemas foi a bqp50.8, com 518 subproblemas resolvidos.
Para as instâncias da classe difı́cil, a implementação paralela do B&B foi mais rápida que
a sequencial e a instância que menos precisou resolver subproblemas foi a cd12 com 924
subproblemas resolvidos. É interessante notar que para as instâncias da classe difı́cil, os
números de subproblemas crescem rapidamente com o aumento do número de variáveis.
Talvez isto aconteça devido a grande quantidade de mı́nimos locais em cada instância.
A Tabela 6.15 mostra os valores para as métricas envolvendo as implementações sequencial e a paralela do B&B, com relação aos tempos de execução exibidos na Tabela
Instâncias
bqp50.1
bqp50.2
bqp50.3
bqp50.4
bqp50.5
bqp50.6
bqp50.7
bqp50.8
bqp50.9
bqp50.10
cd12
cd14
cd16
cd18
cd20
cd22
cd24
cd26
cd28
cd30
Valores das Soluções
GMM
TS
B&B
1.011
2.098
2.098
2.570
3.678
3.702
3.442
4.626
4.626
2.817
3.502
3.544
3.244
4.012
4.012
3.284
3.693
3.693
3.586
4.520
4.520
3.578
4.216
4.216
3.018
3.780
3.780
3.057
3.507
3.507
-438
-438
-438
-693
-693
-693
-1.032 -1.032 -1.032
-1.467 -1.467 -1.467
-2.010 -2.010 -2.010
-2.673 -2.673 -2.673
-3.468 -3.468 -3.468
-4.407 -4.407 -4.407
-5.502 -5.502 -5.502
-6.765 -6.765 -6.765
NSUBP
228
211
264
50
65
31
42
518
243
314
924
3.432
12.870
48.620
184.756
705.432
2.704.156
10.400.600
40.116.600
155.117.520
116
Tempos do B&B
Sequencial (ms) Paralelo (ms)
328,85
565,64
300,95
634,45
326,05
431,55
248,46
310,21
251,48
336,3
236,63
1.031,27
252,27
443,99
419,90
718,59
356,71
1.116,65
528,33
787,89
33,10
2,61
86,27
2,65
400,40
3,91
1.895,58
23,98
9.209,26
103,17
43.024,38
481,03
196.950,53
2.241,91
854.008,21
10.196,92
3.823.914,82
44.737,21
16.986.797,41
202.012,91
Tabela 6.14: Resultados das implementações sequencial e paralelo do método Branch and
Bound, com cálculo do valor da função objetivo na forma básica.
6.14. As colunas sob o tı́tulo Métricas apresentam o valor do cálculo das métricas para
cada classe de instâncias, onde a eficiência é dada em porcentagem e o trabalho e a
sobrecarga são dados em segundos, minutos, horas e dias;
Speedup
0,30
0,25
0,20
0,15
0,10
0,05
0,00
bqp50.1
bqp50.2
bqp50.3
bqp50.4
bqp50.5
bqp50.6
bqp50.7
bqp50.8
bqp50.9 bqp50.10
Figura 6.4: Speedup da implementação do B&B para instâncias da OR Library.
Da Tabela 6.15 podemos inferir que para as instâncias “bqp50.x” o speedup é do tipo
Slowdown, que a eficiência é inferior a 1% e que o maior trabalho se deu para a instância
bqp50.9 com 28,59 minutos. Para as instâncias da classe difı́cil o speedup é do tipo
sublinear. O maior speedup foi de 102,40 que foi para a instância cd16 e para as instâncias
de 20 a 30 variáveis o speedup é em média de 86,64. Notamos que a métrica sobrecarga
tem valores muito próximos aos da métrica trabalho e que estas métricas não têm uma
relação direta com o tamanho da instância.
A figura 6.6 apresenta um gráfico do número de problemas resolvidos para cada ins-
Instâncias
Nome
bqp50.1
bqp50.2
bqp50.3
bqp50.4
bqp50.5
bqp50.6
bqp50.7
bqp50.8
bqp50.9
bqp50.10
cd12
cd14
cd16
cd18
cd20
cd22
cd24
cd26
cd28
cd30
Speedup
0,58
0,47
0,76
0,80
0,75
0,23
0,57
0,58
0,32
0,67
12,68
32,55
102,40
79,05
89,26
89,44
87,85
83,75
85,48
84,09
117
Métricas
Eficiência (%) Trabalho
0,04
14,48m
0,03
16,24m
0,05
11,05m
0,05
7,94m
0,05
8,61m
0,01
26,40m
0,04
11,37m
0,04
18,40m
0,02
28,59m
0,04
20,17m
0,83
4,01s
2,12
4,07s
6,67
6,01s
5,15
36,83s
5,81
2,64m
5,82
12,31m
5,72
57,39m
5,45
4,35h
5,56
19,09h
5,47
3,59d
Sobrecarga
14,47m
16,24m
11,04m
7,94m
8,61m
26,40m
11,36m
18,39m
28,58m
20,16m
3,98s
3,98s
5,61s
34,94s
2,49m
11,60m
54,11m
4,11h
18,03h
3,39d
Tabela 6.15: Métricas para o B&B com cálculo do valor da função objetivo na forma
básica. Os sı́mbolos s, m, h e d correspondem a segundos, minutos, horas e dias respectivamente.
Speedup
120
100
80
60
40
20
0
cd12
cd14
cd16
cd18
cd20
cd22
cd24
cd26
cd28
cd30
Figura 6.5: Speedup da implementação do B&B para instâncias da classe difı́cil.
118
Número de Subproblemas
Resolvidos em Milhões
160
140
Subproblemas
120
Exponencial (Subproblemas)
f(x) = 234,66 e1,3377x
100
80
60
40
20
0
cd12
cd14
cd16
cd18
cd20
cd22
cd24
cd26
cd28
cd30
Instâncias
Figura 6.6: Número de subproblemas resolvidos na implementação do B&B para instâncias da classe difı́cil
tância resolvida da classe difı́cil. Note que o crescimento é exponencial e aproximado pela
função f (x) = 234, 66e1,3377x .
Em resumo:
• A implementação do VNS merece aprimoramentos, para que ela possa competir com
as implementações do TS;
• A implementação sequencial do TS resolveu muito bem as instâncias com 50 e 100
variáveis da OR Library;
• A implementação paralela do TS foi executada para instâncias da OR Library e
obteve um speedup slowdown para instâncias de até 100 variáveis e um speedup
sublinear para instâncias de 250 a 2.500 variáveis, chegando a ter uma aceleração
de até 44,79 vezes na execução do programa;
• Quando utilizado o cálculo do valor da função objetivo na forma básica, o TS paralelo
obteve um speedup de até 14,74 para a versão com memória global e de até 45,06
vezes com a versão com memória compartilhada para as instâncias de 1.000 variáveis;
• A implementação sequencial do B&B resolveu instâncias da OR Library de 50 variáveis e instâncias da classe difı́cil com até 30 variáveis;
119
• A implementação paralela do B&B obteve um speedup slowdown para instâncias da
OR Library com 50 variáveis e um speedup sublinear para instâncias da classe difı́cil
com até 30 variáveis, chegando a ter uma aceleração de até 102,4 vezes na execução
do programa;
• Concluı́mos que resolver instâncias do UQP é realmente um grande desafio, mesmo
utilizando processadores com grandes quantidades de núcleos, ou seja, utilizando
GPUs.
Capı́tulo 7
Comentários Finais e Trabalhos
Futuros
Neste capı́tulo discutimos sobre o trabalho de pesquisa que foi realizado nesta dissertação.
Na Seção 7.1 apresentamos nossos comentários finais sobre nossos desenvolvimentos e na
Seção 7.2 tratamos dos possı́veis trabalhos futuros.
7.1
Comentários Finais
Nesta dissertação estudamos o problema de programação quadrática binária irrestrita, que
chamamos de UQP, métodos para resolvê-lo e como implementá-los de maneira paralela
com placas gráficas, GPUs. O UQP pertence a classe de problemas NP-difı́cil e é um
problema interessante porque muitos problemas de otimização combinatória podem ser
modelados desta maneira. Desenvolvemos versões sequenciais e paralelas de métodos não
exatos, conhecidos como metaheurı́sticas, e um método exato, Branch and Bound.
Nas versões paralelas utilizamos a arquitetura CUDA da NVIDIA. Com esta arquitetura é possı́vel usar os vários núcleos disponı́veis GPUs para executar programas de
propósito geral que são executados nas GPUs. Realizamos também contribuições teórica
para o estudo do UQP, especificamente para a forma como o recálculo do valor da função
objetivo pode ser feito.
O cálculo do valor da função objetivo na forma tradicional tem complexidade computacional de O(n2 ) e o recálculo, por nós apresentado, possui complexidade linear. Propusemos uma maneira de calcular um limitante inferior para o valor da função objetivo, que
fornece valores maiores ou iguais aos métodos apresentados na literatura, que é utilizado
no método Branch and Bound descrito na referência [48]. Também desenvolvemos um
recálculo para o limitante inferior da função objetivo com complexidade computacional
120
CAPÍTULO 7. COMENTÁRIOS FINAIS E TRABALHOS FUTUROS
121
linear. Implementamos de maneira sequencial as heurı́sticas (Tabu Search, Variable Neighborhood Search, Gradient Midpoint Method e uma Busca Local) e o método exato Branch
and Bound. De forma paralela com GPUs, implementamos os métodos Tabu Search e o
Branch and Bound.
Para analisar a eficiência de nossas implementações, utilizamos duas classes de instâncias reportadas na literatura. Uma classe de instâncias está disponı́vel na OR Library e
a outra está definida em [48] e é considerada de difı́cil resolução. Quanto ao paralelismo,
conseguimos acelerar a implementação do método Tabu Search em até 44 vezes e a implementação do método Branch and Bound em até 102 vezes, dependendo da instância
testada.
7.2
Trabalhos Futuros
No decorrer dos estudos tivemos muitas ideias. Em algumas foi possı́vel nos aprofundarmos, em outras nem tanto. Nesta seção apresentamos uma lista de tópicos que temos o
interesse em investigar em trabalhos futuros.
Em termos teóricos:
1. Propor uma função que seja um limitante inferior à f (x), que gere valores maiores
ou iguais aos de g2 apresentado na Seção 5.1.4.
2. Criar formas eficientes de recálculo para o limitante inferior ao valor da função
objetivo, quando um subproblema é desempilhado da pilha de problemas ainda não
resolvidos.
3. Modelar problemas de corte e empacotamento na forma UQP.
4. Fazer um estudo poliédrico do espaço de soluções do UQP linearizado.
Em termos de implementação:
1. Implementar o método Branch and Bound com o recálculo do limitante inferior ao
valor da função objetivo descrito na Seção 5.1.4.
2. Implementar uma estrutura de pilha compartilhada entre as threads, possibilitando
que cada thread resolva os próprios subproblemas, bem como os subproblemas gerados por outras threads, quando seu trabalho acabar.
3. Na implementação paralela do método Branch and Bound, poderı́amos fazer cópia
dos vetores lb e ub na memória compartilhada antes de atualizar seus valores.
CAPÍTULO 7. COMENTÁRIOS FINAIS E TRABALHOS FUTUROS
122
4. Implementar uma busca local paralela para o método Tabu Search.
5. Implementar os métodos Tabu Search e Branch and Bound de maneira distribuı́da
com MPI e utilizando GPUs.
6. Verificar o desempenho de um Branch and Bound com busca em largura paralelizado
com GPUs.
7. Melhorar a implementação do método VNS sequencial.
8. Implementar o método VNS em paralelo com GPUs.
9. Na implementação do Branch and Bound, trocar o vetor x por uma variável armazenada nos registradores, que guarde a representação decimal do vetor.
10. Na implementação do Branch and Bound utilizar um único vetor xInc na memória
global, criando uma região crı́tica com funções atômicas quando for atualizar seus
valores.
Referências Bibliográficas
[1] Adams, W. P. and Dearing, P. M., On the Equivalence between Roof Duality and Lagrangian Duality for Unconstrained 0-1 Quadratic Programming Problems, Discrete
Applied Mathematics 48 (1994), no. 1, 1–20.
[2] Bahram, A., Glover, F., Kochenberger, G. A. and Rego, C., One-Pass Heuristics for
Large-Scale Unconstrained Binary Quadratic Programs, European Journal of Operational Research 137 (2002), 272–287.
[3]
, An Unconstrained Quadratic Binary Programming Approach to the Vertex
Coloring Problem, Annals of operations research 139 (2003), no. 1, 229–141.
[4]
, A Unified Modeling and Solution Framework for Combinatorial Optimization
Problems, OR Spectrum 26 (2004), no. 2, 237–250.
[5]
, A New Modeling and Solution Approach for the Number Partitioning Problem, Journal of Applied Mathematics and Decision Sciences (2005), 113–121.
[6] Bahram, A., Glover, F., Kochenberger, G. A. and Wang, H., An Effective Modeling
and Solution Approach for the Generalized Independent Set Problem, Optimization
Letters 1 (2007), no. 1, 111–117.
[7]
, Solving the Maximum Edge Weight Clique Problem via Unconstrained Quadratic Programming, European Journal of Operational Research 181 (2007), no. 2,
592–597.
[8] Bahram, A., Kochenberger, G. A. and Ahmadian, A., 0-1 Quadratic Programming
Approach for the Optimal Solution of Two Scheduling Problems, International Journal
of Systems Science (1994), 401–408.
[9] Barahona, F., A Solvable Case of Quadratic 0-1 Programming, Discrete Applied
Mathematics 13 (1986), no. 1, 23–26.
[10] Beasley, J. E., Heuristic Algorithms for the Unconstrained Binary Quadratic Programming Problem, Tech. report, Working Paper, Imperial College, 1999.
123
REFERÊNCIAS BIBLIOGRÁFICAS
124
[11] Billionet, A. and Sutter, A., Minimization of a Quadratic Pseudo-Boolean Function,
European Journal of Operational Research 78 (1994), 106–115.
[12] Bixby, R. E., Notes on Combinatorial Optimization, 1987.
[13] Boros, E. and Hammer, P. L., Pseudo-Boolean Optimization, Discrete Applied Mathematics 123 (2002), 155–225.
[14] Boros, E., Hammer, P. L. and Sun, X., The DDT Method for Quadratic 0-1 Minimization, RUTCOR Research Center (1989), 39–89.
[15] Caporossi, G. and Hansen, P. , Variable Neighborhood Search for Extremal Graphs:
1 The AutoGraphiX system, Discrete Mathematics 212 (2000), no. 1, 29 – 44.
[16] Chakradhar, S. T. and Bushnell, M. L., A Solvable Class of Quadratic 0-1 Programming, Discrete Applied Mathematics 36 (1992), no. 3, 233–251.
[17] Chardaire, P. and Sutter, A., A Decomposition Method for Quadratic Zero-One Programming, Management Science 41 (1994), no. 4, 704–712.
[18] Dowsland, K. A., An exact algorithm for the pallet loading problem, European Journal
of Operational Research 31 (1987), no. 1, 78 – 84.
[19] Duives, J. and Lodi, A. and Malaguti, E., Test-assignment: a quadratic coloring
problem, Journal of Heuristics 19 (2013), no. 4, 549–564.
[20] Glover, F. and Laguna, M., Modern Heuristic Techniques for Combinatorial Problems, ch. Tabu Search, pp. 71–140, Blackwell Scientific, 1993.
[21] Gu, S., A Polynomial Time Solvable Algorithm to Linearly Constrained Binary Quadratic Programming Problems with Q being a Tri-Diagonal Matrix, Advances in Information Sciences and Service Sciences 3 (2011), no. 6, 65–72.
[22] Hammer, P. L. and Hansen, P. and Simeone, B., Roof Duality, Complementation and
Persistency in Quadratic 0-1 Optimization, Mathematical Programming 28 (1984),
no. 2, 121–155.
[23] Hammer, P. L. and Rudeanu, S., Boolean Methods in Operations Research, SpringerVerlag, New York, 1968.
[24] Hanafi, S. and Rebai, A. and Vasquez, M., Several versions of the devour digest tidyup heuristic for unconstrained binary quadratic problems, Journal of Heuristics 19
(2013), no. 4, 645–677.
[25] Hansen, P. and Mladenović, N., Variable Neighborhood Search for the P-Median,
Location Science 5 (1997), no. 4, 207 – 226.
125
[26]
, Variable Neighborhood Search: Principles and Applications, European Journal of Operational Research 130 (2001), no. 3, 449 – 467.
[27]
, Variable Neighborhood Search, Search Methodologies (Edmund K. Burke and
Graham Kendall, eds.), Springer US, 2005, pp. 211–238.
[28] Helmberg, C. and Rendl, F., Solving Quadratic (0,1)-Problems by Semidefinite Programs and Cutting Planes, Mathematical Programming 82 (1998), 291–315.
[29] Horst, R. and Pardalos, P. M. and Thoai, N. V., Introduction to Global Optimization,
Kluwer Academic Publishers, 2000.
[30] Iasemidis, L. D., Shiau, D. S., Sackellares, J.C. and Pardalos, P., Transition to Epileptic Seizures: Optimization, DIMACS Series in Discrete Math and Theoretical
Computer Science 55 (2000), 55–73.
[31] Li, D., Sun, X., Gu, S., Gao, J. and Liu, C., Polynomially Solvable Cases of Binary
Quadratic Programs, Optimization and Optimal Control, Springer Optimization and
Its Applications, 2010, pp. 199–225.
[32] Lima, E. L., Análise Real, Volume 1, ch. Algumas Noções Topológicas, pp. 48–58,
IMPA, 2006.
[33] Lu, Z., Glover, F. and Hao, J., Neighborhood Combination for Unconstrained Binary
Quadratic Problems, MIC 2009: The VIII Metaheuristics International Conference,
2009, pp. 1–7.
[34] Luong, T. V. and Melab, N. and Talbi, E. G., Parallel Local Search on GPU, Tech.
report, Institut National de Recherche en Informatique et en Automatique, 2009.
[35] Merz, P. and Freisleben, B., Genetic Algorithms for Binary Quadratic Programming,
in GECCO-1999: Proceedings of the Genetic and Evolutionary Computation Conference, Morgan Kauffman, 1999, pp. 417–424.
[36]
, Greedy and Local Search Heuristics for the Unconstrained Binary Quadratic
Programming Problem, Journal of Heuristics 8 (2002), no. 2, 197–213.
[37] Merz, P. and Katayama, K., A Hybrid Evolutionary Local Search Approach for the
Unconstrained Binary Quadratic Program, Bio Systems (in press), 2003.
[38] Mohammad, M. A., Bahram, A. and Kochenberger, G. A., A Scatter Search Approach
to Unconstrained Quadratic Binary Programs, McGraw-Hill Ltd., UK, 1999.
[39] Morabito, R. and Morales, S., A simple and effective recursive procedure for the
manufacturer’s pallet loading problem, Journal of the Operational Research Society
49 (1998), 819–928.
126
[40] NVIDIA, C., Whitepaper NVIDIA GeForce GTX 680, http://www.geforce.com/
Active/en_US/en_US/pdf/GeForce-GTX-680-Whitepaper-FINAL.pdf.
[41]
, CUDA by Example, http://developer.download.nvidia.com/books/
cuda-by-example/cuda-by-example-sample.pdf, July 2010.
[42]
, NVIDIA CUDA C: Programming Guide, version 4.0, http:
//developer.download.nvidia.com/compute/DevZone/docs/html/C/doc/CUDA_
C_Programming_Guide.pdf, May 2011.
[43]
, NVIDIA CUDA C Best Pratices Guide, Version 4.1, http://docs.nvidia.
com/cuda/pdf/CUDA_C_Best_Practices_Guide.pdf, 2012.
[44] Palubeckis, G., A Heuristic-Based Branch and Bound Algorithm for the Unconstrained Quadratic Zero-One Programming Problem, Computing (1995), 284–301.
[45] Pardalos, P. and Rodgers, G. P., A Branch and Bound Algorithm for Maximum
Clique problem, Computers & Operations Research 19 (1992), 363–375.
[46] Pardalos, P. and Xue, J., The Maximum Clique Problem, Journal of Global Optimization (1994), 301–328.
[47] Pardalos, P. M. and Rodgers, G. P., Parallel Branch and Bound Algorithms for
Unconstrained Quadratic Zero-One Programming. In: Impacts of Recent Computer
Advances on Operation Research, R. Sharda et al., 1989.
[48]
, Computational Aspects of a Branch and Bound Algorithm for Quadratic
Zero-One Programming, Computing 45 (1990), no. 2, 131–144.
[49]
, Parallel Branch and Bound Algorithms for Quadratic Zero-One Programs on
the Hypercube Architecture, Annals of Operations Research 22 (1990), no. 1, 271–292.
[50] Pardalos, P. M. and Rosen, J. B., Constrained Global Optimization: Algorithms and
Applications (Lecture Notes in Computer Science), Springer-Verlag, 1987.
[51] Polacek, M. and Hartl, R. F. and Doerner, K. and Reimann, M., A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows,
Journal of Heuristics 10 (2004), no. 6, 613–627.
[52] Ravelo, S. V. and Meneses, C. N., Unconstrained Quadratic Binary Programs, Manuscript, 2011, pp. 1–28.
[53] Saad, Y. and Schultz, M. H, Topological Properties of Hipercubes, Tech. report, YALEU/DCS/RR, 1985.
127
[54] Tanenbaum, A. S. and Woodhull, A. S., Sistemas Operacionais: Projeto e Implementação, Bookman, 2000.
[55] Vemuganti, R., Applications of Set Covering, Set Packing and Set Partitioning Models: A Survey, Handbook of Combinatorial Optimization eds Du, D. and Pardalos,
P. M., Kluwer Academic Publishers, 1998, pp. 573–746.
[56] Williams, A. C., Quadratic 0-1 Programming using the Roof Duality with Computational Results, Tech. report, RUTCOR Research Report 8-85, Rutgers University,
New Brunswick, NJ., 1985.

Universidade Federal do ABC - Pós

Transcrição

Documentos relacionados

Sabendo que 1 pé tem 30,48 cm e que 1 polegada tem 2,54 cm

Untitled

Lista de Exerc´ıcios 11 1. Um balde de água contendo 10 litros de

Análise de Algoritmos

142812

Matemática Discreta 2011.1

1 Segunda Prova: EDO - Mecânica /Integral em 20/10/2015 C. A.

Gabarito - Profmat

Lista de exercícios 03

CAP´ITULO 4 INTEGRAIS 4.1 Antiderivadas ou Primitivas