Solving the ACC Basketball Scheduling Problem with Integer Local
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
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
, 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
A set of problem instances of increasing constraint tightness
is available, ranging up to 1773x3479 variables x constraints.
The tightest instance permits only few solutions (87).
The WSAT(OIP) solver including an AMPL interface is
A recent paper describing an efficient constraint-programming approach
can be obtained from Martin Henz's
This page maintained by
Last Updated: October 7, 1998