Match scheduling research: ILP solvers
6 views
Skip to first unread message
Jeremy Morse
Feb 7, 2015, 12:11:40 PM2/7/15
to srobo...@googlegroups.com
Hi,
About a year ago [0] I wrote a match scheduler that used SAT solvers to
~exhaustively explore how teams could be scheduled, and produce one
where all teams had some minimum amount of time between matches (I think
it managed 25 mins gap for 2 arenas with 56 teams). Chris Baines and I
then explored some options for optimising that schedule by swapping
teams between arenas, and possibly back/forwards a match if that didn't
violate other constraints.
This led to a situation where the schedule was good at stopping pair of
teams facing each other very frequently. However, it also reduced the
range of teams faced by each other. Which isn't great, ideally all teams
should face all other teams, although that's probably infeasible.
There's a class of constraint solver out there called "Integer linear
programming" (ILP) solvers. These aim to take some kind of formula, and
then determine some optimal value for that formula (i.e., what's the
maximum value it can evaluate to). It might be possible to take our
existing schedule (see my past emails to srobo-devel), encode them as an
ILP formula that evaluates to the number of teams that each team faces,
then tell a solver to maximise that number.
The tricky part will be finding an encoding of this problem that doesn't
violate schedule constraints: i.e. that the schedule is made up of
discardable rounds, people have a minimum gap between matches, etc.
It might also be possible to re-formulate the original SAT problem into
ILP (they're both NP-complete). However, I'm not optimistic about that,
as the match schedule requires discrete assignments of teams to slots,
which is awkward in linear equations.
Anyhoo, if you have time to dive into a rabbit hole and see whether this
kind of optimization is feasible, that'd be great. Do let me know if
this is looked at though, or reply, to avoid effort duplication. I'm not
familiar with ILP, so can't provide a huge amount of support.
[0] http://comments.gmane.org/gmane.science.robotics.srobo.devel/718
--
Thanks,
Jeremy
About a year ago [0] I wrote a match scheduler that used SAT solvers to
~exhaustively explore how teams could be scheduled, and produce one
where all teams had some minimum amount of time between matches (I think
it managed 25 mins gap for 2 arenas with 56 teams). Chris Baines and I
then explored some options for optimising that schedule by swapping
teams between arenas, and possibly back/forwards a match if that didn't
violate other constraints.
This led to a situation where the schedule was good at stopping pair of
teams facing each other very frequently. However, it also reduced the
range of teams faced by each other. Which isn't great, ideally all teams
should face all other teams, although that's probably infeasible.
There's a class of constraint solver out there called "Integer linear
programming" (ILP) solvers. These aim to take some kind of formula, and
then determine some optimal value for that formula (i.e., what's the
maximum value it can evaluate to). It might be possible to take our
existing schedule (see my past emails to srobo-devel), encode them as an
ILP formula that evaluates to the number of teams that each team faces,
then tell a solver to maximise that number.
The tricky part will be finding an encoding of this problem that doesn't
violate schedule constraints: i.e. that the schedule is made up of
discardable rounds, people have a minimum gap between matches, etc.
It might also be possible to re-formulate the original SAT problem into
ILP (they're both NP-complete). However, I'm not optimistic about that,
as the match schedule requires discrete assignments of teams to slots,
which is awkward in linear equations.
Anyhoo, if you have time to dive into a rabbit hole and see whether this
kind of optimization is feasible, that'd be great. Do let me know if
this is looked at though, or reply, to avoid effort duplication. I'm not
familiar with ILP, so can't provide a huge amount of support.
[0] http://comments.gmane.org/gmane.science.robotics.srobo.devel/718
--
Thanks,
Jeremy
Reply all
Reply to author
Forward
0 new messages