BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
Matheus de Souza Alves Silva
Marcio Tadayuki Mine
Marcone Jamilson Freitas Souza
Gustavo Peixoto Silva
Universidade Federal de Ouro Preto
Luiz Satoru Ochi
Universidade Federal Fluminense
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
SUMÁRIO
 Descrição do problema
 Justificativa do trabalho
 Problema abordado
 Metodologia
 Resultados
 Conclusões e trabalhos futuros
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
DESCRIÇÃO DO PROBLEMA
Conhecido na literatura inglesa como
 Sports Timetabling
 Traveling Tournament Problem (TTP)
Definição
 Montar uma tabela de jogos entre os times participantes de uma
competição esportiva
 Satisfazer às restrições da competição
 Minimizar os custos relativos ao deslocamento dos times
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
DESCRIÇÃO DO PROBLEMA
1
(1)
3
1712Km
Vitória
1
1372Km
Atlético
586Km
(2)
3
Santos 2
3
1712Km
3090Km
Vitória
1372Km
Atlético
3 586Km
Santos
1712Km
2
Grêmio
Grêmio
Vitória x Atlético | Grêmio x Atlético | Atlético x Santos
Atlético x Vitória | Grêmio x Atlético | Atlético x Santos
Distância total percorrida: 6760 Km
Distância total percorrida: 5382 Km
Economia = 1378 Km
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
JUSTIFICATIVA DO TRABALHO




Gastos com deslocamento
Influência no desempenho dos times
Enquadra-se na classe de problemas NP-difíceis
Número de tabelas possíveis para uma competição envolvendo n
times confrontando-se entre si em turnos completos (Concílio &
Zuben (2002)):
(n  1)!(n  3)!(n  5)!...(n  (n  1))!2
( n 1)
n
2
 Competição com 20 participantes: 2,9062x10130 combinações
possíveis
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Abordagem heurística
 Ribeiro & Urrutia (2004) – GRASP e ILS (Iterated Local Search)
 Anagnostopoulos et al. (2003) e Biajoli et al. (2004) – Simulated
Annealing
 Crauwels et al. (2003) – Colônia de Formigas
 Metodologias investigadas
 Método de 2 fases baseadas em backtracking para gerar uma solução
inicial
 Heurísticas Iterated Local Search e Método Randômico de Descida
para refinar a solução inicial
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
PROBLEMA ABORDADO
 Primeira Divisão do Campeonato Brasileiro de Futebol 2004 e 2005
 Realizado em dois turnos completos e espelhados
 Restrições do problema







