If this model is going to be useful, it needs to be able to read data in a realistic format. That includes at least being able to take in data on when students are available, as datetime strings.
In the first model, I used a discretized time model, and the assignment variables were stored in a list of lists with equal length. One dimension for students, and one for time. This representation requires a lot of nested loops. Now, I set the challenge as being able to handle increased complexity with a more readable model. For this, I changed the representation from list of lists to a dict that maps student-time pairs to the assignment variables.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Old representation | |
# N is number of students | |
# T is number of time units | |
student2time2take = [[solver.IntVar(0, 1) for _ in range(T)] | |
for _ in range(N)] | |
# New representation | |
# available is a set((student, time)) | |
student_time2take = dict([(item, solver.IntVar(0, 1)) | |
for item in available]) |
This changes the way groups of variables are retrieved. For example:
The upside is particularly clear when we want to sum in the non-primary dimension, and won't have to do transposing. In this case, we also get out of retrieving by indexes.
In summary I was happy with the outcome of this change. The flat representation both handles a new feature, and makes for clearer operations. New results, using this data:
The lessons are 20 minutes.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Old representation | |
# take_times is list | |
def constrain_take_times(solver, student2time2take, take_times): | |
for student, time2take in enumerate(student2time2take): | |
solver.Add(solver.Sum(time2take) == num_take_times[student]) | |
# New representation | |
# take_times is dict | |
# This code is one line longer, but is more explicit | |
def constrain_take_times(solver, students, student_time2take,take_times): | |
for student in students: | |
takes = [take for (st_id, _), take in student_time2take.items() | |
if st_id == student] | |
solver.Add(solver.Sum(takes) == take_times[student]) |
The upside is particularly clear when we want to sum in the non-primary dimension, and won't have to do transposing. In this case, we also get out of retrieving by indexes.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Old representation | |
# D is number of days | |
# T_D is time units per day | |
def get_total_workdays(solver, student2time2take, D, T_D): | |
works_days = [] | |
time2student2take = list(transpose(student2time2take)) | |
for d in range(D): | |
student2take = time2student2take[d*T_D:(d+1)*T_D] | |
takes = flatten_simple(student2take) | |
works_day = max_var(solver, takes, lb=0, ub=1) | |
works_days.append(works_day) | |
return works_days | |
# New representation | |
# times is set of times | |
# This code is unbothered with the order of the keys | |
def get_day2works(solver, times, student_time2take): | |
day2works = {} | |
for day in equivalence_partition(times, lambda x: x.date()): | |
date = next(iter(day)).date() | |
takes = [take for (_, t), take in student_time2take.items() | |
if t in day] | |
works = max_var(solver, takes, lb=0, ub=1) | |
day2works[date] = works | |
return day2works |
In summary I was happy with the outcome of this change. The flat representation both handles a new feature, and makes for clearer operations. New results, using this data:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
student_id | date | time | |
---|---|---|---|
1 | 2019-02-04 | 15:00 | |
1 | 2019-02-05 | 15:00 | |
1 | 2019-02-06 | 16:00 | |
1 | 2019-02-07 | 16:00 | |
2 | 2019-02-04 | 17:00 | |
2 | 2019-02-05 | 17:00 | |
2 | 2019-02-06 | 15:00 | |
2 | 2019-02-08 | 14:00 | |
3 | 2019-02-04 | 15:00 | |
3 | 2019-02-05 | 16:00 | |
3 | 2019-02-07 | 17:00 | |
3 | 2019-02-08 | 14:00 | |
4 | 2019-02-04 | 17:00 | |
4 | 2019-02-05 | 15:00 | |
4 | 2019-02-05 | 16:00 | |
4 | 2019-02-05 | 17:00 | |
5 | 2019-02-06 | 17:00 | |
5 | 2019-02-06 | 15:00 | |
5 | 2019-02-06 | 16:00 | |
5 | 2019-02-07 | 17:00 | |
6 | 2019-02-04 | 17:00 | |
6 | 2019-02-05 | 16:00 | |
6 | 2019-02-06 | 15:00 | |
6 | 2019-02-08 | 14:00 | |
7 | 2019-02-04 | 17:00 | |
7 | 2019-02-05 | 17:00 | |
7 | 2019-02-06 | 15:00 | |
7 | 2019-02-07 | 14:00 |
The lessons are 20 minutes.
![]() | |
|
Inga kommentarer:
Skicka en kommentar