🔢 matemática

Centralized Round-Robin Tournament Scheduling with a Flexible Number of Matches per Round

Este artigo aborda o problema NP-difícil de minimizar a distância total de viagem em torneios de rodízio único centralizados com contagens de partidas flexíveis por rodada, estabelecendo resultados de complexidade teórica e casos resolvíveis em tempo polinomial, ao mesmo tempo em que propõe uma heurística de busca local iterada altamente eficaz que supera a programação inteira mista em instâncias de larga escala.

Autores originais: Hikaru Anai, Yunjian Cao, Wei Wu

Publicado 2026-10-15

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Hikaru Anai, Yunjian Cao, Wei Wu

Artigo original sob licença CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um mundo onde a logística de uma liga esportiva não é apenas sobre quem joga contra quem, mas sobre a própria jornada. No campo da pesquisa operacional, uma área dedicada a fazer sistemas complexos funcionarem com eficiência, pesquisadores frequentemente enfrentam o quebra-cabeça do escalonamento. Uma versão clássica desse quebra-cabeça é o torneio de todos contra todos (round-robin), um formato onde cada equipe joga contra todas as outras exatamente uma vez. Tradicionalmente, esses torneios são rígidos: uma rodada é um bloco de tempo fixo onde o número máximo de jogos possíveis acontece simultaneamente, como uma casa cheia em um teatro onde todos os assentos estão ocupados. O desafio geralmente reside em decidir a ordem dessas rodadas ou onde realizá-las para economizar tempo e dinheiro. Mas no mundo real, particularmente em ligas amadoras regionais e esportes escolares no Japão, as regras costumam ser mais fluidas. Os organizadores podem não ter campos suficientes para que todos joguem ao mesmo tempo, ou podem querer limitar o deslocamento de um grupo específico de equipes em um determinado dia. Essa flexibilidade significa que uma única rodada pode conter apenas um jogo, ou dez, dependendo do que faça sentido para aquele dia. A questão passa a ser: como você organiza uma temporada onde o número de jogos por dia pode mudar, e cada dia tem um único local sede, para manter a distância total percorrida por todas as equipes o mais baixa possível?

Este é o problema específico que uma equipe de pesquisadores da Universidade de Shizuoka e da Universidade de Seikei se propôs a resolver. Eles focaram em um cenário onde um organizador central escolhe um local para um dia inteiro e, em seguida, decide quantos jogos agendar ali, garantindo que nenhuma equipe jogue duas vezes no mesmo dia. O objetivo deles era simples, mas difícil de alcançar: minimizar a milhagem total percorrida por todas as equipes para chegar aos seus jogos. Para entender a dificuldade, deve-se perceber que cada vez que você divide um grupo de jogos em um novo dia, você pode conseguir escolher um local mais próximo dessas equipes específicas, mas também utiliza um dos dias limitados disponíveis na temporada. É um delicado equilíbrio entre manter o cronograma compacto e manter o deslocamento curto.

Os pesquisadores primeiro fizeram uma pergunta fundamental: este problema é solucionável por um computador em um tempo razoável ou é complexo demais para que se encontre a resposta perfeita? Eles provaram que, para o caso geral, o problema é computacionalmente intratável. Em termos simples, isso significa que, à medida que o número de equipes cresce, o tempo necessário para encontrar o melhor cronograma absoluto explode, tornando impossível até mesmo para os computadores mais poderosos resolvê-lo perfeitamente para grandes grupos. Eles demonstraram isso mostrando que, mesmo se simplificassem os custos de viagem para apenas três valores possíveis, a lógica subjacente permanece complexa demais para ser resolvida eficientemente. Essa descoberta é crucial porque diz aos organizadores de torneios que eles não podem confiar em uma fórmula simples para obter o cronograma perfeito para uma grande liga; eles precisarão de atalhos inteligentes.