Cada time joga somente uma vez por rodada
Dois times jogarão entre si duas vezes, uma no turno e a outra no returno,
alternando o mando de campo entre os mesmos
Nas duas primeiras rodadas de cada turno, cada time alternará seus jogos,
sendo um em casa e o outro na casa do adversário
As duas últimas rodadas de cada turno terão a configuração inversa das duas
primeiras rodadas de cada turno com relação ao mando de campo
Não poderá haver jogos entre times do mesmo estado na última rodada
A diferença entre os jogos feitos em cada turno em casa e fora de casa de um
time não pode ser maior que uma unidade
Um time não pode jogar mais que duas vezes consecutivas dentro ou fora de
casa
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Representação de uma solução
Utiliza-se a representação de Anagnostopoulos et al. (2003)
Time \ Rodada
1
2
3
4
5
6
1
+6
+5
-4
+3
-2
-1
2
-5
-3
+2
+6
+1
-4
3
+4
+6
+5
-1
-3
-2
4
+3
+4
-1
-2
-6
+5
5
-2
+1
+6
-5
+4
-3
6
-6
-5
+4
-3
+2
+1
7
+5
+3
-2
-6
-1
+4
Exemplo de uma solução envolvendo 6 times
8
-4
-6
-5
+1
+3
+2
9
-3
-4
+1
+2
+6
-5
10
+2
-1
-6
+5
-4
+3
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Estruturas de Vizinhança
Movimento swap rounds
Time \ Rodada
1
2
3
4
5
6
1
+6
+5
-4
+3
-2
-1
2
-5
-3
+2
+6
+1
-4
3
+4
+6
+5
-1
-3
-2
4
+3
+4
-1
-2
-6
+5
5
-2
+1
+6
-5
+4
-3
6
-6
-5
+4
-3
+2
+1
7
+5
+3
-2
-6
-1
+4
8
-4
-6
-5
+1
+3
+2
9
-3
-4
+1
+2
+6
-5
10
+2
-1
-6
+5
-4
+3
6
-4
-6
-5
+1
+3
+2
7
+5
+3
-2
-6
-1
+4
8
-6
-5
+4
-3
+2
+1
9
-3
-4
+1
+2
+6
-5
10
+2
-1
-6
+5
-4
+3
(1)
Solução inicial
Time \ Rodada
1
2
3
4
5
6
1
+4
+6
+5
-1
-3
-2
2
-5
-3
+2
+6
+1
-4
3
+6
+5
-4
+3
-2
-1
4
+3
+4
-1
-2
-6
+5
5
-2
+1
+6
-5
+4
-3
Solução após a aplicação do movimento swap rounds
(2)
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Estruturas de Vizinhança
Movimento swap teams
Time \ Rodada
1
2
3
4
5
6
1
+6
+5
-4
+3
-2
-1
2
-5
-3
+2
+6
+1
-4
3
+4
+6
+5
-1
-3
-2
4
+3
+4
-1
-2
-6
+5
5
-2
+1
+6
-5
+4
-3
6
-6
-5
+4
-3
+2
+1
7
+5
+3
-2
-6
-1
+4
8
-4
-6
-5
+1
+3
+2
9
-3
-4
+1
+2
+6
-5
10
+2
-1
-6
+5
-4
+3
6
-6
-5
+4
-3
+2
+1
7
+2
-1
-5
-6
+3
+4
8
-4
+3
-2
+1
-6
+5
9
-3
+6
+1
+5
-4
-2
10
+5
-4
-6
+2
-1
+3
(1)
Solução inicial
Time \ Rodada
1
2
3
4
5
6
1
+6
+5
-4
+3
-2
-1
2
-2
+1
+5
+6
-3
-4
3
+4
-3
+2
-1
+6
-5
4
+3
-6
-1
-5
+4
+2
5
-5
+4
+6
-2
+1
-3
Solução após a aplicação do movimento swap teams
(2)
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Estruturas de Vizinhança
Movimento swap homes
Time \ Rodada
1
2
3
4
5
6
1
+6
+5
-4
+3
-2
-1
2
-5
-3
+2
+6
+1
-4
3
+4
+6
+5
-1
-3
-2
4
+3
+4
-1
-2
-6
+5
5
-2
+1
+6
-5
+4
-3
6
-6
-5
+4
-3
+2
+1
7
+5
+3
-2
-6
-1
+4
8
-4
-6
-5
+1
+3
+2
9
-3
-4
+1
+2
+6
-5
10
+2
-1
-6
+5
-4
+3
6
-6
-5
+4
-3
+2
+1
7
+5
+3
-2
-6
-1
+4
8
+4
-6
-5
-1
+3
+2
9
-3
-4
+1
+2
+6
-5
10
+2
-1
-6
+5
-4
+3
(1)
Solução inicial
Time \ Rodada
1
2
3
4
5
6
1
+6
+5
-4
+3
-2
-1
2
-5
-3
+2
+6
+1
-4
3
-4
+6
+5
+1
-3
-2
4
+3
+4
-1
-2
-6
+5
5
-2
+1
+6
-5
+4
-3
Solução após a aplicação do movimento swap homes
(2)
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Estruturas de Vizinhança
Movimento replace teams
Time \ Rodada
1
2
3
4
5
6
1
+6
+5
-4
+3
-2
-1
2
-5
-3
+2
+6
+1
-4
3
+4
+6
+5
-1
-3
-2
4
+3
+4
-1
-2
-6
+5
5
-2
+1
+6
-5
+4
-3
6
-6
-5
+4
-3
+2
+1
7
+5
+3
-2
-6
-1
+4
8
-4
-6
-5
+1
+3
+2
9
-3
-4
+1
+2
+6
-5
10
+2
-1
-6
+5
-4
+3
6
-6
-5
+4
-3
+1
+2
7
+5
+3
-1
-6
-2
+4
8
-4
-6
-5
+2
+3
+1
9
-3
-4
+2
+1
+6
-5
10
+1
-2
-6
+5
-4
+3
(1)
Solução inicial
Time \ Rodada
2
1
3
4
5
6
1
+6
+5
-4
+3
-1
-2
2
-5
-3
+1
+6
+2
-4
3
+4
+6
+5
-2
-3
-1
4
+3
+4
-2
-1
-6
+5
5
-1
+2
+6
-5
+4
-3
Solução após a aplicação do movimento replace teams
(2)
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Função de Avaliação
Baseada em penalidade
f (s)   custo(i)  dif (s)   w j  inv j
iT
em que
jC
f(s):
função de avaliação
T:
C:
custo(i):
dif(s):
conjunto dos times participantes da competição;
conjunto de restrições;
custo de um time i  T;
diferença entre o custo máximo e o custo mínimo
dos times;
penalidade por desrespeitar a restrição j  C;
número de vezes que a restrição j  C está sendo
desrespeitada.
wj:
invj:
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Geração de uma Solução Inicial
Método de duas fases proposto por Silva et al. (2005)
 Primeira Fase: Geração das duas primeiras e duas últimas rodadas do
