Implement CSP soft constraints

[NolanVH]

User Story

As a developer of the CSP implementation I would like to be able to have a set of functions which represent the soft scheduling constraints that I can use to reduce the possible valid assignments of values to variables.

The five soft constraints and the approach we will use to implement them can be found here.

Acceptance Criteria

• [x] All five soft constraints from the doc are taken into account
• [x] Constraints are carefully analyzed and tested for runtime complexity
• [x] Constraint implementations are easy to understand and identify
• [ ] At least one test is implemented to ensure we generate schedule that is optimized for soft constraints

Related Issues

Blocked by #35 Blocks #15

Additional Resources

Add attachments, external links, etc here.

[strdavis]

• Implemented soft constraint approach for backtracking search, as discussed with group.
  • Running the search repeatedly, relaxing the satisfaction threshold each time.
  • Sorting the professors by preference score for each course.
• This approach did not work. If the highest possible satisfaction score for any one professor is very low, then this approach fails to find a solution until the threshold has been lowered far enough to permit that low satisfaction score. But then it also permits low satisfaction scores for all other professors, so the overall improvement is minimal.
• However, sorting the professor by preference score was very effective.
• As an alternative, implemented an optimizer based on the min-conflicts algorithm. This optimizer runs on the feasible schedule produced by the backtracking search. ie we use the backtracking search to satisfy the hard constraints, then optimize on the result.
• This approach seems to work well.
  • When applied to the result of CSP 1, where professors were sorted by preference score, it increases the overall average enthusiasm score by ~10 points (from ~168 to ~178).
  • Preliminary testing indicates it also works for the num-courses-per-semester constraint.
  • Runtime for CSP 1 is increased to around 3 seconds on my machine.

[strdavis]

• Implemented preferred-course-day-spread soft constraint.
• Again used the min-conflicts-based optimization method.
• Seems to work for basic tests where a small number of professors have preferred course day spreads specified.
• Still need to test with preferred course day spreads specified for all professors.
• Runtime of CSP 2 is increased to around 20 seconds on my machine.
• Note that in the optimization steps for both CSP 1 and CSP 2, the max number of iterations is set to 1000. However, we rarely see improvements after 500 iterations, so we can probably reduce the number of steps and cut the runtime in half.

[strdavis]

• Tested the optimizer on the preferred-course-day-spread soft constraint, where all professors had a specified preference for this constraint.
• The majority of professors had timeslots reassigned. The resulting timeslots were always in alignment with the professor's preferences.
• Optimizer was run on CSP 2 for 500 iterations. CSP 2 runtime was around 8 seconds on my machine.

[kianapaz]

• Implemented the Hard constraint for the professors on leave and the researching professors that require a semester off
• created a hard constraint for both, but pruned the CSP 1 domain to exclude the researching profs for their researching professor
• The CSP 1 & 2 soft constraints are implemented and running at about 2.4 seconds and 4.6 seconds respectively
• The CSP 2 soft constraint now takes into account the multiple ranges of preferred time slots for a professor.
• Optimizer is set to run for 1000 iterations for CSP 1 and 2

[kianapaz]

Notes:

BE's professor input had to be edited for the following

• Kui Wu had to change his semester off to SUMMER from SPRING in order to teach CSC361_spring
• SIma had to change his semester off to SPRING from SUMMER in order to teach SENG440_summer