No entanto, o estudo não parou na prova da dificuldade. A equipe descobriu que, sob certas condições específicas, o problema torna-se muito mais fácil. Se o número de dias disponíveis para o torneio for exatamente o mínimo necessário para acomodar todos os jogos, a solução é direta e pode ser encontrada rapidamente. Eles também identificaram um caso especial envolvendo apenas dois locais possíveis. Nesse cenário, desenvolveram um método baseado na estrutura matemática das preferências das equipes para determinar o melhor cronograma instantaneamente. Isso fornece uma ferramenta poderosa para ligas menores ou aquelas com opções de locais muito limitadas, permitindo encontrar o cronograma perfeito sem a necessidade de um supercomputador.

Para as situações mais comuns e difíceis, envolvendo muitas equipes e muitos dias, os pesquisadores projetaram uma estratégia de busca sofisticada chamada busca local iterada. Pense nisso como uma maneira metódica de explorar um vasto cenário de cronogramas possíveis. O processo começa com um cronograma decente e depois tenta melhorá-lo repetidamente através de mudanças pequenas e estratégicas. Essas mudanças incluem fundir dois dias de jogos em um só e depois dividi-los novamente de forma diferente, ou mover um único jogo de um dia para outro para resolver um conflito. O algoritmo é projetado para escapar de armadilhas locais — situações onde um cronograma parece bom, mas está longe de ser o melhor possível — ao ocasionalmente realizar uma mudança maior e mais disruptiva para agitar as coisas e explorar novas possibilidades.

Quando os pesquisadores testaram seus métodos em sessenta e quatro cenários diferentes, variando de oito a sessenta e quatro equipes, os resultados foram impressionantes. Para torneios menores com menos de trinta e duas equipes, seus modelos matemáticos conseguiam encontrar o cronograma perfeito e provar que era o melhor possível. Para os torneios maiores e mais complexos, os modelos matemáticos exatos frequentemente enfrentavam dificuldades, ficando sem memória ou falhando em encontrar uma solução dentro do limite de tempo. Em contraste, a estratégia de busca encontrou consistentemente cronogramas de alta qualidade. Nos problemas de médio porte, produziu soluções que estavam a uma fração de percentual do melhor teórico. Mesmo nos maiores problemas, onde os modelos exatos falharam, a estratégia de busca forneceu cronogramas viáveis que eram muito superiores ao que as abordagens matemáticas padrão conseguiam gerenciar.

O estudo também revelou insights interessantes sobre como a flexibilidade do cronograma afeta o resultado. Ter mais dias disponíveis para jogar partidas geralmente permite melhores economias de viagem, mas o benefício diminui após um certo ponto. Da mesma forma, ter mais locais para escolher ajuda a reduzir a distância de viagem, mas também torna o quebra-cabeça do escalonamento mais difícil de resolver. Os pesquisadores descobriram que, ao dividir os jogos por mais dias, os organizadores podem agrupar equipes que moram perto umas das outras e enviá-las para um local próximo, reduzindo significativamente o deslocamento. Isso confirma que a flexibilidade de variar o número de jogos por dia não é apenas uma conveniência logística, mas uma poderosa alavanca para reduzir custos e esforço.

Em última análise, este trabalho oferece um conjunto de ferramentas completo para organizar esses torneios flexíveis. Oferece uma prova da dificuldade do problema, um conjunto de soluções exatas para casos especiais e uma heurística robusta e rápida para os cenários do mundo real que mais importam. Ao combinar teoria matemática profunda com design de algoritmos práticos, os pesquisadores deram aos organizadores esportivos uma maneira de navegar pelos complexos compromissos entre tempo, espaço e deslocamento, garantindo que o foco permaneça no jogo, e não na jornada.

Resumo Técnico: Escalonamento de Torneios Round-Robin Centralizados com Número Flexível de Partidas por Rodada

Definição do Problema

O artigo aborda o Problema de Escalonamento de Torneio Round-Robin Centralizado com Número Flexível de Partidas por Rodada (CRRTSP-FMR). Este problema surge no contexto de esportes amadores regionais e ligas de clubes escolares no Japão, onde restrições operacionais frequentemente ditam que todas as partidas dentro de uma rodada específica (período de tempo) devem ser realizadas em um único local comum.

