Stable marriage problem... IN JAVASCRIPT
October 9, 2015 9:05 AM Subscribe
Trying to build an app (using JavaScript) that automatically generates a schedule for an "interview event."
More specifically, an interview event is an event during which companies interview students at a coding boot camp. Typically, the event is scheduled to last for four hours and each interview lasts 20 minutes. The app will need to automatically allocate students across the given time slots without creating scheduling conflicts while also maintaining a relatively equal distribution of interviews for both students and companies. It'll look like this schedule or this schedule.
Caveats:
1) Some companies will send multiple representatives. The app should avoid scheduling a student with the same company more than once EXCEPT if it is absolutely necessary to maintain an equal number of interviews across students.
2) Students and companies can rate each other on a three-point scale (1 = no, 2 = neutral, 3 = yes). The app should give preference to company/student combinations who want to meet when creating the schedule.
What I know:
Stable marriage problem seems to have some bearing. I've also looked at sodoku and speed dating stuff a little bit...
Some tech details:
If it matters, the entire app is being written in JavaScript. Node.js server, MongoDB database, Express.js framework, AngularJS frontend.
What I am looking for:
Not code exactly (though if there are some code samples you can point me to, that would obviously help too). More theory, algorithms, and general discussion about how to solve this kind of thing with computer programming (bonus points for JavaScript specific approaches). Also, libraries that might be useful? The team I am working with have got a pretty good start and there are some things happening, but it's a pretty complicated problem and we keep encountering little blocks. What say you hive mind?
More specifically, an interview event is an event during which companies interview students at a coding boot camp. Typically, the event is scheduled to last for four hours and each interview lasts 20 minutes. The app will need to automatically allocate students across the given time slots without creating scheduling conflicts while also maintaining a relatively equal distribution of interviews for both students and companies. It'll look like this schedule or this schedule.
Caveats:
1) Some companies will send multiple representatives. The app should avoid scheduling a student with the same company more than once EXCEPT if it is absolutely necessary to maintain an equal number of interviews across students.
2) Students and companies can rate each other on a three-point scale (1 = no, 2 = neutral, 3 = yes). The app should give preference to company/student combinations who want to meet when creating the schedule.
What I know:
Stable marriage problem seems to have some bearing. I've also looked at sodoku and speed dating stuff a little bit...
Some tech details:
If it matters, the entire app is being written in JavaScript. Node.js server, MongoDB database, Express.js framework, AngularJS frontend.
What I am looking for:
Not code exactly (though if there are some code samples you can point me to, that would obviously help too). More theory, algorithms, and general discussion about how to solve this kind of thing with computer programming (bonus points for JavaScript specific approaches). Also, libraries that might be useful? The team I am working with have got a pretty good start and there are some things happening, but it's a pretty complicated problem and we keep encountering little blocks. What say you hive mind?
there are two completely separate things here.
one is a web app that allows people and companies to register, specify preferences, and (later) retrieve appointments.
the other is some batch process, which, give registrations and preferences, allocates appointments.
so the most basic step is making sure that those two are separate. in particular, if it's not clear from the the specification / design that they are separate, or that there are two phases - before and after allocation - then you need to sort that out.
related to that, you also need to think about whether there needs to be a separate process, post-allocation, that handles changes in some way (perhaps using empty slots).
once that's clear, the first bit should be pretty standard and doable by anyone; the second part should be given to someone a bit more competent. for the second part, this paper and related work could be useful. but imagine you could also get close enough with an ad-hoc method using, say, simulated annealing. since it's off-line, run once, it doesn't have to be fast or beautiful.
posted by andrewcooke at 9:41 AM on October 9, 2015 [4 favorites]
one is a web app that allows people and companies to register, specify preferences, and (later) retrieve appointments.
the other is some batch process, which, give registrations and preferences, allocates appointments.
so the most basic step is making sure that those two are separate. in particular, if it's not clear from the the specification / design that they are separate, or that there are two phases - before and after allocation - then you need to sort that out.
related to that, you also need to think about whether there needs to be a separate process, post-allocation, that handles changes in some way (perhaps using empty slots).
once that's clear, the first bit should be pretty standard and doable by anyone; the second part should be given to someone a bit more competent. for the second part, this paper and related work could be useful. but imagine you could also get close enough with an ad-hoc method using, say, simulated annealing. since it's off-line, run once, it doesn't have to be fast or beautiful.
posted by andrewcooke at 9:41 AM on October 9, 2015 [4 favorites]
if you want to get really heavy with the second part, because it's offline and only has to talk to the database (why mongo?!) it could be in any language, so you could use some kind of constraint programming system. i've used choco, for example, and it was pretty easy to learn. but really, unless you're getting into the business of this kind of thing, it's likely not worth the effort.
posted by andrewcooke at 9:58 AM on October 9, 2015 [1 favorite]
posted by andrewcooke at 9:58 AM on October 9, 2015 [1 favorite]
In general for these things you have a couple of concepts:
- The set of possible states (assignments of candidate to interviewer to time slot).
- An evaluation function that takes in a state and returns a score for how good an arrangement is
- A function that generates a new state to try, uses the evaluation function on it to score it, decides if this is better than the best state seen so far or not, and then either decides it's time to stop or repeats the process
You're going to need these regardless of what approach you pick, so you may as well work them out first (the evaluation function in particular is going to need some tuning, as you see results and have to decide whether matching an interviewer and candidate who rated each other a three is more better than putting some candidate with the same company twice is worse).
If the number of states is small enough, you can just exhaustively enumerate each possible state and pick the best one. If it's larger, you'll need to take one of the other approaches above, which are all some combination of random selection and modification. Another approach that hasn't been mentioned is a genetic algorithm, where you essentially pick a random selection of states, choose the best, then randomly slightly modify the state in different ways to create a new set of selections.
posted by inkyz at 11:28 AM on October 9, 2015
- The set of possible states (assignments of candidate to interviewer to time slot).
- An evaluation function that takes in a state and returns a score for how good an arrangement is
- A function that generates a new state to try, uses the evaluation function on it to score it, decides if this is better than the best state seen so far or not, and then either decides it's time to stop or repeats the process
You're going to need these regardless of what approach you pick, so you may as well work them out first (the evaluation function in particular is going to need some tuning, as you see results and have to decide whether matching an interviewer and candidate who rated each other a three is more better than putting some candidate with the same company twice is worse).
If the number of states is small enough, you can just exhaustively enumerate each possible state and pick the best one. If it's larger, you'll need to take one of the other approaches above, which are all some combination of random selection and modification. Another approach that hasn't been mentioned is a genetic algorithm, where you essentially pick a random selection of states, choose the best, then randomly slightly modify the state in different ways to create a new set of selections.
posted by inkyz at 11:28 AM on October 9, 2015
Finally my research area comes into play on AskMeFi.
The above posts mostly have it, but I'll add that this seems more similar in flavour to scheduling/timetabling problems than strictly stable marriage / graph matching as you have several side constraints in play. I wish I had commercialized my timetabling code by now, I could just point you at that ;)
It may be useful to make a more formal specification of your problem, taking into account all of your extra constraints. Some immediate questions that sprang to mind:
- Are the company representatives each just sitting in a single room for 4 hours, and the students come to them, or do you have to allocate rooms as well for each pairing?
- Is the equal number of interviews for each student a hard constraint that you must satisfy, or are you willing to break it in some cases? i.e., what priority do you place between extra interviews for students (causing some to have more/fewer than others) vs. having some company representatives with an empty time slot?
- With the ratings, are you really trying to maximize, say, the sum of ratings across all of your pairings, or do negative ratings impact more than neutral/yes?
There's probably more, but these problems are often very efficiently solved by local search techniques, using efficient algorithms for maximum bipartite graph matching as a subprocedure for time slot assignment. (see for example the Edmonds-Karp algorithm for computing such a matching. There are others too, if you want to get into heuristics.) Feel free to MeMail me too if you like, solving combinatorial problems like this is what I do for a living.
posted by homotopy at 1:06 PM on October 9, 2015 [1 favorite]
The above posts mostly have it, but I'll add that this seems more similar in flavour to scheduling/timetabling problems than strictly stable marriage / graph matching as you have several side constraints in play. I wish I had commercialized my timetabling code by now, I could just point you at that ;)
It may be useful to make a more formal specification of your problem, taking into account all of your extra constraints. Some immediate questions that sprang to mind:
- Are the company representatives each just sitting in a single room for 4 hours, and the students come to them, or do you have to allocate rooms as well for each pairing?
- Is the equal number of interviews for each student a hard constraint that you must satisfy, or are you willing to break it in some cases? i.e., what priority do you place between extra interviews for students (causing some to have more/fewer than others) vs. having some company representatives with an empty time slot?
- With the ratings, are you really trying to maximize, say, the sum of ratings across all of your pairings, or do negative ratings impact more than neutral/yes?
There's probably more, but these problems are often very efficiently solved by local search techniques, using efficient algorithms for maximum bipartite graph matching as a subprocedure for time slot assignment. (see for example the Edmonds-Karp algorithm for computing such a matching. There are others too, if you want to get into heuristics.) Feel free to MeMail me too if you like, solving combinatorial problems like this is what I do for a living.
posted by homotopy at 1:06 PM on October 9, 2015 [1 favorite]
Response by poster: Thanks everyone for the suggestions. Glad to throw something in your wheelhouse homotopy! Any particular timetabling links you got?
We have made pretty good progress on the issue and we're using this weekend to further experiment and research so big thanks for all the resources in particular. Our code can now generate a complete random schedule that allocates a relatively equal number of interviews to students while avoiding schedule conflicts. I'm sure ratings will ruin that. Ha.
Some answers for the curious:
(why mongo?!)
Mongo because as it were, I am actually a current student at this code academy and Mongo is what we were taught. This app is the final group project for the client (in our group's case, the client is the school). Each interview event will have approximately 20 students and approximately 20 interviewers, so it didn't really seem like a lightweight database would be problematic. Am I incorrect in that assumption?
Are the company representatives each just sitting in a single room for 4 hours, and the students come to them, or do you have to allocate rooms as well for each pairing?
Exactly the former. Everyone is in one giant room. It gets pretty loud.
Is the equal number of interviews for each student a hard constraint that you must satisfy, or are you willing to break it in some cases? i.e., what priority do you place between extra interviews for students (causing some to have more/fewer than others) vs. having some company representatives with an empty time slot?
Students need only have a relatively equal amount of interviews so it isn't a hard constraint.
With the ratings, are you really trying to maximize, say, the sum of ratings across all of your pairings, or do negative ratings impact more than neutral/yes?
Actually, it's the other way around (to some extent). Positive ratings of students by companies impact more than neutral/no. In other words, if a company is a "yes" for the student the app should make it a point to prioritize that pairing even if the student is a "no." (As to why that would be, the staff at the school are of a mind that students probably don't have as clear a view of companies that would be a good fit so if someone really wants to meet them, the app should make it happen even if the student isn't that interested... JUST IN CASE).
posted by panoptican at 8:16 AM on October 10, 2015
We have made pretty good progress on the issue and we're using this weekend to further experiment and research so big thanks for all the resources in particular. Our code can now generate a complete random schedule that allocates a relatively equal number of interviews to students while avoiding schedule conflicts. I'm sure ratings will ruin that. Ha.
Some answers for the curious:
(why mongo?!)
Mongo because as it were, I am actually a current student at this code academy and Mongo is what we were taught. This app is the final group project for the client (in our group's case, the client is the school). Each interview event will have approximately 20 students and approximately 20 interviewers, so it didn't really seem like a lightweight database would be problematic. Am I incorrect in that assumption?
Are the company representatives each just sitting in a single room for 4 hours, and the students come to them, or do you have to allocate rooms as well for each pairing?
Exactly the former. Everyone is in one giant room. It gets pretty loud.
Is the equal number of interviews for each student a hard constraint that you must satisfy, or are you willing to break it in some cases? i.e., what priority do you place between extra interviews for students (causing some to have more/fewer than others) vs. having some company representatives with an empty time slot?
Students need only have a relatively equal amount of interviews so it isn't a hard constraint.
With the ratings, are you really trying to maximize, say, the sum of ratings across all of your pairings, or do negative ratings impact more than neutral/yes?
Actually, it's the other way around (to some extent). Positive ratings of students by companies impact more than neutral/no. In other words, if a company is a "yes" for the student the app should make it a point to prioritize that pairing even if the student is a "no." (As to why that would be, the staff at the school are of a mind that students probably don't have as clear a view of companies that would be a good fit so if someone really wants to meet them, the app should make it happen even if the student isn't that interested... JUST IN CASE).
posted by panoptican at 8:16 AM on October 10, 2015
Best answer: Here's the code, in case anyone was curious. The schedule module is the driving force. Thanks for the guidance from all!
posted by panoptican at 6:22 PM on November 11, 2015 [1 favorite]
posted by panoptican at 6:22 PM on November 11, 2015 [1 favorite]
« Older Things to do with long Paris layover besides... | How to find a balance with a (maybe?) flirty... Newer »
This thread is closed to new comments.
If you have a small number of students and reps, this may be a better use of your time.
posted by brentajones at 9:37 AM on October 9, 2015 [1 favorite]