Scheduler with Heuristics

[axelahmer]

Trying out a few small little experiments with heuristics. @ssardina

Investigating this first:

prelim results (2 threads, 240s) are its on-par, maybe a little worse:

run1 is baseline (no heuristics)

4factor is [4,factor] with the above

[axelahmer]

Also intrigued to test this idea:

% calc the number of time slots teams can play with one another
possible_matches(HomeTeam, AwayTeam, N) :- 
    team(HomeTeam), team(AwayTeam), HomeTeam!=AwayTeam,
    N = #count { Time : home(HomeTeam, Time), not forbidden(AwayTeam, Time), time(Time) }.

% prefer to schedule games that have less possible matches 
#heuristic schedule(HomeTeam, AwayTeam, _) : possible_matches(HomeTeam, AwayTeam, N), N<100. [100-N, factor]

[axelahmer]

managed to improve the mean performance using this heuristic:

% calc the number of time slots teams can play with one another
possible_matches(HomeTeam, AwayTeam, N) :- team(HomeTeam), team(AwayTeam), HomeTeam!=AwayTeam, N = #count { Time : home(HomeTeam, Time), not forbidden(AwayTeam, Time), time(Time) }.

% prefer to schedule games that have less possible matches 
#heuristic schedule(HomeTeam, AwayTeam, _) : possible_matches(HomeTeam, AwayTeam, N), N<20. [20-N@10, init]

Average performance relative to GUROBI (lower is better, 1.0 means equal to GUROBI):
run_name
GUROBI              1.000000
TABU                1.115104
poss_match20init    2.541821
run1                2.962599
4factor             3.558493

[ssardina]

very cool, how do you generate this and where do you have the results of gurbobi et al?

[axelahmer]

I'm storing all results in a results csv now. can select what runs i want to visulize from it using script i pushed most recently

-r lets you specify what runs you care about. Script has gurobi and tabu hardcoded.

python analyze.py -r 4factor run1 poss_match20init poss_match_300-N_init

results table looks something like this

You can name your runs by passing an argument to run_batch

I supress the nice schedule pretty print but you can enable it by passing --render

[axelahmer]

Important to pass --heuristic to solver or run_batch if you want to use domain heuristics too.

[ssardina]

BTW:

https://dl.acm.org/doi/pdf/10.1613/jair.1.14091

[axelahmer]

Wonderful. I saw a phd opportunity on the clingo forum yesterday from Klagenfurt! Thinking about applying funnily enough 🤔

[ssardina]

You would be very very good and they would love to have you I am sure! I am happy to be your reference if needed.

BTW, why don't you use just:

#heuristic schedule(HomeTeam, AwayTeam, _) : possible_matches(HomeTeam, AwayTeam, N).   [-N@10, init]

Why do you do 20-N?

[axelahmer]

Thanks @ssardina , going to read through that paper in my free time - seems long but interesting, it explains a lot really well, glad some people are trying to fix ASPs downfalls. A lot of these solutions to aid industrial problems help me with my yearly christmas optimization puzzles! You should do this year's one with me if you arent on holiday!! Rightly or wrongly I always use ASP.

Regarding PHD: I think I will apply. I'll definitely use you as a reference - thank you! 🙏 In general, I'm interested in how heuristics can be learnt for combinatorial optimization problems. This stuff is pretty interesting if you havent seen much of it: https://arxiv.org/abs/2402.14048

Regarding your question: I did both, but this version just showcases a way of preferencing teams that have a low amount of possible schedules up to some limit - after which there is no preferncial differnce.