primeiro turno
 Segunda Fase: Geração das rodadas intermediárias
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Geração de uma Solução Inicial
Método de duas fases proposto por Silva et al. (2005)
 Primeira Fase: Geração das duas primeiras e duas últimas rodadas do
primeiro turno
 Segunda Fase: Geração das rodadas intermediárias
Objetivo da Primeira Fase
Satisfazer às restrições:
 Nas duas primeiras rodadas de cada turno, cada time alternará seus jogos,
sendo um em casa e o outro na casa do adversário
 As duas últimas rodadas de cada turno terão a configuração inversa das duas
primeiras rodadas de cada turno com relação ao mando de campo
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Geração de uma Solução Inicial
Método de duas fases proposto por Silva et al. (2005)
 Primeira Fase: Geração das duas primeiras e duas últimas rodadas do
primeiro turno
 Segunda Fase: Geração das rodadas intermediárias
Time \ Rodada
1
2
3
4
5
6
7
8
1
+4
-5
+6
-1
+2
-3
+8
-7
2
-2
+1
-4
+3
-8
+7
-6
+5
3
4
5
6
-6
+7
-8
+5
-4
+1
-2
+3
7
+8
-3
+2
-7
+6
-5
+4
-1
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Geração de uma Solução Inicial
Método de duas fases proposto por Silva et al. (2005)
 Primeira Fase: Geração das duas primeiras e duas últimas rodadas do
primeiro turno
 Segunda Fase: Geração das rodadas intermediárias
Time \ Rodada
1
2
3
4
5
6
7
8
1
+4
-5
+6
-1
+2
-3
+8
-7
2
-2
+1
-4
+3
-8
+7
-6
+5
3
+3
+4
-1
-2
+7
-8
-5
+6
4
-5
+6
+7
+8
+1
-2
-3
-4
5
-7
-8
+5
-6
-3
+4
+1
+2
6
-6
+7
-8
+5
-4
+1
-2
+3
7
+8
-3
+2
-7
+6
-5
+4
-1
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Geração de uma Solução Inicial
Método de duas fases proposto por Silva et al. (2005)
 Primeira Fase: Geração das duas primeiras e duas últimas rodadas do
primeiro turno
 Segunda Fase: Geração das rodadas intermediárias
Time \ Rodada
1
2
3
4
5
6
7
8
1
+4
-5
+6
-1
+2
-3
+8
-7
2
-2
+1
-4
+3
-8
+7
-6
+5
3
+3
+4
-1
-2
+7
-8
-5
+6
4
-5
+6
+7
+8
+1
-2
-3
-4
5
-7
-8
+5
-6
-3
+4
+1
+2
6
-6
+7
-8
+5
-4
+1
-2
+3
7
+8
-3
+2
-7
+6
-5
+4
-1
8
-4
+5
-6
+1
-2
+3
-8
+7
Solução inicial gerada pelo método
9
+2
-1
+4
-3
+8
-7
+6
-5
10
-3
-4
+1
+2
-7
+8
+5
-6
11
+5
-6
-7
-8
-1
+2
+3
+4
12
+7
+8
-5
+6
+3
-4
-1
-2
13
+6
-7
+8
-5
+4
-1
+2
-3
14
-8
+3
-2
+7
-6
+5
-4
+1
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
METODOLOGIA
 Refinamento da Solução
Método Híbrido ILS-MRD
 Metaheurística Iterated Local Search (ILS)
 Método Randômico de Descida (MRD)
Exploração do Espaço de Soluções
 Estruturas de Vizinhança
