정수 계획법으로 구축한 애틀랜틱 코스트 컨퍼런스 1997-98 농구 일정

애틀랜틱 코스트 컨퍼런스의 9개 학교는 매년 1월과 2월에 9주, 18슬롯의 더블 라운드 로빈을 치르며, 농구는 리그의 최대 수익원이었다. 1995년 컨퍼런스와 그 대학들은 이 종목에서 3천만 달러 이상을 벌어들였고, 그 거의 전부가 TV 및 라디오 중계권과 입장 수입이었다. 1996-97 시즌까지 일정은 컨퍼런스 사무국에서 수작업으로 작성되었다. 1991-92 시즌에 9번째 팀(플로리다 주립대)이 합류하고 TV 요청이 늘어난 후, 1996-97을 위한 제약 프로그래밍 시도는 여전히 재대결 간격이 좋지 않고 TV 요구를 충족하지 못한 일정을 내놓았다.

1997-98을 위해 ACC는 조지 넴하우저와 마이클 트릭에게 의뢰했다. 그들의 시스템은 모든 합법적 시즌 패턴을 열거했다. 즉 18슬롯에 걸쳐 8번 홈, 8번 원정, 2번 휴식, 연속 홈 또는 원정은 최대 2회라는 조건으로 2,304개 후보 중 38개를 유지했다. 정수 계획법이 9개 패턴 집합을 구성했고(17개 집합, 각 1분 미만), 약 300개 변수의 두 번째 IP가 10분 미만에 826개의 실행 가능한 모든 시간표를 생성했으며, 모두 CPLEX 4.0을 갖춘 Sun SPARCstation 20에서 이루어졌다. 팀-패턴 배정에 대한 최종 24시간 열거(약 3억 개 옵션)는 17개의 실행 가능한 일정을 남겼다.

이들은 3개로 추려져 제출되었고, ESPN과 Raycom과 협의한 ACC는 그중 하나를 공식 남자 일정으로 채택했으며, 승인된 여자 일정도 같은 시스템에서 나왔다. 가장 어려운 요구 사항은 대화 과정에서만 드러났다. ESPN은 듀크-노스캐롤라이나 경기를 10번 슬롯과 마지막 경기에 원했는데, 이는 완전히 대칭된 일정을 배제하며, Raycom은 2월에 대한 정교한 선호를 가지고 있었다. 넴하우저와 트릭은 시스템의 하루 만의 처리 속도를 높이 평가했다. 컨퍼런스가 실제 일정을 보고 실제로 필요한 것을 계속 다듬을 수 있었기 때문이다.

홈/원정 패턴을 열거한 뒤 정수 계획법으로 시즌을 선택한다

시즌을 먼저 H/A/B 패턴으로 나누면 팀의 한 해가 어떤 모습인지를 어떤 상대와 만나는지와 분리하여, 하나의 거대한 문제를 세 개의 작은 문제로 바꾼다.

이 규모에서는 열거가 저렴했다. 2,304개의 후보 패턴 중 38개만 합법이었던 반면, 조합 설계 이론은 손으로 도출한 몇 개의 시간표만 특성화할 수 있었다.

실제 팀을 패턴에 배정하는 작업을 마지막까지 미룸으로써 시간표 단계는 학교별 선호를 무시할 수 있었고, 정수 계획법을 작고 빠르게 유지했다.

결정적 제약은 알고리즘의 우아함이 아니라 처리 속도였다. ACC는 늦은 요구 사항을 계속 추가했고, 하루 만에 처리하는 시스템만이 이를 흡수할 수 있었다.

이해관계자들이 요구 사항을 미리 진술하지 못할 때, 빠른 후보 일정은 그들이 실제로 무엇을 필요로 하는지 가르쳐 준다. 열거와 기성 최적화가 우아한 방법을 기다리는 것보다 낫다.

패턴-시간표-배정 프레임워크는 OR 문헌에서 라운드 로빈 스포츠 일정 수립의 표준 템플릿이 되었다. 이 사례는 계속 살아 있는 벤치마크로 남았다. 2001년 Operations Research 후속 논문은 유한 영역 제약 프로그래밍으로 동일한 1997-98 인스턴스를 다시 풀었고, 열거와 정수 계획법에 비해 극적인 속도 향상을 보고했다. 더 깊은 교훈, 즉 빠른 일정 생성이 일정 담당자, 컨퍼런스, 방송사 간의 협상 도구라는 점은 이후 리그 일정 수립 프로젝트에 영향을 주었다.