The Mentor Matching Problem
source link: https://matthewcrews.com/blog/2020-12-03-mathematical-planning-for-mentor-pairing/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
The Mentor Matching Problem
December 3, 2020
There are few things I love more than a fresh mathematical planning challenge so I was delighted when Kevin Avignon reached out to me and asked me to look at a question he had posted on the Software Engineer Stack Exchange site. He wanted to know whether the question was a candidate for Mathematical Planning. The question is a really interesting problem of pairing Mentors and Mentees. Mentors have a set of skills they can teach. Mentees have a set of skills they are interested in learning. Both Mentors and Mentees only have certain times they are available. Mentors are also capable of mentoring multiple mentees.
So, for this sounds like a straightforward assignment problem but then there is a twist. The questioner wanted pairings of rare skills to be a higher priority than pairings of more common skills. Ah, now we have a Mathematical Planning problem! We have the three key ingredients:
- A Quantifiable Objective: We want to maximize the value of pairings based on the rarity of the skill
- Constraints to follow: Mentors and Mentees must match on skills and availability
- Decision to make: Which Mentors and Mentees do we pair at what time?
Any time I see those three ingredients, I know I have a Mathematical Planning problem on my hands. I respond to Kevin and say, “Yes! You have a great candidate for Mathematical Planning! I’ll put something together for you this evening.” I begin mulling this problem as the day goes by. Once the family is all in bed, I turn on my PC and start modeling!
Define the Domain#
The first thing I do is put together a tiny domain of types to represent my problem. I encourage anyone who is writing these models in F# to take advantage of domain modeling because it will protect you again some nefarious bugs. To learn more, check out Scott Wlaschin’s book Domain Modeling Made Functional.
namespace MentorMatching
module Types =
type MentorId = MentorId of string
type MenteeId = MenteeId of string
type Skill = Skill of string
type Period = Period of int
type MenteeCapacity = MenteeCapacity of int
type Mentor = {
MentorId : MentorId
Skills : Skill Set
Periods : Period Set
MaxMentees : MenteeCapacity
}
type Mentee = {
MenteeId : MenteeId
Skills : Skill Set
Periods : Period Set
}
This simple set of types represent the problem space that I will build a mathematical planning model around. I now want to create a function which builds the model. I like to type out the functions signatures of what I am trying to implement beforehand as a way to get a high-level overview for that I am about to build. It’s an idea I got from Mark Seemann in his excellent PluralSight course Type-Driven Development with F#. Here is the function signature that I come to.
let private buildModel (mentees:Mentee seq) (mentors:Mentor seq) (skillValue:SMap<Skill,float>) (pairingDecision:SMap4<Skill,Period,Mentor,Mentee,Decision>) : Model =
The mentees
and mentors
arguments are self-explanatory. They are the mentors and mentees we want to pair up. The skillValue
argument is the value we have assigned to each Skill
for this problem. I will discuss the heuristic we use to calculate the value for a skill in a following section. The pairingDecision
argument is a 4-dimensional SliceMap. The first dimension is the Skill
, the second dimension is the Period
, the third dimension is the Mentor
, and the final dimension is the Mentee
. The value in the SliceMap is a Boolean
decision which indicates whether to use the pairing or not. We will be taking advantage of the slicing capabilities of SliceMaps to make the formulation more streamlined.
The first thing we need to do is create a set of constraints which state that a given Mentee
may only be assigned once. We use a ConstraintBuilder
Computation Expression and iterate through the mentees
, creating a constraint for each mentee
.
let menteeSingleAssignmentConstraints =
ConstraintBuilder "MenteeSingleAssignment" {
for mentee in mentees ->
sum pairingDecision.[All, All, All, mentee] <== 1.0
}
Now we need to limit how many Mentees a Mentor can take on. This value is the MenteeCapacity
of the Mentor
. We will loop through the sequence of Mentors and create the constraints that we need.
let mentorMaxAssignmentConstraints =
ConstraintBuilder "MentorMaxAssignments" {
for mentor in mentors ->
let (MenteeCapacity menteeCapacity) = mentor.MaxMentees
sum pairingDecision.[All, All, mentor, All] <== float menteeCapacity
}
There is an important nuance to this problem that could easily be missed. Mentors can take on multiple Mentees. It is entirely possible that the same Mentor is mentoring two different Mentees at the same time. This does not make sense. We need to create a set of constraints which prevents this from happening. We will create a constraint for each Mentor and each period to ensure this is not the case.
let mentorSingleAssignmentForPeriodConstraints =
ConstraintBuilder "MentorSingleAssignmentForPeriod" {
for mentor in mentors do
for period in mentor.Periods ->
let x = pairingDecision.[All, period, mentor, All]
sum pairingDecision.[All, period, mentor, All] <== 1.0
}
That is all the constraints that we need but we still need to create an expression that quantifies success, our objective function. We have assigned a value to each Skill
. We want to award pairings of valuable skills. To do that we can multiply the Value
of the Skill
by the decision that corresponds to that skill. The SliceMap
library provides a couple of conveniences for expressing this. The sum
function and the .*
operator. The sum
function is a function meant to be used with SliceMaps to make translating from math notation to code more straightforward. It is not strictly necessary, but it does make this kind of work more straightforward. The .*
operator is known as the Hadamard Product. If you have worked in Matlab, you probably recognize it. It is an element by element multiplication along matching dimensions. In this case it is going to multiply the value associated with each Skill
by the pairing decision that it corresponds to.
let assignmentValueExpr = sum (skillValue .* pairingDecision)
assignmentValueExpr
is a mathematical expression which quantifies how good of a solution the Solver has found. This is the thing we are wanting the Solver to make as large as possible. From here we create an Objective
and compose our model.
let maxAssignmentValueObjecitve =
Objective.create "MaxAssignmentValue" Maximize assignmentValueExpr
let model =
Model.create maxAssignmentValueObjecitve
|> Model.addConstraints menteeSingleAssignmentConstraints
|> Model.addConstraints mentorMaxAssignmentConstraints
|> Model.addConstraints mentorSingleAssignmentForPeriodConstraints
From here we can call the Solver.solve
function and get our results.
let solveSettings = {
SolverType = CBC
MaxDuration = 1_000L
WriteLPFile = None
}
let result = Solver.solve solveSettings model
match result with
| Optimal sln ->
Solution.getValues sln (pairingDecision.AsMap())
|> Map.toSeq
|> Seq.filter (fun (k, v) -> v >= 1.0) // Get the Pairings that the solver selected
|> Seq.map fst // Return just the tuple representing the pairing
|> Result.Ok
| _ -> Result.Error "Error Solving
If you want to see the full solution, check out the repo where I put it together.
Quantifying the Value of a Skill#
Earlier I mentioned that I would talk about the heuristic that was used to evaluate the value of a skill. I propose that we just rank the skills by the frequency of their occurrence and assign value based on its rank.
let private getSkillValue (mentees:Mentee seq) (mentors:Mentor seq) =
let menteeSkills =
mentees
|> Seq.collect (fun m -> m.Skills)
let mentorSkills =
mentors
|> Seq.collect (fun m -> m.Skills)
let skillCounts =
Seq.append menteeSkills mentorSkills
|> Seq.countBy id
let numberOfSkills = Seq.length skillCounts
skillCounts
|> Seq.sortBy snd
|> Seq.mapi (fun i (skill, _) -> skill, float (numberOfSkills - i))
|> Map.ofSeq
This ranking and scoring will ensure that the solver will choose low frequency skills over high frequency skills. There are some bizarre edge cases that could crop up, but I don’t have the space to cover them here.
Why Mathematical Planning instead some other algorithm?#
While this was a fun challenge, it is important to step back and ask, “Why would I choose this technique over some other?” The question on Stack Exchange has an interesting discussion of different approaches people proposed. Each of them has their own merit. The reason that I often propose Mathematical Planning that it is easy to modify should the nature of the problem change. If some new constraint was required, it would be relatively easy to refactor the code and add it. Bespoke implementations of heuristics are often difficult to refactor and evolve over time.
This was a fun challenge and I hope it ends up being useful. If you have questions about whether your problem is a good candidate for Mathematical Planning, please reach out!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK