Matthew Crews
Blog About
Matthew Crews

The Mentor Matching Problem

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:

  1. A Quantifiable Objective: We want to maximize the value of pairings based on the rarity of the skill
  2. Constraints to follow: Mentors and Mentees must match on skills and availability
  3. 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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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.

1

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.

1
2
3
4
5

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.

1
2
3
4
5
6

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.

1
2
3
4
5
6
7

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.

1

 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.

1
2
3
4
5
6
7
8

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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!