Ao contrário do escalonamento tradicional de round-robin, onde cada rodada possui um número fixo máximo de confrontos (determinado pelo número de equipes), o CRRTSP-FMR permite que o número de partidas por rodada seja uma variável de decisão. O escalonador deve:

Atribuir cada par de $n$ equipes para jogar exatamente uma vez.
Particionar essas partidas em no máximo $q$ rodadas (onde $q \ge \rho(n)$ , o número mínimo teórico de rodadas).
Atribuir um local comum único para cada rodada ativa.
Garantir que cada equipe jogue no máximo uma vez por rodada.

O objetivo é minimizar a distância total de viagem de todas as equipes para os locais atribuídos. A flexibilidade no número de partidas por rodada introduz um compromisso (trade-off): dividir as rodadas permite ao escalonador selecionar locais mais próximos de subconjuntos específicos de equipes, mas aumenta o número total de rodadas necessárias, potencialmente conflitando com o limite superior $q$ .

Metodologia

1. Formulações Matemáticas

Os autores propõem dois modelos de Programação Inteira Mista (MIP):

Formulação Baseada em Índices de Tempo: Indexa explicitamente as rodadas candidatas $k \in \{1, \dots, q\}$ . Utiliza variáveis binárias para a atribuição de partida-rodada e de local-rodada. Para lidar com a simetria (onde a ordem das rodadas não afeta o custo), os autores introduzem restrições de quebra de simetria que impõem uma ordenação canônica baseada no menor índice de partida lexicográfica em cada rodada.
Formulação Baseada em Atribuição: Trata as partidas como tarefas (jobs) e os "pares de uso de local" $(j, k)$ como máquinas. Esta formulação atribui diretamente as partidas a usos específicos de locais. Ela também incorpora restrições de quebra de simetria para ordenar os usos de cada local com base no menor índice de partida atribuído a eles. Os autores argumentam que esta formulação oferece uma relaxação de Programação Linear (LP) mais forte devido à sua estrutura de empacotamento (packing).

2. Análise de Complexidade

NP-Completude: A versão de decisão do CRRTSP-FMR é provada como fortemente NP-completa, mesmo quando os custos de viagem são restritos ao conjunto $\{0, 1, 3\}$ . A prova utiliza uma redução do problema de coloração de 3 arestas de grafos cúbicos.
Casos Solúveis em Tempo Polinomial:
- Número Mínimo de Rodadas ( $q = \rho(n)$ ): Se o número de rodadas for igual ao mínimo teórico, o problema é solucionável em tempo polinomial. A estratégia ótima envolve atribuir todas as rodadas ao único local que minimize a viagem total das equipes.
- Atingibilidade do Limite Inferior: Os autores definem um "limite inferior de partida independente" ( $Z_{LB}$ ) onde cada partida é jogada em seu local mais barato possível. Eles provam que, se o limite de rodadas $q$ for maior ou igual à soma dos índices cromáticos dos grafos formados pelas partidas atribuídas a cada local, $Z_{LB}$ é atingível.
- Caso de Dois Locais ( $m=2$ ): Para dois locais, o problema reduz-se à análise de dois grafos limiar (threshold graphs) complementares. Os autores desenvolvem um teste exato de tempo polinomial ( $O(n \log n)$ ) para determinar se o limite inferior é atingível, computando os índices cromáticos desses grafos limiar.

3. Abordagem Heurística (Busca Local Iterada)

Para instâncias maiores onde os métodos exatos falham, os autores propõem uma heurística de Busca Local Iterada (ILS):

