Student sectioning (after a solution is found).
In the current implementation, students are not re-sectioned during the
search, but a student re-sectioning algorithm is called after the solver is
finished or upon the user's request. The re-sectioning is based on a local
search algorithm where the neighboring assignment is obtained from the
current assignment by applying one of the following moves:
- Two students enrolled in the same course swap all of their class
- A student is re-enrolled into classes associated with a course such that
the number of conflicts involving that student is minimized.
The solver maintains a queue, initially containing all courses with multiple
classes. During each iteration, an improving move (i.e., a move decreasing
the overall number of student conflicts) is applied once discovered.
Re-sectioning is complete once no more improving moves are possible. Only
consistent moves (i.e., moves that respect class limits and other
constraints) are considered. Any additional courses having student conflicts
after a move is accepted are added to the queue.
Since students are not re-sectioned during the timetabling search, the
computed number of student conflicts is really an upper bound on the actual
number that may exist afterward. To compensate for this during the search,
student conflicts between subparts with multiple classes are weighted lower
than conflicts between classes that meet at a single time (i.e., having
student conflicts that cannot be avoided by re-sectioning).