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.
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.
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
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.
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.
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.
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.
From here we can call the
Solver.solve function and get our results.
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.
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!