Solução Inicial: Gerada via dois métodos: (1) 1-fatoração com divisão gananciosa (greedy splitting), e (2) Coloração de arestas construtiva (algoritmo Misra–Gries) seguida de empacotamento de cadeias de Kempe para reduzir as rodadas para $q$ .
Vizinhanças de Busca Local: O algoritmo emprega uma estratégia de melhoria de melhor resultado (best-improvement) usando quatro vizinhanças:
1. Fusão-e-Divisão (Merge-and-Split): Funde duas rodadas e reparticiona as partidas em duas novas rodadas viáveis (modelado como uma 2-coloração de um grafo de conflito).
2. Cadeia de Expulsão Simples (Simple Ejection Chain): Move uma partida para uma nova rodada, expulsando uma partida conflitante, que é então movida para uma terceira rodada.
3. Cadeia de Expulsão de Profundidade Variável (VEC): Estende a cadeia simples com uma busca em feixe (beam-search) para explorar sequências de deslocamento mais longas.
4. Expulsar-e-Injetar (Eject-and-Inject): Remove uma rodada inteira, reatribui suas partidas e cria uma nova rodção a partir de uma partida semente para manter a contagem de rodadas.
Perturbação (Movimento de Choque/Kick Move): Para escapar de ótimos locais, é usado um movimento de choque híbrido adaptativo. Ele seleciona aleatoriamente um subconjunto de rodadas, agrupa suas partidas e as reconstrói. Se a reconstrução falhar, uma mudança de cadeia de Kempe generalizada é aplicada para permutar as partidas entre as rodadas selecionadas enquanto preserva a viabilidade.

Resultados Computacionais

Experimentos foram conduzidos em 64 instâncias de referência com $n \in \{8, 16, 32, 64\}$ equipes, $m \in \{2, 4, 8, 16\}$ locais e limites de rodadas $q$ variados.

Desempenho do MIP:
- A formulação Baseada em Atribuição (AB) superou significativamente a formulação Baseada em Índices de Tempo (TI) em instâncias pequenas e médias ( $n \le 32$ ), frequentemente provando a otimalidade.
- No entanto, ambas as formulações tiveram dificuldades com $n=64$ . O modelo AB frequentemente encontrava limitações de memória ou falhava em encontrar soluções viáveis, enquanto o modelo TI produzia grandes lacunas de otimalidade (optimality gaps).
- As restrições de quebra de simetria melhoraram o desempenho do TI para $n=32$ , mas degradaram o desempenho do AB em instâncias difíceis.
Desempenho do ILS:
- A heurística ILS encontrou soluções viáveis para todas as 64 instâncias.
- Para $n=8$ e $n=16$ , o ILS igualou os ótimos provados (gap de 0%).
- Para $n=32$ , a melhor configuração (usando Merge-and-Split, Simple Ejection Chain e Variable-Depth Ejection Chain) alcançou um gap de otimalidade médio de 0,15%.
- Para $n=64$ , o ILS manteve gaps moderados (média de ~10,5% em relação aos limites inferiores fracos dos modelos MIP), superando substancialmente as abordagens MIP que frequentemente falhavam em produzir soluções viáveis.
- A vizinhança "Eject-and-Inject" mostrou-se contraproducente sob os parâmetros testados, aumentando os gaps médios.

Significância e Alegações

O artigo alega quatro contribuições primárias:

Formulação do Problema: Introduz uma nova variante de escalonamento (CRRTSP-FMR) que relaxa a estrutura de rodadas fixas dos problemas clássicos de round-robin, refletindo restrições práticas.
Complexidade: Estabelece a dificuldade computacional intrínseca do problema (fortemente NP-completo), mesmo com estruturas de custo simplificadas.
Insights Estruturais: Identifica regimes solucionáveis em tempo polinomial e fornece um teste de otimalidade exato para o caso de dois locais usando a teoria de grafos limiar, caracterizando quando o limite inferior de partidas independentes é atingível.
Solução Algorítmica: Demonstra que uma heurística ILS personalizada, aproveitando construtos da teoria dos grafos como coloração de arestas e cadeias de Kempe, pode resolver eficazmente instâncias de larga escala onde abordagens MIP exatas falham.

Os autores concluem que a flexibilidade no número de partidas por rodada permite reduções significativas na distância de viagem ao possibilitar a seleção de locais mais próximos de subconjuntos específicos de equipes, desde que o limite de rodadas $q$ seja suficientemente alto. Eles observam que trabalhos futuros poderiam incorporar restrições adicionais do mundo real, como disponibilidade de locais, atribuição de árbitros e métricas de justiça (fairness).