•
•
•
•
swap rounds
swap teams
swap homes
replace teams
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
procedimento ILS
s0  SolucaoInicialAleatoria
s  BuscaLocal(s0)
iter  0
enquanto (iter < itermax)
iter  iter + 1
s’  perturbação(s)
s”  BuscaLocal(s’)
se ( f(s”) < f(s) ) faça
s  s”
fim-se
fim-enquanto
retorne s
procedimento ILS-MRD
s0  SolucaoInicial
s  MRD(s0, IterMRD)
kp  kp0
iter  0
enquanto (kp < kpmax)
enquanto (iter - melhorIter < itermax)
iter  iter + 1
s’  perturbação(s, kp)
s”  MRD(s’, IterMRD)
se ( f(s”) < f(s) ) faça
s  s”
melhorIter  iter
kp  kp0
fim-se
fim-enquanto
kp  kp + delta
fim-enquanto
retorne s
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
RESULTADOS COMPUTACIONAIS
 Ambiente de Desenvolvimento e Instâncias Utilizadas
 Linguagem C / Borland C++ Builder v5.0
 PC Athlon XP 2.0GHz, 256 MB RAM
 Windows XP
 Problemas-teste disponíveis em
http://www.decom.ufop.br/prof/marcone/projects/ttp/bssp.html
 100 execuções de cada instância
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
RESULTADOS COMPUTACIONAIS
 Desempenho do Método ILS-MRD
ILS-MRD
Instâncias Melhor Valor
Melhor Média Desvio Tempo (min)
bssp2004
806134 825089
-2,1
29,54
842789(1)
bssp2005
743621 760350 -16,4
21,72
909119(2)
(1) Biajoli et al. (2004); (2) CBF
 Fórmula do Desvio
Desvio  100 
Média  MelhorValo r
MelhorValo r
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
RESULTADOS COMPUTACIONAIS
 Melhores soluções obtidas pelos métodos
Instâncias
bssp2004
bssp2005
CBF
ILS-MRD
Biajoli et al . (2004)
DIST
DIF
FO
DIST
DIF
FO
DIST
DIF
FO
905316 86610 991926 789480 53309 842789 754935 51199 806134
838464 70655 909119
696800 46821 743621
Percentual de melhora em relação ao custo (DIST) – bssp2004
 16,6% em relação à tabela elaborada manualmente pela CBF
 4,4% em relação à tabela de Biajoli et al. (2004)
Percentual de melhora em relação ao custo (DIST) – bssp2005
 16,9% em relação à tabela elaborada manualmente pela CBF
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
RESULTADOS COMPUTACIONAIS
 Melhores soluções obtidas pelos métodos
Instâncias
bssp2004
bssp2005
CBF
ILS-MRD
Biajoli et al . (2004)
DIST
DIF
FO
DIST
DIF
FO
DIST
DIF
FO
905316 86610 991926 789480 53309 842789 754935 51199 806134
838464 70655 909119
696800 46821 743621
Percentual de melhora em relação à diferença (DIF) – bssp2004
 40,9% em relação à tabela elaborada manualmente pela CBF
 4,0% em relação à tabela de Biajoli et al. (2004)
Percentual de melhora em relação à diferença (DIF) – bssp2005
 33,7% em relação à tabela elaborada manualmente pela CBF
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
RESULTADOS COMPUTACIONAIS
 Melhores soluções obtidas pelos métodos
Instâncias
bssp2004
bssp2005
CBF
ILS-MRD
Biajoli et al . (2004)
DIST
DIF
FO
DIST
DIF
FO
DIST
DIF
FO
905316 86610 991926 789480 53309 842789 754935 51199 806134
838464 70655 909119
696800 46821 743621
Economia possível (bssp2004 e bssp2005):
 Considerando o custo do quilômetro aéreo a R$0,70
 Delegação de 20 pessoas
 Aprox. R$ 2 milhões, em relação às tabelas da CBF
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
CONCLUSÕES E TRABALHOS FUTUROS
 Conclusões
Apresenta-se uma metodologia heurística (ILS-MRD)
 Metaheurística Iterated Local Search (ILS)
 Método Randômico de Descida (MRD)
Desempenho do ILS-MRD
 Método robusto e eficiente para resolver o Problema de Programação
de Jogos
 Os resultados obtidos pelo método superam, na média, os melhores
resultados encontrados na literatura
Importância do método de geração da solução inicial
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
CONCLUSÕES E TRABALHOS FUTUROS
 Trabalhos Futuros
 Incorporar ao método técnicas de intensificação, como a
Reconexão por Caminhos (Path Relinking)
BUSCA LOCAL ITERADA APLICADA À RESOLUÇÃO DO
PROBLEMA DE PROGRAMAÇÃO DE JOGOS DE COMPETIÇÕES
ESPORTIVAS REALIZADAS EM DOIS TURNOS ESPELHADOS
AGRADECIMENTOS
 UFOP
 FAPEMIG
 Borland Latin America