Solving the ACC Basketball Scheduling Problem with Integer Local Search

The Atlantic Coast Conference (ACC) has recently played a Basketball season that was scheduled with a multi-stage approach using integer programming and explicit enumeration. Here, we approach the ACC problem in a monolithic 0-1 encoding. Using a domain-independent local search strategy for integer optimization, we show that the problem can be solved without resorting to a multi-stage approach. Despite the full set of requirements and preferences permits only few solutions, integer local search can find such high-quality schedules within reasonable time. We also introduce "minimal distortion mirroring", a scheme to handle preassigned team pairings that are in conflict with perfect mirroring without swapping entire time slots.

The problem was orignially described in a paper by Michael Trick and George Nemhauser and is available from Michael Trick's Home Page.

We have approached the problem using WSAT(OIP), an integer local search heuristic, given a monolithic 0-1 integer linear programming model. WSAT(OIP) was given the algebraic model specified with AMPL , a modelling language for mathematical programming. The final ACC Model incorporates all of the constraints and optimization criteria given in the paper by Nemhauser and Trick as hard constraints.

• The AMPL Model of ACC
• A solution found by WSAT(OIP)

• Problems in .mps format: acc-benchmarks-mps.tar.gz [tightness levels 0-6] (495K).
• Problems in .opb format: acc-benchmarks-opb.tar.gz [tightness levels 0-9] (310K).

The WSAT(OIP) solver including an AMPL interface is available here.