Calendário de basquete da Atlantic Coast Conference de 1997-98 construído por programação inteira

As nove escolas da Atlantic Coast Conference disputam um duplo turno de nove semanas e 18 vagas a cada janeiro e fevereiro, e o basquete era a maior fonte de receita da liga: em 1995, a conferência e suas universidades arrecadaram mais de US$ 30 milhões com o esporte, quase tudo em direitos de TV e rádio mais bilheteria. Até 1996-97, o calendário era elaborado à mão no escritório da conferência. Depois que uma nona equipe (Florida State) entrou em 1991-92 e os pedidos de televisão se multiplicaram, uma tentativa de programação por restrições para 1996-97 ainda produziu um calendário com má separação entre reencontros e necessidades de TV não atendidas.

Para 1997-98, a ACC recorreu a George Nemhauser e Michael Trick. O sistema deles enumerou todos os padrões legais de temporada — 8 jogos em casa, 8 fora, 2 folgas ao longo de 18 vagas, no máximo dois jogos consecutivos em casa ou fora —, mantendo 38 dos 2.304 candidatos. Um programa inteiro montou conjuntos de nove padrões (17 conjuntos, menos de um minuto cada), e um segundo PI de cerca de 300 variáveis gerou todos os 826 calendários viáveis em menos de dez minutos, tudo em uma Sun SPARCstation 20 com CPLEX 4.0. Uma enumeração final de 24 horas das atribuições de equipes a padrões — aproximadamente 300 milhões de opções — deixou 17 calendários viáveis.

Esses foram reduzidos a três e submetidos; a ACC, consultando a ESPN e a Raycom, adotou um como o calendário oficial masculino, e um calendário feminino aceito veio do mesmo sistema. As exigências mais difíceis só surgiram no diálogo — a ESPN queria Duke-North Carolina na vaga 10 e no encerramento, o que exclui um calendário totalmente espelhado, e a Raycom tinha preferências elaboradas para fevereiro. Nemhauser e Trick creditam ao sistema a capacidade de resposta em um dia: a conferência podia examinar calendários reais e continuar refinando o que de fato precisava.

Enumerar padrões de casa/fora e depois escolher a temporada por programação inteira

Dividir a temporada primeiro em um padrão C/F/D (casa/fora/descanso) separa o que é o ano de uma equipe de qual adversário ela enfrenta, transformando um problema enorme em três pequenos.

A enumeração era barata neste tamanho — 2.304 padrões candidatos, dos quais 38 eram legais —, enquanto a teoria de projetos combinatórios conseguia caracterizar apenas alguns calendários derivados à mão.

Adiar a atribuição das equipes reais aos padrões até o final permitiu que a etapa do calendário ignorasse preferências específicas de cada escola, mantendo os programas inteiros pequenos e rápidos.

A restrição vinculante não era a elegância algorítmica, mas a velocidade de resposta: a ACC continuava acrescentando exigências tardias, e só um sistema rápido em um dia poderia absorvê-las.

Quando as partes interessadas não conseguem declarar suas exigências de antemão, calendários candidatos rápidos ensinam a elas o que de fato precisam. Enumeração mais otimização pronta para uso supera esperar por métodos elegantes.

A estrutura padrão-calendário-atribuição tornou-se o modelo padrão para o agendamento de esportes em turno duplo na literatura de Pesquisa Operacional. O episódio permaneceu como referência viva: um acompanhamento de 2001 na Operations Research resolveu novamente a mesma instância de 1997-98 com programação por restrições de domínio finito e relatou uma aceleração dramática em relação à enumeração mais programação inteira. A lição mais profunda — a de que a geração rápida de calendários é uma ferramenta de negociação entre agendadores, conferências e emissoras — tem moldado projetos de agendamento de ligas desde então.