Skip to content

Instantly share code, notes, and snippets.

@IanMercer
Last active November 18, 2015 03:55
Show Gist options
  • Save IanMercer/d7670577d5e88ab2bdf6 to your computer and use it in GitHub Desktop.
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.
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