Last active
November 18, 2015 03:55
-
-
Save IanMercer/d7670577d5e88ab2bdf6 to your computer and use it in GitHub Desktop.
Sample using Constraint Solver to solve a student to workshop allocation problem. I made this to explore csp.net. Each student picks workshops they want to attend, each workshop has a limited size, each workshop runs four times in different time slots.
This file contains 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
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Threading; | |
using Csp; | |
using Csp.Constraints; | |
using NUnit.Framework; | |
namespace TestConstraintSolver | |
{ | |
[TestFixture] | |
internal class TestSolver | |
{ | |
private static readonly Random r = new Random(); | |
private IReadOnlyCollection<T> RandomPermutation<T>(IReadOnlyCollection<T> collection) | |
{ | |
IList<T> result = collection.ToList(); | |
for (int j = 0; j < result.Count; j++) | |
{ | |
var k = r.Next(result.Count); | |
var t = result[j]; | |
result[j] = result[k]; | |
result[k] = t; | |
} | |
return result.ToArray(); | |
} | |
[Test] | |
public void Solve() | |
{ | |
int studentCount = 23; | |
IReadOnlyCollection<Student> students = Enumerable.Range(1, studentCount) | |
.Select(i => new Student(i)) | |
.ToArray(); | |
int workshopCount = 5; | |
IReadOnlyCollection<Workshop> workshops = Enumerable.Range(1, workshopCount) | |
.Select(w => new Workshop(w)).ToArray(); | |
// Each student has five choices of workshops to attend | |
IReadOnlyDictionary<Student, IReadOnlyCollection<Workshop>> studentChoices = students | |
.Select(student => new {student, y = RandomPermutation(workshops)}) | |
.ToDictionary(x => x.student, x => x.y); | |
// Each student has four time slots on the calendar | |
var studentSlots = students.SelectMany(s => Enumerable.Range(1, 4) | |
.Select(r => new StudentSlot(s, r))); | |
// The variables are the StudentSlots and the domain is the workshops they want to attend | |
IReadOnlyCollection<Variable<StudentSlot, Workshop>> studentAssignmentVariables = | |
studentSlots.Select(ss => new Variable<StudentSlot, Workshop>(ss, | |
studentChoices[ss.Student])).ToList(); | |
var workshopsCanBeAttendedAtMostOnce = studentAssignmentVariables.GroupBy(x => x.UserObject.Student) | |
.Select(gp => new AllDifferentConstraint<StudentSlot, Workshop>(gp)); | |
// A single constraint for all variables to check no more than 19 per workshop | |
var workshopsContainUpTo19Students = new [] { new MaxWorkshopConstraint(studentAssignmentVariables, 19)}; | |
IConstraint<StudentSlot, Workshop>[] constraints = | |
Enumerable.Empty<IConstraint<StudentSlot, Workshop>>() | |
.Concat(workshopsCanBeAttendedAtMostOnce) | |
.Concat(workshopsContainUpTo19Students) | |
.ToArray(); | |
var problem = new Problem<StudentSlot, Workshop>(studentAssignmentVariables, constraints); | |
var solver = new RecursiveBacktrackSolver<StudentSlot, Workshop>(); | |
var solution = solver.Solve(problem, CancellationToken.None); | |
if (solution == null) | |
{ | |
Console.WriteLine("No solution"); | |
} | |
else | |
{ | |
var solutionDictionary = solution.AsReadOnlyDictionary(); | |
foreach (var result in solutionDictionary.GroupBy(x => x.Key.UserObject.Student).OrderBy(gp => gp.Key.StudentNumber)) | |
{ | |
var usersWorkshops = result.OrderBy(x => x.Key.UserObject.TimeSlot).Select(x => x.Value); | |
Console.WriteLine(result.Key + " : " + string.Join(", ", usersWorkshops)); | |
} | |
} | |
} | |
internal class Student | |
{ | |
public int StudentNumber { get; } | |
public Student(int number) | |
{ | |
this.StudentNumber = number; | |
} | |
public override string ToString() | |
{ | |
return "Student " + this.StudentNumber; | |
} | |
} | |
internal class StudentSlot | |
{ | |
public Student Student { get; } | |
public int TimeSlot { get; } | |
public StudentSlot(Student student, int timeSlot) | |
{ | |
this.Student = student; | |
this.TimeSlot = timeSlot; | |
} | |
public override string ToString() | |
{ | |
return this.Student + " session " + this.TimeSlot; | |
} | |
} | |
internal class Workshop | |
{ | |
public int WorkshopNumber { get; set; } | |
public Workshop(int workshop) | |
{ | |
this.WorkshopNumber = workshop; | |
} | |
public override string ToString() | |
{ | |
return "Workshop " + this.WorkshopNumber; | |
} | |
} | |
/// <summary> | |
/// The MaxWorkshopConstraint looks across all assigned variables to check no workshop has >19 | |
/// </summary> | |
internal class MaxWorkshopConstraint : IConstraint<StudentSlot, Workshop> | |
{ | |
readonly IReadOnlyCollection<Variable<StudentSlot, Workshop>> variables; | |
readonly int limit; | |
public MaxWorkshopConstraint(IEnumerable<Variable<StudentSlot, Workshop>> variables, int limit) | |
{ | |
this.variables = variables.ToList(); | |
this.limit = limit; | |
} | |
public bool IsViolated(Assignment<StudentSlot, Workshop> assignment) | |
{ | |
var workshopsInAssignment = this.variables | |
.Where(assignment.HasValue) | |
.Select(assignment.GetValue) | |
.GroupBy(x => x) | |
.ToList(); | |
return workshopsInAssignment.Any(x => x.Count() > this.limit); | |
} | |
public IReadOnlyCollection<Variable<StudentSlot, Workshop>> Variables => this.variables; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment