Novembro 2004 Futebol e Otimização OR in Sports 2/75
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
Atribuição de juízes
Heurísticas e paralelismo para problemas de
otimização e de bioinformática
Grupo de pesquisa (Diretório CNPq)
Novembro 2004 Futebol e Otimização OR in Sports 4/75
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 Implementações em grids e clusters (Laboratório de
Paralelismo: cluster de 64 processadores conectados por um switch rápido)
Novembro 2004 Futebol e Otimização OR in Sports 5/75
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 • Projeto de redes com funções de custo em escada • Síntese de redes com custos de conexão e de
instalação
Novembro 2004 Futebol e Otimização OR in Sports 6/75
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 8/75
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 • Campeão? Classificação para a Libertadores?
Rebaixamento? Aplicação motivadora, problema NP-completo!
Motivação
Novembro 2004 Futebol e Otimização OR in Sports 9/75
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?
O problema se complica se 24 equipes participam do campeonato!
Flamengo 37
Cruzeiro 37
Bahia 36
4 pontos!
Novembro 2004 Futebol e Otimização OR in Sports 10/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: Libertadores: p = 4 Rebaixamento: p = 20
Novembro 2004 Futebol e Otimização OR in Sports 11/75
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: quantos pontos um time deve fazer para ter alguma chance de classificar-se nas p primeiras posições? PQS(k)
Novembro 2004 Futebol e Otimização OR in Sports 12/75
contrário caso
) time do frente à está não time o (se se
,0
,1 jktty kjj
Formulação
contrário caso
time o derrota time o se
,0
,1 jixij
jp j time pelo acumulados já pontos
torneio do final ao time pelo ganhos pontos jt j
Novembro 2004 Futebol e Otimização OR in Sports 13/75
Formulação
,...,1 }1,0{
disputadoser a ),( jogo ;,...,1;,...,1 }1,0{
,...,1 )1(
,...,1 )(1.3
disputadoser a ),( jogo ;,...,1;,...,1 1
:a sujeito
máximo1)(
njy
jinjnix
py
njyMtt
njxxxpt
jinjnixx
tkGQS
j
ij
kj j
jjk
ji ji jiijjijj
jiij
k
tk > tj yj = 0
k = time sendo considerado
Novembro 2004 Futebol e Otimização OR in Sports 14/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.
Quando o time k está “matematicamente eliminado”?O time k está matematicamente eliminado se seu problema da classificação possível é inviável.
Novembro 2004 Futebol e Otimização OR in Sports 15/75
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:
http://www.futmax.org Rebaixamento?
FUTMAX na rede e na imprensa
Novembro 2004 Futebol e Otimização OR in Sports 16/75
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)
Programa Redação SPORTV ao vivo (8/Nov/2004)
FUTMAX na rede e na imprensa
Novembro 2004 Futebol e Otimização OR in Sports 18/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 19/75
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.
De novo, FUTMAX mostrou que não era verdade!
Resultados
Novembro 2004 Futebol e Otimização OR in Sports 21/75
Resultados
FUTMAX pode ser usado para acompanhar o desempenho de cada time:
Pontos possíveis
Pontos para classificação garantida
Pontos para classificaçãopossível
Pontos acumulados
FLUMINENSE
Novembro 2004 Futebol e Otimização OR in Sports 22/75
Resultados
Spin-offs: seguido pelo HockeyPlex project (mesma idéia para a National Hockey League, USA)
Tese de doutorado de Sebastián Urrutia (PUC-Rio, 2005)
Repercussão e motivação Publicações:Ribeiro & Urrutia, “OR on the ball”, OR/MS Today,
2004.Ribeiro & Urrutia, “IP applied to playoff elimination”,
International Transactions in OR, 2005.
Novembro 2004 Futebol e Otimização OR in Sports 24/75
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!
Motivação
Novembro 2004 Futebol e Otimização OR in Sports 25/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 26/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,
invertendo-se 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 todos os times.
Novembro 2004 Futebol e Otimização OR in Sports 27/75
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 28/75
4 3
2
1
5
6
Formulação
Exemplo: 1-fatoração de K6
Novembro 2004 Futebol e Otimização OR in Sports 29/75
4 3
2
1
5
6
1
Formulação
Exemplo: 1-fatoração de K6
Novembro 2004 Futebol e Otimização OR in Sports 30/75
4 3
2
1
5
6
2
Formulação
Exemplo: 1-fatoração de K6
Novembro 2004 Futebol e Otimização OR in Sports 31/75
4 3
2
1
5
6
3
Formulação
Exemplo: 1-fatoração de K6
Novembro 2004 Futebol e Otimização OR in Sports 32/75
4 3
2
1
5
6
4
Formulação
Exemplo: 1-fatoração de K6
Novembro 2004 Futebol e Otimização OR in Sports 33/75
4 3
2
1
5
6
5
Formulação
Exemplo: 1-fatoração de K6
Novembro 2004 Futebol e Otimização OR in Sports 34/75
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).
Formulação
Novembro 2004 Futebol e Otimização OR in Sports 35/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.• “Método do polígono”
Novembro 2004 Futebol e Otimização OR in Sports 36/75
4 3
2
1
5
6
Exemplo: “método do polígono” para n=6
1a rodada
Heurística construtiva
Novembro 2004 Futebol e Otimização OR in Sports 37/75
3 2
1
5
4
6
Exemplo: “método do polígono” para n=6
2a rodada
Heurística construtiva
Novembro 2004 Futebol e Otimização OR in Sports 38/75
2 1
5
4
3
6
Exemplo: “método do polígono” para n=6
3a rodada
Heurística construtiva
Novembro 2004 Futebol e Otimização OR in Sports 39/75
1 5
4
3
2
6
Exemplo: “método do polígono” para n=6
4a rodada
Heurística construtiva
Novembro 2004 Futebol e Otimização OR in Sports 40/75
5 4
3
2
1
6
Exemplo: “método do polígono” para n=6
5a rodada
Heurística construtiva
Novembro 2004 Futebol e Otimização OR in Sports 41/75
Heurística construtiva
Times abstratos (n=6)
Rodada
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 42/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 times abstratos com valores elevados na matriz com os números de jogos consecutivos.
Novembro 2004 Futebol e Otimização OR in Sports 43/75
Heurística construtiva
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
Novembro 2004 Futebol e Otimização OR in Sports 44/75
Heurística construtiva
Times reais (n=6)
Rodada
FLU SAN FLA GRE PAL PAY
1/6 PAY PAL GRE FLA SAN FLU
2/7 GRE FLA SAN FLU PAY PAL
3/8 SAN FLU PAL PAY FLA GRE
4/9 PAL GRE PAY SAN FLU FLA
5/10 FLA PAY FLU PAL GRE SAN
Novembro 2004 Futebol e Otimização OR in Sports 45/75
Heurística construtiva
Etapa 3: atribuir estádios aos jogos (mandos de campo)
• 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.
Novembro 2004 Futebol e Otimização OR in Sports 46/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 47/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 n8, nem sempre é possível).
Gerar e avaliar soluções nestas vizinhanças é rápido, mas nem sempre leva a boas soluções “escondidas”.
Novembro 2004 Futebol e Otimização OR in Sports 48/75
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 49/75
Vizinhanças
4 3
2
1
5
6
2
Forçar jogo 1vs. 3 na rodada (fator) 2.
Novembro 2004 Futebol e Otimização OR in Sports 50/75
4 3
2
1
5
6
2
Vizinhanças
Times 1 e 3 agora jogam duas vezes nesta rodada.
Novembro 2004 Futebol e Otimização OR in Sports 51/75
4 3
2
1
5
6
2
Vizinhanças
Eliminar os outros jogos dos times 1 e 3 nesta rodada.
Novembro 2004 Futebol e Otimização OR in Sports 52/75
4 3
2
1
5
6
2
Vizinhanças
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 53/75
4 3
2
1
5
6
4
Vizinhanças
Considerar a rodada onde estava o jogo 2 vs. 4.
Novembro 2004 Futebol e Otimização OR in Sports 54/75
Vizinhanças
4 3
2
1
5
6
4
Forçar o jogo 1 vs. 4 (retirado da rodada 2) a ser jogado nesta rodada.
Novembro 2004 Futebol e Otimização OR in Sports 55/75
Vizinhanças
4 3
2
1
5
6
4
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 56/75
Vizinhanças
4 3
2
1
5
6
4
Forçar o jogo 2 vs. 5 para ser jogado nesta rodada.
Novembro 2004 Futebol e Otimização OR in Sports 57/75
Vizinhanças
4 3
2
1
5
6
1
Considerar a rodada em que o jogo 2 vs. 5 estava programado.
Novembro 2004 Futebol e Otimização OR in Sports 58/75
Vizinhanças
4 3
2
1
5
6
1
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 59/75
Vizinhanças
4 3
2
1
5
6
1
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 60/75
Vizinhanças
4 3
2
1
5
6
1
Forçar o jogo 2 vs. 6 a ser jogado nesta rodada.
Novembro 2004 Futebol e Otimização OR in Sports 61/75
Vizinhanças
4 3
2
1
5
6
5
Considerar a rodada onde o jogo 2 vs. 6 estava programado.
Novembro 2004 Futebol e Otimização OR in Sports 62/75
Vizinhanças
4 3
2
1
5
6
5
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 63/75
Vizinhanças
4 3
2
1
5
6
5
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 colocado na rodada 2 no início da cadeia de ejeção).
Novembro 2004 Futebol e Otimização OR in Sports 64/75
Vizinhanças
4 3
2
1
5
6
5
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 65/75
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.Urrutia & Ribeiro, “Max breaks applied to the
mirrored TTP”, Discrete Applied Mathematics, 2005.
Resultados
Novembro 2004 Futebol e Otimização OR in Sports 66/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 67/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 apenas nas
rodadas de meio de semana (serão 14 ao longo do campeonato em 2005).
Novembro 2004 Futebol e Otimização OR in Sports 68/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 unidades de transmissão
(“uplinks”).
Novembro 2004 Futebol e Otimização OR in Sports 69/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
requisitos técnicos e televisivos violados. Outro problema: campeonato da 2a. divisão
• Futebol Brasileiro Associados• Todas as passagens são pagas pelos organizadores.• Uma mesma equipe joga mais de uma vez por semana.• Neste contexto, minimizar as viagens é importante!
Novembro 2004 Futebol e Otimização OR in Sports 70/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ão-sincronizadas, longas seqüências dentro/fora de casa, até 4 jogos por semana.
Televisão: um jogo às 6as feiras e dois aos domingos. Tese de mestrado de Marcus Pavan (UFF) Resultados preliminares: reduções de distâncias de
25% Tabela da Nova Liga (Oscar) para 2005
Novembro 2004 Futebol e Otimização OR in Sports 72/75
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 critérios pessoais e técnicos.
Novembro 2004 Futebol e Otimização OR in Sports 73/75
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).
• Número de jogos que cada juiz deseja arbitrar no fim de semana.
• Juízes com restrições de deslocamento (não podem viajar).
Novembro 2004 Futebol e Otimização OR in Sports 74/75
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
(PUC-Rio).
Novembro 2004 Futebol e Otimização OR in Sports 75/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
Artigos disponíveis em:http://www.inf.puc-rio.br/~celso/publicacoes.htm
Novembro 2004 Futebol e Otimização OR in Sports 76/75
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) ao número de pontos:
Usar, por exemplo, . Com um modelo similar, calcular PQS(k):
número mínimo de pontos para classificação possível
(3 ) [1 ( )]j j ji ij jii j i jt p x x x
0.01
Novembro 2004 Futebol e Otimização OR in Sports 77/75
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 78/75
while .not.StoppingCriterionS 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)
until ReinitializationCriterionend
Heurística GRASP + ILS
Novembro 2004 Futebol e Otimização OR in Sports 79/75
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 efetivo!
Novembro 2004 Futebol e Otimização OR in Sports 80/75
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.