Celso C. Ribeiro
Futebol e Otimização:
Classificação, Tabelas e Juízes
Julho 2005
Maceió
Resumo
 Grupo de pesquisa: temas, projetos, aplicações
e equipe
 Problemas de classificação
• Motivação e formulação
• FUTMAX na rede e na imprensa
• Resultados
 Programação de tabelas
• Motivação e formulação
• Heurísticas
• Aplicações
Novembro 2004
Futebol e Otimização
OR in Sports 2/75
Grupo de pesquisa (Diretório CNPq)
Heurísticas e paralelismo para
problemas de otimização e de
bioinformática
Temas básicos
 Metaheurísticas e paralelismo
• Metaheurísticas: métodos gerais para a solução
aproximada de problemas combinatórios NP-difíceis,
que utilizam diferentes estratégias para escapar de
ótimos locais:

Algoritmos genéticos, GRASP, path-relinking, busca tabu,
VNS, simulated annealing, colônias de formigas, busca
espalhada…
• Paralelismo:
Algoritmos mais robustos e menos dependentes de
parâmetros
 Melhores soluções, resolução mais rápida, problemas
maiores
Novembro 2004
Futebol e Otimização
OR in Sports 4/75
 Implementações em grids e clusters (Laboratório de

Projetos, aplicações e equipe
 Escalonamento da produção:
• Seqüenciamento da produção da linha de
montagem da Renault


Lavagens de pistolas de pintura e número de carros de
cada tipo
Desafio Renault-ROADEF’2005: equipe PUC-UFF
classificada em segundo lugar (Caroline, Daniel,
Sebastián, Thiago)
 Projeto e roteamento em redes de
telecomunicações:
• Engenharia de tráfego e otimização do roteamento
Novembro 2004
Futebol e Otimização
OR in Sports 5/75
• Projeto de redes com funções de custo em escada
Projetos, aplicações e equipe
 Biologia computacional:
• Problema da filogenia
• Seqüenciamento de DNA
• Reconhecimento de imagens médicas através de
grafos
 Logística aplicada a esportes:
• Classificação
• Tabelas
• Juízes
 Equipe: 11 doutorandos e 3 mestrandos
Novembro 2004
Futebol e Otimização
OR in Sports 6/75
Logística aplicada a esportes
Classificação
Motivação
 A imprensa anuncia desde cedo as “chances”
de classificação, baseadas em previsões e
estatísticas freqüentemente obscuras (“com 53
pontos qualquer equipe escapa do
rebaixamento em 2004”): previsões anunciadas
são freqüentemente erradas!
 Problema da classificação garantida: quantos
pontos um time deve fazer para ter certeza de
classificar-se para as finais (play-offs) de um
torneio?
• Vitória: 3 pontos, empate: 1 ponto, derrota: 0 ponto
Novembro
2004
Futebol e Otimização
OR in Sports 8/75
• Campeão?
Classificação
para a Libertadores?
Motivação
 Três times disputam duas vagas nos play-offs.
 Cada um tem dois jogos a jogar: Flamengo vs.
Vasco e Bahia, Cruzeiro vs. Grêmio e Santos, e
Bahia vs. Flamengo e Fluminense.
 Quantos pontos o Cruzeiro tem que fazer para
ter certeza de se classificar?
4 pontos!
Flamengo
37
 O problema se complica se Cruzeiro
37
24 equipes participam do Bahia
36
campeonato!
Novembro 2004
Futebol e Otimização
OR in Sports 9/75
Formulação
Problemas de classificação para play-offs:
Quantos pontos uma equipe deve fazer para:
 … ter certeza de terminar nas p primeiras
posições? (condição suficiente para
classificação)
 … ter alguma chance de terminar nas p
primeiras posições? (condição necessária para
classificação)
Campeonato brasileiro 2004:
2004
OR in Sports 10/75
Novembro
Libertadores:
p = 4Futebol e Otimização
Formulação
 Problema da classificação garantida:
quantos pontos um time deve fazer para ter
certeza de classificar-se nas p primeiras
posições?
 Calcular o número máximo de pontos que o
time pode fazer e mesmo assim não ficar
classificado entre os p primeiros: somar 1 a
este número para obter o número mínimo
de pontos para garantir a classificação:
GQS(k)
 Problema da classificação possível:
Novembro 2004
Futebol e Otimização
OR in Sports 11/75
quantos pontos um time deve fazer para ter
Formulação
1, seo timei derrotao time j
xij  
0, casocontrário
p j  pontosjáacumulados
pelotime j
t j  pontosganhos
pelotime j aofinaldotorneio
1, set j  tk (seo timek nãoestáàfrentedotime j )
yj  
0, casocontrário
Novembro 2004
Futebol e Otimização
OR in Sports 12/75
Formulação
GQS(k )  1  máximot k
sujeito a :
xij  x ji  1
k = time sendo consider
i  1,...,n; j  1,...,n; jogo (i, j ) a ser disputado

t j  p j  3.i  j x ji  i  j 1  ( xij  x ji )
t k  t j  M (1  y j )

j  1,...,n

j  1,...,n
tk > tj  yj = 0
y

p
j
j k
xij  {0,1}
i  1,...,n; j  1,...,n; jogo (i, j ) a ser disputado
y j  {0,1}
j  1,...,n
Novembro 2004
Futebol e Otimização
OR in Sports 13/75
Formulação
 Quando o time k está “matematicamente
classificado”?
O time k está matematicamente classificado se
seu problema da classificação guarantida é
inviável.
 Quando o time k depende apenas dele para se
classificar?
O time k depende apenas dele se GQS(k) é
menor ou igual ao número total de pontos que
pode fazer.
Novembro
Quando
o time k está
2004
Futebol“matematicamente
e Otimização
OR in Sports 14/75
FUTMAX na rede e na imprensa
 Projeto FUTMAX:
• Sistema de agentes para coleta automática de
resultados via web (projeto de Thiago Noronha,
doutorando PUC-Rio).
• Modelos gerados automaticamente para cada
time.
• Problemas de programação inteira resolvidos
com CPLEX.
• Arquivo HTML de resultados gerado
automaticamente.
 Publicação automática:
Futebol e Otimização
Novembro 2004
OR in Sports 15/75
FUTMAX na rede e na imprensa
 Site FUTMAX no ar (24/Set/2002)
 Rádio Globo: “Enquanto a bola não rola”
(29/Set/2002)




Caderno Internet do Jornal do Brasil (30/Set/2002)
Entrevista para TV Campus (24/Out/2002)
Artigo no Jornal da PUC (18/Dez/2002)
SPORTV pede cálculos e considera publicação
ao vivo das “chances” de classificação (Out/2003)
 FUTMAX fornece dados para SPORTV News
(7/Nov/2004)
Novembro 2004
Futebol e Otimização
OR in Sports 16/75
FUTMAX na rede e na imprensa
Novembro 2004
Futebol e Otimização
OR in Sports 17/75
Resultados
 Já na 11a. rodada em 2002, alguns times não
mais dependiam apenas de seus resultados
para se classificarem.
 Antonio Lopes, técnico do Vasco, disse que
“basta ganharmos os 10 próximos jogos para
nos classificarmos”.
 FUTMAX mostrou que não era verdade!
Novembro 2004
Futebol e Otimização
OR in Sports 18/75
Resultados
 31/Outubro/2002: São Paulo ganhou da Ponte
Preta fazendo 43 pontos.
 A imprensa (Folha de São Paulo) anunciou que
o São Paulo estava matematicamene
classificado.
 FUTMAX mostrou que não era verdade!
 3/Novembro/2002: São Caetano completou 42
pontos e a imprensa anunciou que estava
matematicamene classificado.
Novembro
De novo,
FUTMAXFutebol
mostrou
2004
e Otimização que não era
OR in Sports 19/75
Resultados
Novembro 2004
Futebol e Otimização
OR in Sports 20/75
Resultados
FUTMAX pode ser usado para acompanhar o desempenho d
Pontos
possíveis
FLUMINEN
Pontos para classificação
SE
garantida
Pontos para classificação
possível
Pontos acumulados
Novembro 2004
Futebol e Otimização
OR in Sports 21/75
Resultados
 Spin-offs: seguido pelo HockeyPlex project
(mesma idéia para a National Hockey League,
USA)
 Tese de doutorado de Sebastián Urrutia (PUCRio, 2005)
 Repercussão e motivação
 Publicações:
Ribeiro & Urrutia, “OR on the ball”, OR/MS Today,
2004.
Novembro 2004& Urrutia, “IPFutebol
e Otimização
OR in Sports 22/75
Ribeiro
applied
to playoff elimination”,
Logística aplicada a esportes
Programação de tabelas
Motivação
 Escalonamento de jogos é um problema
difícil: diferentes restrições, questões de
logística, múltiplos objetivos a otimizar, e
diversos decisores (administradores das
federações, dirigentes, TV, etc.).
 A distância total viajada é um critério
importante a ser minimizado, para reduzir
custos de viagem e dar mais tempo aos
jogadores para descanso e treinamentos.
 Mas é necessário evitar tabelas injustas!
Novembro 2004
Futebol e Otimização
OR in Sports 24/75
Formulação
 Condições:
• n (par) times participam de um torneio.
• Cada time tem seu estádio na cidade onde está
baseado.
• As distâncias entre os estádios são
conhecidas.
• Um time que joga dois jogos consecutivos fora
de casa vai diretamente de uma cidade para a
outra, sem retornar à sua base.
Novembro 2004
Futebol e Otimização
OR in Sports 25/75
Formulação
 Condições (cont.):
• O torneio segue o formato de duplo round-robin
espelhado:



Há 2(n-1) rodadas, cada uma com n/2 jogos.
Cada time joga contra cada outro time exatamente duas
vezes, uma em casa e outra fora.
Jogos do turno e do returno na mesma ordem, invertendose apenas o mando de campo.
• Nenhum time pode jogar mais de três jogos
consecutivos em casa, nem mais de três jogos
consecutivos fora.
 Objetivo: minimizar a distância total viajada por
Novembro
2004 os times.
Futebol e Otimização
OR in Sports 26/75
todos
Formulação
 Dado um grafo G=(V, E), um fator de G é um
grafo G’=(V,E’) com E’E.
 G’ é um 1-fator se todos seus nós tem grau
um.
 Uma fatoração de G=(V,E) é um conjunto de
fatores G1=(V,E1), ..., Gp=(V,Ep) sem arestas
comuns, com E1...Ep=E.
 Todos fatores em uma 1-fatoração de G são
1-fatores.
Novembro 2004
Futebol e Otimização
OR in Sports 27/75
Formulação
1
Exemplo:
1-fatoração de K6
Novembro 2004
5
2
4
3
6
Futebol e Otimização
OR in Sports 28/75
Formulação
1
Exemplo:
1-fatoração de K6
Novembro 2004
1
5
2
4
3
6
Futebol e Otimização
OR in Sports 29/75
Formulação
2
Exemplo:
1-fatoração de K6
Novembro 2004
1
5
2
4
3
6
Futebol e Otimização
OR in Sports 30/75
Formulação
3
Exemplo:
1-fatoração de K6
Novembro 2004
1
5
2
4
3
6
Futebol e Otimização
OR in Sports 31/75
Formulação
4
Exemplo:
1-fatoração de K6
Novembro 2004
1
5
2
4
3
6
Futebol e Otimização
OR in Sports 32/75
Formulação
5
Exemplo:
1-fatoração de K6
Novembro 2004
1
5
2
4
3
6
Futebol e Otimização
OR in Sports 33/75
Formulação
 Torneios espelhados: a tabela do returno é
determinada pela tabela do primeiro turno.
• Cada aresta de Kn representa um jogo.
• Cada 1-fator de Kn representa uma rodada.
• Cada 1-fatoração orientada de Kn é uma
tabela.
• O problema é enorme: a maior instância
resolvida de forma ótima em um único
processador envolve apenas n=6 equipes
(n=8 em paralelo).
Novembro 2004
Futebol e Otimização
OR in Sports 34/75
Heurística construtiva

Montagem de uma tabela inicial: três
etapas
1. Escalonar os jogos usando times abstratos
(estrutura da tabela).
2. Associar times reais aos times abstratos.
3. Atribuir estádios aos jogos (mandos de
campo).

Etapa1: escalonar os jogos usando times
abstratos
• Esta etapa define a estrutura do torneio.
Novembro 2004
Futebol e Otimização
OR in Sports 35/75
• “Método do polígono”
Heurística construtiva
6
Exemplo:
“método do polígono” para n=6
1
5
2
1a rodada
3
4
Novembro 2004
Futebol e Otimização
OR in Sports 36/75
Heurística construtiva
6
Exemplo:
“método do polígono” para n=6
5
4
1
2a rodada
2
3
Novembro 2004
Futebol e Otimização
OR in Sports 37/75
Heurística construtiva
6
Exemplo:
“método do polígono” para n=6
4
3
5
3a rodada
1
2
Novembro 2004
Futebol e Otimização
OR in Sports 38/75
Heurística construtiva
6
Exemplo:
“método do polígono” para n=6
3
2
4
4a rodada
5
1
Novembro 2004
Futebol e Otimização
OR in Sports 39/75
Heurística construtiva
6
Exemplo:
“método do polígono” para n=6
2
1
3
5a rodada
4
5
Novembro 2004
Futebol e Otimização
OR in Sports 40/75
Heurística construtiva
Times abstratos (n=6)
Rodad
A
B
C
D
E
F
1/6
F
E
D
C
B
A
2/7
D
C
B
A
F
E
3/8
B
A
E
F
C
D
4/9
E
D
F
B
A
C
5/10
C
F
A
E
D
B
Novembro 2004
Futebol e Otimização
OR in Sports 41/75
Heurística construtiva

Etapa 2: associar times reais aos times
abstratos
•
Construir uma matriz com o número de jogos
consecutivos para cada par de times abstratos:
para cada par de times abstratos X e Y, uma
entrada nesta tabela contém o número total de
vezes em que os outros times jogam
consecutivamente com X e Y em qualquer ordem.
• Associar pares de times reais aos times abstratos
usando um algoritmo guloso: pares de times reais
com sedes próximas são associados a pares de
Novembro times
2004
Futebolvalores
e Otimização elevados naORmatriz
in Sports 42/75
abstratos com
Heurística construtiva
Novembro 2004
A
B
C
D
E
F
A
0
1
6
5
2
4
B
1
0
2
5
6
4
C
6
2
0
2
5
3
D
5
5
2
0
2
4
E
2
6
5
2
0
3
F
4
4
3
4
3
0
Futebol e Otimização
OR in Sports 43/75
Heurística construtiva
Times reais (n=6)
Rodad FLU SAN FLA GR PAL PAY
1/6
PAY PAL
2/7
GR FLA SAN FLU PAY PAL
3/8
SAN FLU PAL PAY FLA GR
4/9
PAL GR PAY SAN FLU FLA
5/10
FLA PAY FLU PAL GR SAN
Novembro 2004
GR FLA SAN FLU
Futebol e Otimização
OR in Sports 44/75
Heurística construtiva

Etapa 3: atribuir estádios aos jogos
(mandos de campo)
•
•
Novembro 2004
Atribuir estádios de modo que nenhum time
faça mais do que três jogos consecutivos fora
de casa ou em casa.
Melhorar a atribuição de estádios, através de
uma busca local baseada em trocas de
estádios.
Futebol e Otimização
OR in Sports 45/75
Otimização
 Metaheurísticas baseadas em métodos de
busca local:
• Melhorar sucessivamente a solução atual, através
de modificações simples na estrutura da solução
(soluções vizinhas).
Novembro 2004
Futebol e Otimização
OR in Sports 46/75
Vizinhanças
 Vizinhança “casa-fora”: selecionar um jogo
e inverter o estádio onde é realizado.
 Vizinhança “troca de times”: selecionar dois
times e inverter todos seus jogos rodada a
rodada.
 Vizinhança “troca parcial de rodada”:
selecionar dois jogos AxB e CxD da rodada
X e dois jogos AxC e BxD da rodada Y e
inverter as rodadas destes jogos (apenas
para n8, nem sempre é possível).
Novembro
2004
Futebol e Otimização
OR in Sports 47/75
 Gerar
e avaliar soluções
nestas
Vizinhanças
 Vizinhança “rotação de jogos” (cadeia de
ejeção):
• Forçar um jogo para determinada rodada: adicionar
uma nova aresta a um 1-fator da 1-fatoração
associada à tabela atual.
• Utilizar uma cadeia de ejeção para recuperar uma
1-fatoração.
Novembro 2004
Futebol e Otimização
OR in Sports 48/75
Vizinhanças
2
1
5
2
4
3
6
Forçar jogo 1vs. 3 na rodada (fator) 2.
Novembro 2004
Futebol e Otimização
OR in Sports 49/75
Vizinhanças
2
1
5
2
4
3
6
Times 1 e 3 agora jogam duas vezes nesta rodada.
Novembro 2004
Futebol e Otimização
OR in Sports 50/75
Vizinhanças
2
1
5
2
4
3
6
Eliminar os outros jogos dos times 1 e 3 nesta rodada.
Novembro 2004
Futebol e Otimização
OR in Sports 51/75
Vizinhanças
2
1
5
2
4
3
6
Forçar os antigos oponentes dos times 1 e 3 a jogarem entre si
nesta rodada: novo jogo 2 vs. 4 nesta rodada.
Novembro 2004
Futebol e Otimização
OR in Sports 52/75
Vizinhanças
4
1
5
2
4
3
6
Considerar a rodada onde estava o jogo 2 vs. 4.
Novembro 2004
Futebol e Otimização
OR in Sports 53/75
Vizinhanças
4
1
5
2
4
3
6
Forçar o jogo 1 vs. 4 (retirado da rodada 2) a ser jogado nesta rod
Novembro 2004
Futebol e Otimização
OR in Sports 54/75
Vizinhanças
4
1
5
2
4
3
6
Retirar os jogos 2 vs. 4 (colocado na rodada 2) e 1 vs. 5
(já que o time 1 não pode jogar duas vezes).
Novembro 2004
Futebol e Otimização
OR in Sports 55/75
Vizinhanças
4
1
5
2
4
3
6
Forçar o jogo 2 vs. 5 para ser jogado nesta rodada.
Novembro 2004
Futebol e Otimização
OR in Sports 56/75
Vizinhanças
1
1
5
2
4
3
6
Considerar a rodada em que o jogo 2 vs. 5 estava programado.
Novembro 2004
Futebol e Otimização
OR in Sports 57/75
Vizinhanças
1
1
5
2
4
3
6
Forçar o jogo 1 vs. 5 (retirado da rodada 4)
a ser jogado nesta rodada.
Novembro 2004
Futebol e Otimização
OR in Sports 58/75
Vizinhanças
1
1
5
2
4
3
6
Eliminar os jogos 2 vs. 5 (colocado na rodada 4) e 1 vs. 6
(já que o time 1 não pode ser jogado duas vezes).
Novembro 2004
Futebol e Otimização
OR in Sports 59/75
Vizinhanças
1
1
5
2
4
3
6
Forçar o jogo 2 vs. 6 a ser jogado nesta rodada.
Novembro 2004
Futebol e Otimização
OR in Sports 60/75
Vizinhanças
5
1
5
2
4
3
6
Considerar a rodada onde o jogo 2 vs. 6 estava programado.
Novembro 2004
Futebol e Otimização
OR in Sports 61/75
Vizinhanças
5
1
5
2
4
3
6
Forçar o jogo 1 vs. 6 (eliminado da rodada 1)
a ser jogado nesta rodada.
Novembro 2004
Futebol e Otimização
OR in Sports 62/75
Vizinhanças
5
1
5
2
4
3
6
Eliminar os jogos 2 vs. 6 (colocado na rodada 1) e 1 vs. 3
(já que o time 1 nãopode jogar duas vezes e este jogo foi colocad
na rodada 2 no início da cadeia de ejeção).
Novembro 2004
Futebol e Otimização
OR in Sports 63/75
Vizinhanças
5
1
5
2
4
3
6
Finalmente, forçar o jogo 2 vs. 3 (eliminado da rodada 2
no início da cadeia de ejeção) a ser jogado nesta rodada.
Novembro 2004
Futebol e Otimização
OR in Sports 64/75
Resultados
 Resultados para Campeonato Brasileiro:
redução de 50%
 Tese de doutorado de S. Urrutia (PUC-Rio,
2005)
 Publicações:
Ribeiro & Urrutia, “Heuristics for the mirrored
TTP”, European Journal of OR, 2005.
Ribeiro & Urrutia, “Min travels max breaks”,
Electronic Notes in Discrete Mathematics,
2005.
Novembro 2004
Futebol e Otimização
OR in Sports 65/75
Aplicação 1: CB futebol
 TTP é o modelo apropriado e aplicado a
diversos torneios americanos (NHL, MLB, NBA)
...
 ... mas não para torneios brasileiros!
• MLB: uma equipe pode fazer até 140 jogos em seis
meses.
• Campeonato brasileiro: poucos jogos no meio da
semana, uma equipe normalmente retorna à sua
base após cada jogo e não há viagens a otimizar.
 Qual é o problema de interesse?
Novembro 2004
Futebol e Otimização
OR in Sports 66/75
Aplicação 1: CB futebol
 Critérios técnicos, por exemplo:
• Minimizar as seqüências consecutivas de jogos
dentro e fora de casa para uma mesma equipe
(equilíbrio).
• Uma equipe que joga a primeira rodada fora, deve
jogar a última em casa (e vice-versa).
• Nenhum time grande aceita fazer um clássico
regional nas quatro últimas rodadas.
• Disponibilidade de estádios (exemplo: última
rodada).
• Possibilidade de combinar
viagens apenasORnas
Novembro 2004
Futebol e Otimização
in Sports 67/75
Aplicação 1: CB futebol
 Os critérios difíceis e mais importantes
economicamente são os televisivos, por
exemplo:
• TV Globo é o grande investidor no CB e adianta
recursos vultosos para o Clube dos 13.
• Em cada domingo, deve haver um jogo de um time
grande do Rio (São Paulo) fora do Rio (São Paulo),
contra um dos outros doze times considerados
grandes.
• Capacidade de transmissão dos canais PPV.
• Disponibilidade de Futebol
unidades
de transmissão
Novembro 2004
e Otimização
OR in Sports 68/75
Aplicação 1: CB futebol
 Também há critérios de segurança, por
exemplo:
• Padrões complementares para equipes da mesma
cidade.
 Problema multicritério: minimizar o número de
 Outro problema: campeonato da 2a. divisão
requisitos técnicos e televisivos violados.
• Futebol Brasileiro Associados
• Todas as passagens são pagas pelos
organizadores.
• Uma mesma equipe joga mais de uma vez por
semana.
Novembro 2004
Futebol e Otimização
OR in Sports 69/75
Aplicação 2: CB basquete
 Campeonato brasileiro de basquete: CBB tem
poucos recursos e paga todas as passagens dos
16 clubes.
 Escassez de recursos libera muitas restrições e
justifica a minimização das viagens: rodadas nãosincronizadas, longas seqüências dentro/fora de
casa, até 4 jogos por semana.
 Televisão: um jogo às 6as feiras e dois aos
domingos.
Novembro
Tese2004de mestrado de
Marcus Pavan (UFF)
Futebol e Otimização
OR in Sports 70/75
Logística aplicada a esportes
Juízes
Motivação: aplicação real
 Ligas (amadoras) regionais de esportes nos
Estados Unidos (beisebol, basquete, futebol):
centenas de jogos em cada fim de semana em
diferentes categorias
• boys, girls
• faixas etárias: 8-10, 10-12, 12-14, 14-16, 16-18
 Em uma única liga regional na Califórnia pode
haver até 500 jogos de futebol em um único fim
de semana, a serem arbitrados por mais de 600
juízes.
 Atribuir juízes a jogos, de modo a satisfazer
Novembro 2004
Futebol e Otimização
OR in Sports 72/75
critérios pessoais e técnicos.
Descrição
 Restrições:
• Podem ser requisitados de 0 a 3 juízes para cada
jogo.
• Cada jogo requer juízes com níveis diferentes de
certificação.
• Um juiz não pode ser atribuído a um jogo no qual
participa como jogador.
• Conflitos de horários entre os jogos.
• Associações entre juízes: há grupos de juízes que
exigem e grupos de juízes que desejam serem
escalados para os mesmos jogos (familiares,
caronas).
Novembro 2004
Futebol e Otimização
OR in Sports 73/75
• Número de jogos que cada juiz deseja arbitrar no fim
Descrição
 Otimização: problema multicritério
• Diferença ente o número almejado e o número de
jogos para os quais cada juiz é escalado.
• Tempos de deslocamento entre diferentes jogos.
 Portabilidade: o software desenvolvido deve ser
aplicável a três esportes.
 Projeto em desenvolvimento.
 Tese de doutorado de Alexandre Duarte (PUCRio).
Novembro 2004
Futebol e Otimização
OR in Sports 74/75
Observações finais
 Repercussão das atividades do grupo de
pesquisa
 Motivação para pós-graduandos…
 … e muitas possibilidades para quem estiver
interessado em temas de tese de mestrado e
doutorado!
 Grupo de logística em esportes:
http://www.esportemax.org
 Transparências disponíveis em:
http://www.inf.puc-rio.br/~celso/talks.htm
2004
OR in Sports 75/75
Novembro
Artigos
disponíveisFutebol
em:e Otimização
Formulação
 Empates no número de pontos ganhos são
resolvidos em favor de times com mais
vitórias.
 Neste modelo, somar um valor muito
pequeno (neces-sariamente menor do que 1)
tao
p j  (3 de )pontos:
x

[1

(
x

x
)]
j número
ji
ij
ji
i j
i j


  0.01
 Usar, por exemplo,
.
Futebol e Otimização
OR in Sports 76/75
Novembro
Com2004um modelo similar,
calcular PQS(k):
Formulação
 Variantes:
• round-robin simples
• rodadas não sincronizadas
• múltiplos jogos entre cada par de equipes (mais
do que dois, variável)
• times da mesma cidade com padrões
complementares
• jogos pré-escalonados e restrições de TV
• disponibilidade de estádios
• minimizar custos de passagem e de
hospedagem, etc.
Novembro 2004
Futebol e Otimização
OR in Sports 77/75
Heurística GRASP + ILS
while .not.StoppingCriterion
S  GenerateRandomizedInitialSolution()
S,S  LocalSearch(S)
/* S best solution in
cycle */
repeat
/* S* best overall
solution */
S’  Perturbation(S,history)
S’  LocalSearch(S’)
S  AceptanceCriterion(S,S’,history)
S*  UpdateOverallBestSolution(S,S*)
S  UpdateCycleBestSolution(S,S)
Novembro
2004 ReinitializationCriterion
Futebol e Otimização
OR in Sports 78/75
until
Vizinhanças
 A cadeia de ejeção termina quando o jogo
forçado no início é removido da rodada onde
era jogado na tabela inicial:
• O comprimento da cadeia de ejeção é variável.
• A cadeia de ejeção é capaz de encontrar soluções
“escondidas” que não podem ser obtidas pelos
outros movimentos.
• Movimentos caros computacionalmente,
avaliados apenas esporadicamente.
 O uso de cadeias de ejeção é importante e
Novembro
2004
Futebol e Otimização
OR in Sports 79/75
efetivo!
Resultados
 Problemas-teste com até 20 equipes
 Resultados em um Pentium IV 2.0 MHz
 Heurística construtiva:
• Muito rápida: 1000 execuções (n=16) em 1
segundo
• Diversas ordens de magnitude mais rápida do
que as melhores heurísticas: melhores soluções
do que aquelas obtidas após diversos dias de
processamento por uma heurística de colônia de
formigas com backtracking e busca local.
Novembro 2004
Futebol e Otimização
OR in Sports 80/75
Resultados
 Metaheurística GRASP + ILS:
• Limite de tempo: 10 minutos
• Melhores soluções para diversos problemas da
literatura.
• Melhor heurística até então: simulated
annealing, cerca de 5 dias de processamento!
Novembro 2004
Futebol e Otimização
OR in Sports 81/75