Mixing
Choosing office hours to maximise number of students who can attend at least one time slot
Clash Royale CLAN TAG#URR8PPP
up vote
39
down vote
favorite
I have the following (real world!) problem which is most easily described using an example.
I ask my six students when the best time to hold office hours would be. I give them four options, and say that I'll hold two hours in total. The poll's results are as follows (1 means yes, 0 means no):
$$beginarrayc
textName & 9 text am & 10 text am & 11 text am & 12 text pm \ hline
textAlice & 1 & 1 & 0 & 0 \
textBob & 1 & 1 & 0 & 1 \
textCharlotte & 1 & 1 & 0 & 1 \
textDaniel & 0 & 1 & 1 & 1 \
textEve & 0 & 0 & 1 & 1 \
textFrank & 0 & 0 & 1 & 0 \ hline
textTotal & 3 & 4 & 3 & 4
endarray$$
Naively, one might pick columns 2 and 4, which have the greatest totals. However, the solution which allows the most distinct people to attend is to pick columns 2 and 3.
In practice, however, I have ~30 possible timeslots and over 100 students, and want to pick, say, five different timeslots for office hours. How do I pick the timeslots which maximise the number of distinct students who can attend?
combinatorics optimization
asked 2 days ago
lokodiz
1,3941719
 |Â
show 7 more comments
up vote
39
down vote
favorite
I have the following (real world!) problem which is most easily described using an example.
I ask my six students when the best time to hold office hours would be. I give them four options, and say that I'll hold two hours in total. The poll's results are as follows (1 means yes, 0 means no):
$$beginarrayc
textName & 9 text am & 10 text am & 11 text am & 12 text pm \ hline
textAlice & 1 & 1 & 0 & 0 \
textBob & 1 & 1 & 0 & 1 \
textCharlotte & 1 & 1 & 0 & 1 \
textDaniel & 0 & 1 & 1 & 1 \
textEve & 0 & 0 & 1 & 1 \
textFrank & 0 & 0 & 1 & 0 \ hline
textTotal & 3 & 4 & 3 & 4
endarray$$
Naively, one might pick columns 2 and 4, which have the greatest totals. However, the solution which allows the most distinct people to attend is to pick columns 2 and 3.
In practice, however, I have ~30 possible timeslots and over 100 students, and want to pick, say, five different timeslots for office hours. How do I pick the timeslots which maximise the number of distinct students who can attend?
combinatorics optimization
asked 2 days ago
lokodiz
1,3941719
8
$binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
– Misha Lavrov
2 days ago
5
I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
– lokodiz
2 days ago
3
Re the formulation: Based on experience, it's much better instead of asking for a hard binary 1/0 is to have them soft-rank each timeslot from 0 (totally impossible, conflict) up to say 3 or 4 (ideal)
– smci
2 days ago
5
Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
– Eric Duminil
yesterday
2
@smci : that solution might also solve a secondary problem: students who do not have that many choices overall might be more important to cover first in an algorithm like Misha's than those available all the time. compare Frank in the example above to Bob/Charlotte/Daniel (those 3 are irrelevant for the solution as they will always be covered when choosing 2 slots of 4).
– Chieron
yesterday
 |Â
show 7 more comments
up vote
39
down vote
favorite
up vote
39
down vote
favorite
I have the following (real world!) problem which is most easily described using an example.
I ask my six students when the best time to hold office hours would be. I give them four options, and say that I'll hold two hours in total. The poll's results are as follows (1 means yes, 0 means no):
$$beginarrayc
textName & 9 text am & 10 text am & 11 text am & 12 text pm \ hline
textAlice & 1 & 1 & 0 & 0 \
textBob & 1 & 1 & 0 & 1 \
textCharlotte & 1 & 1 & 0 & 1 \
textDaniel & 0 & 1 & 1 & 1 \
textEve & 0 & 0 & 1 & 1 \
textFrank & 0 & 0 & 1 & 0 \ hline
textTotal & 3 & 4 & 3 & 4
endarray$$
Naively, one might pick columns 2 and 4, which have the greatest totals. However, the solution which allows the most distinct people to attend is to pick columns 2 and 3.
In practice, however, I have ~30 possible timeslots and over 100 students, and want to pick, say, five different timeslots for office hours. How do I pick the timeslots which maximise the number of distinct students who can attend?
combinatorics optimization
asked 2 days ago
lokodiz
1,3941719
I have the following (real world!) problem which is most easily described using an example.
I ask my six students when the best time to hold office hours would be. I give them four options, and say that I'll hold two hours in total. The poll's results are as follows (1 means yes, 0 means no):
$$beginarrayc
textName & 9 text am & 10 text am & 11 text am & 12 text pm \ hline
textAlice & 1 & 1 & 0 & 0 \
textBob & 1 & 1 & 0 & 1 \
textCharlotte & 1 & 1 & 0 & 1 \
textDaniel & 0 & 1 & 1 & 1 \
textEve & 0 & 0 & 1 & 1 \
textFrank & 0 & 0 & 1 & 0 \ hline
textTotal & 3 & 4 & 3 & 4
endarray$$
Naively, one might pick columns 2 and 4, which have the greatest totals. However, the solution which allows the most distinct people to attend is to pick columns 2 and 3.
In practice, however, I have ~30 possible timeslots and over 100 students, and want to pick, say, five different timeslots for office hours. How do I pick the timeslots which maximise the number of distinct students who can attend?
combinatorics optimization
combinatorics optimization
asked 2 days ago
lokodiz
1,3941719
asked 2 days ago
lokodiz
1,3941719
edited 14 hours ago
asked 2 days ago
lokodiz
1,3941719
asked 2 days ago
lokodiz
1,3941719
asked 2 days ago
lokodiz
1,3941719
1,3941719
8
$binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
– Misha Lavrov
2 days ago
5
I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
– lokodiz
2 days ago
3
Re the formulation: Based on experience, it's much better instead of asking for a hard binary 1/0 is to have them soft-rank each timeslot from 0 (totally impossible, conflict) up to say 3 or 4 (ideal)
– smci
2 days ago
5
Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
– Eric Duminil
yesterday
2
@smci : that solution might also solve a secondary problem: students who do not have that many choices overall might be more important to cover first in an algorithm like Misha's than those available all the time. compare Frank in the example above to Bob/Charlotte/Daniel (those 3 are irrelevant for the solution as they will always be covered when choosing 2 slots of 4).
– Chieron
yesterday
 |Â
show 7 more comments
8
$binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
– Misha Lavrov
2 days ago
5
I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
– lokodiz
2 days ago
3
Re the formulation: Based on experience, it's much better instead of asking for a hard binary 1/0 is to have them soft-rank each timeslot from 0 (totally impossible, conflict) up to say 3 or 4 (ideal)
– smci
2 days ago
5
Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
– Eric Duminil
yesterday
2
@smci : that solution might also solve a secondary problem: students who do not have that many choices overall might be more important to cover first in an algorithm like Misha's than those available all the time. compare Frank in the example above to Bob/Charlotte/Daniel (those 3 are irrelevant for the solution as they will always be covered when choosing 2 slots of 4).
– Chieron
yesterday
8
8
$binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
– Misha Lavrov
2 days ago
$binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
– Misha Lavrov
2 days ago
5
5
I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
– lokodiz
2 days ago
I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
– lokodiz
2 days ago
3
3
Re the formulation: Based on experience, it's much better instead of asking for a hard binary 1/0 is to have them soft-rank each timeslot from 0 (totally impossible, conflict) up to say 3 or 4 (ideal)
– smci
2 days ago
Re the formulation: Based on experience, it's much better instead of asking for a hard binary 1/0 is to have them soft-rank each timeslot from 0 (totally impossible, conflict) up to say 3 or 4 (ideal)
– smci
2 days ago
5
5
Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
– Eric Duminil
yesterday
Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
– Eric Duminil
yesterday
2
2
@smci : that solution might also solve a secondary problem: students who do not have that many choices overall might be more important to cover first in an algorithm like Misha's than those available all the time. compare Frank in the example above to Bob/Charlotte/Daniel (those 3 are irrelevant for the solution as they will always be covered when choosing 2 slots of 4).
– Chieron
yesterday
@smci : that solution might also solve a secondary problem: students who do not have that many choices overall might be more important to cover first in an algorithm like Misha's than those available all the time. compare Frank in the example above to Bob/Charlotte/Daniel (those 3 are irrelevant for the solution as they will always be covered when choosing 2 slots of 4).
– Chieron
yesterday
 |Â
show 7 more comments
3 Answers
3
active
oldest
votes
up vote
55
down vote
accepted
In general, this problem is the maximum coverage problem, which is NP-hard, so you're not going to be able to find the optimal solution by any method substantially faster than brute force. (As I mentioned, for a problem of your size, brute force is still feasible.)
However, a modification of your strategy (to choose the timeslots with the highest totals) performs reasonably well.
It doesn't actually make sense to choose all the timeslots with the highest totals immediately: if they all have the same students in them, then this isn't any better than just choosing one of the timeslots. Instead, we can:
- Choose one timeslot with the highest total number of students.
- Remove all students that can make it to that timeslot from consideration. Recalculate the totals for the remaining students.
- Repeat steps 1-2 until you have chosen $k=5$ timeslots.
According to the wikipedia article, this algorithm achieves an approximation ratio of $1 - frac1e$; that is, if you can reach $N$ students with the optimal choice of timeslots, this algorithm will reach at least $(1 - frac1e)N$ students.
There are other possible approximate solutions out there; for example, there is the big step heuristic, which considers all choices of $p$ timeslots in each step, as opposed to all individual timeslots. (When $p=1$, it is the algorithm above; when $p=k$, it is just brute force.) No fast algorithm has guaranteed performance better than $(1 - frac1e)N$, but they may perform better in some cases.
answered 2 days ago
Misha Lavrov
37.8k55093
"so you're not going to be able to do substantially better than brute force" That is very wrong. You can do much better than brute force (which will fail for large numbers) provided you don't need perfection (as you go on to show).
– Martin Bonner
yesterday
@MartinBonner Good point. I have rephrased to make the statement more precise.
– Misha Lavrov
yesterday
I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
– qwr
yesterday
@qwr Different NP-hard problems have extremely different behavior when we try to approximate them, and extremely different average-case behavior (for instance, approximating the maximum independent set of a graph is hard in almost all cases). Not being an expert, I wouldn't want to say anything about this specific problem. The known hardness result here is that (assuming $P ne NP$) no algorithm can guarantee a $(1 - frac1e + epsilon)$-factor approximation; this, of course, does not say anything about the average case.
– Misha Lavrov
yesterday
add a comment |Â
up vote
8
down vote
With those numbers, brute force is still feasible. You have 30 choose 5 = 142506 different combinations. I don't think there's any algorithm other than brute force that is guaranteed to get the best solution, but one heuristic would be to arrange the students in sets from least availability to most. Then rank time slots by how many of the least available students they match, then break ties by how many of second lest available, etc. Take the best time slot according to that criteria. Remove all students that can make that time slot, and apply the same algorithm to the remaining time slots and students, and continue until you've reached your maximum number of time slots. In your example, Frank is the least available student, so 11 am, as the only time slot he can make, is the first choice. This leaves Alice, Bob, and Charlotte without a time slot, and of them, Alice is the least available. 9 am and 10 am both accommodate Alice, so you can take either one (although if you take into account students that were removed in previous steps, then 10 am wins).
You can combine the two: use the heuristic until you get to small enough numbers that you're okay with using brute force.
Another heuristic is to look at clustering (is there one set of students that is mostly available in the morning, and another in the evening), and pick time slots in different clusters.
answered 2 days ago
Acccumulation
5,7642616
add a comment |Â
up vote
3
down vote
Practically speaking, simply vary the office hours each week.
answered yesterday
user38230
462
2
The risk here is low attendance because students end up confused about when your office hours are.
– Misha Lavrov
yesterday
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
55
down vote
accepted
In general, this problem is the maximum coverage problem, which is NP-hard, so you're not going to be able to find the optimal solution by any method substantially faster than brute force. (As I mentioned, for a problem of your size, brute force is still feasible.)
However, a modification of your strategy (to choose the timeslots with the highest totals) performs reasonably well.
It doesn't actually make sense to choose all the timeslots with the highest totals immediately: if they all have the same students in them, then this isn't any better than just choosing one of the timeslots. Instead, we can:
- Choose one timeslot with the highest total number of students.
- Remove all students that can make it to that timeslot from consideration. Recalculate the totals for the remaining students.
- Repeat steps 1-2 until you have chosen $k=5$ timeslots.
According to the wikipedia article, this algorithm achieves an approximation ratio of $1 - frac1e$; that is, if you can reach $N$ students with the optimal choice of timeslots, this algorithm will reach at least $(1 - frac1e)N$ students.
There are other possible approximate solutions out there; for example, there is the big step heuristic, which considers all choices of $p$ timeslots in each step, as opposed to all individual timeslots. (When $p=1$, it is the algorithm above; when $p=k$, it is just brute force.) No fast algorithm has guaranteed performance better than $(1 - frac1e)N$, but they may perform better in some cases.
answered 2 days ago
Misha Lavrov
37.8k55093
"so you're not going to be able to do substantially better than brute force" That is very wrong. You can do much better than brute force (which will fail for large numbers) provided you don't need perfection (as you go on to show).
– Martin Bonner
yesterday
@MartinBonner Good point. I have rephrased to make the statement more precise.
– Misha Lavrov
yesterday
I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
– qwr
yesterday
@qwr Different NP-hard problems have extremely different behavior when we try to approximate them, and extremely different average-case behavior (for instance, approximating the maximum independent set of a graph is hard in almost all cases). Not being an expert, I wouldn't want to say anything about this specific problem. The known hardness result here is that (assuming $P ne NP$) no algorithm can guarantee a $(1 - frac1e + epsilon)$-factor approximation; this, of course, does not say anything about the average case.
– Misha Lavrov
yesterday
add a comment |Â
up vote
55
down vote
accepted
In general, this problem is the maximum coverage problem, which is NP-hard, so you're not going to be able to find the optimal solution by any method substantially faster than brute force. (As I mentioned, for a problem of your size, brute force is still feasible.)
However, a modification of your strategy (to choose the timeslots with the highest totals) performs reasonably well.
It doesn't actually make sense to choose all the timeslots with the highest totals immediately: if they all have the same students in them, then this isn't any better than just choosing one of the timeslots. Instead, we can:
- Choose one timeslot with the highest total number of students.
- Remove all students that can make it to that timeslot from consideration. Recalculate the totals for the remaining students.
- Repeat steps 1-2 until you have chosen $k=5$ timeslots.
According to the wikipedia article, this algorithm achieves an approximation ratio of $1 - frac1e$; that is, if you can reach $N$ students with the optimal choice of timeslots, this algorithm will reach at least $(1 - frac1e)N$ students.
There are other possible approximate solutions out there; for example, there is the big step heuristic, which considers all choices of $p$ timeslots in each step, as opposed to all individual timeslots. (When $p=1$, it is the algorithm above; when $p=k$, it is just brute force.) No fast algorithm has guaranteed performance better than $(1 - frac1e)N$, but they may perform better in some cases.
answered 2 days ago
Misha Lavrov
37.8k55093
"so you're not going to be able to do substantially better than brute force" That is very wrong. You can do much better than brute force (which will fail for large numbers) provided you don't need perfection (as you go on to show).
– Martin Bonner
yesterday
@MartinBonner Good point. I have rephrased to make the statement more precise.
– Misha Lavrov
yesterday
I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
– qwr
yesterday
@qwr Different NP-hard problems have extremely different behavior when we try to approximate them, and extremely different average-case behavior (for instance, approximating the maximum independent set of a graph is hard in almost all cases). Not being an expert, I wouldn't want to say anything about this specific problem. The known hardness result here is that (assuming $P ne NP$) no algorithm can guarantee a $(1 - frac1e + epsilon)$-factor approximation; this, of course, does not say anything about the average case.
– Misha Lavrov
yesterday
add a comment |Â
up vote
55
down vote
accepted
up vote
55
down vote
accepted
In general, this problem is the maximum coverage problem, which is NP-hard, so you're not going to be able to find the optimal solution by any method substantially faster than brute force. (As I mentioned, for a problem of your size, brute force is still feasible.)
However, a modification of your strategy (to choose the timeslots with the highest totals) performs reasonably well.
It doesn't actually make sense to choose all the timeslots with the highest totals immediately: if they all have the same students in them, then this isn't any better than just choosing one of the timeslots. Instead, we can:
- Choose one timeslot with the highest total number of students.
- Remove all students that can make it to that timeslot from consideration. Recalculate the totals for the remaining students.
- Repeat steps 1-2 until you have chosen $k=5$ timeslots.
According to the wikipedia article, this algorithm achieves an approximation ratio of $1 - frac1e$; that is, if you can reach $N$ students with the optimal choice of timeslots, this algorithm will reach at least $(1 - frac1e)N$ students.
There are other possible approximate solutions out there; for example, there is the big step heuristic, which considers all choices of $p$ timeslots in each step, as opposed to all individual timeslots. (When $p=1$, it is the algorithm above; when $p=k$, it is just brute force.) No fast algorithm has guaranteed performance better than $(1 - frac1e)N$, but they may perform better in some cases.
answered 2 days ago
Misha Lavrov
37.8k55093
In general, this problem is the maximum coverage problem, which is NP-hard, so you're not going to be able to find the optimal solution by any method substantially faster than brute force. (As I mentioned, for a problem of your size, brute force is still feasible.)
However, a modification of your strategy (to choose the timeslots with the highest totals) performs reasonably well.
It doesn't actually make sense to choose all the timeslots with the highest totals immediately: if they all have the same students in them, then this isn't any better than just choosing one of the timeslots. Instead, we can:
- Choose one timeslot with the highest total number of students.
- Remove all students that can make it to that timeslot from consideration. Recalculate the totals for the remaining students.
- Repeat steps 1-2 until you have chosen $k=5$ timeslots.
According to the wikipedia article, this algorithm achieves an approximation ratio of $1 - frac1e$; that is, if you can reach $N$ students with the optimal choice of timeslots, this algorithm will reach at least $(1 - frac1e)N$ students.
There are other possible approximate solutions out there; for example, there is the big step heuristic, which considers all choices of $p$ timeslots in each step, as opposed to all individual timeslots. (When $p=1$, it is the algorithm above; when $p=k$, it is just brute force.) No fast algorithm has guaranteed performance better than $(1 - frac1e)N$, but they may perform better in some cases.
answered 2 days ago
Misha Lavrov
37.8k55093
edited yesterday
answered 2 days ago
Misha Lavrov
37.8k55093
answered 2 days ago
Misha Lavrov
37.8k55093
answered 2 days ago
Misha Lavrov
37.8k55093
37.8k55093
"so you're not going to be able to do substantially better than brute force" That is very wrong. You can do much better than brute force (which will fail for large numbers) provided you don't need perfection (as you go on to show).
– Martin Bonner
yesterday
@MartinBonner Good point. I have rephrased to make the statement more precise.
– Misha Lavrov
yesterday
I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
– qwr
yesterday
@qwr Different NP-hard problems have extremely different behavior when we try to approximate them, and extremely different average-case behavior (for instance, approximating the maximum independent set of a graph is hard in almost all cases). Not being an expert, I wouldn't want to say anything about this specific problem. The known hardness result here is that (assuming $P ne NP$) no algorithm can guarantee a $(1 - frac1e + epsilon)$-factor approximation; this, of course, does not say anything about the average case.
– Misha Lavrov
yesterday
add a comment |Â
"so you're not going to be able to do substantially better than brute force" That is very wrong. You can do much better than brute force (which will fail for large numbers) provided you don't need perfection (as you go on to show).
– Martin Bonner
yesterday
@MartinBonner Good point. I have rephrased to make the statement more precise.
– Misha Lavrov
yesterday
I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
– qwr
yesterday
@qwr Different NP-hard problems have extremely different behavior when we try to approximate them, and extremely different average-case behavior (for instance, approximating the maximum independent set of a graph is hard in almost all cases). Not being an expert, I wouldn't want to say anything about this specific problem. The known hardness result here is that (assuming $P ne NP$) no algorithm can guarantee a $(1 - frac1e + epsilon)$-factor approximation; this, of course, does not say anything about the average case.
– Misha Lavrov
yesterday
"so you're not going to be able to do substantially better than brute force" That is very wrong. You can do much better than brute force (which will fail for large numbers) provided you don't need perfection (as you go on to show).
– Martin Bonner
yesterday
"so you're not going to be able to do substantially better than brute force" That is very wrong. You can do much better than brute force (which will fail for large numbers) provided you don't need perfection (as you go on to show).
– Martin Bonner
yesterday
@MartinBonner Good point. I have rephrased to make the statement more precise.
– Misha Lavrov
yesterday
@MartinBonner Good point. I have rephrased to make the statement more precise.
– Misha Lavrov
yesterday
I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
– qwr
yesterday
I think it's worth noting approximation algorithms for NP-hard problems like TSP and SAT perform extremely well on real-world examples.
– qwr
yesterday
@qwr Different NP-hard problems have extremely different behavior when we try to approximate them, and extremely different average-case behavior (for instance, approximating the maximum independent set of a graph is hard in almost all cases). Not being an expert, I wouldn't want to say anything about this specific problem. The known hardness result here is that (assuming $P ne NP$) no algorithm can guarantee a $(1 - frac1e + epsilon)$-factor approximation; this, of course, does not say anything about the average case.
– Misha Lavrov
yesterday
@qwr Different NP-hard problems have extremely different behavior when we try to approximate them, and extremely different average-case behavior (for instance, approximating the maximum independent set of a graph is hard in almost all cases). Not being an expert, I wouldn't want to say anything about this specific problem. The known hardness result here is that (assuming $P ne NP$) no algorithm can guarantee a $(1 - frac1e + epsilon)$-factor approximation; this, of course, does not say anything about the average case.
– Misha Lavrov
yesterday
add a comment |Â
up vote
8
down vote
With those numbers, brute force is still feasible. You have 30 choose 5 = 142506 different combinations. I don't think there's any algorithm other than brute force that is guaranteed to get the best solution, but one heuristic would be to arrange the students in sets from least availability to most. Then rank time slots by how many of the least available students they match, then break ties by how many of second lest available, etc. Take the best time slot according to that criteria. Remove all students that can make that time slot, and apply the same algorithm to the remaining time slots and students, and continue until you've reached your maximum number of time slots. In your example, Frank is the least available student, so 11 am, as the only time slot he can make, is the first choice. This leaves Alice, Bob, and Charlotte without a time slot, and of them, Alice is the least available. 9 am and 10 am both accommodate Alice, so you can take either one (although if you take into account students that were removed in previous steps, then 10 am wins).
You can combine the two: use the heuristic until you get to small enough numbers that you're okay with using brute force.
Another heuristic is to look at clustering (is there one set of students that is mostly available in the morning, and another in the evening), and pick time slots in different clusters.
answered 2 days ago
Acccumulation
5,7642616
add a comment |Â
up vote
8
down vote
With those numbers, brute force is still feasible. You have 30 choose 5 = 142506 different combinations. I don't think there's any algorithm other than brute force that is guaranteed to get the best solution, but one heuristic would be to arrange the students in sets from least availability to most. Then rank time slots by how many of the least available students they match, then break ties by how many of second lest available, etc. Take the best time slot according to that criteria. Remove all students that can make that time slot, and apply the same algorithm to the remaining time slots and students, and continue until you've reached your maximum number of time slots. In your example, Frank is the least available student, so 11 am, as the only time slot he can make, is the first choice. This leaves Alice, Bob, and Charlotte without a time slot, and of them, Alice is the least available. 9 am and 10 am both accommodate Alice, so you can take either one (although if you take into account students that were removed in previous steps, then 10 am wins).
You can combine the two: use the heuristic until you get to small enough numbers that you're okay with using brute force.
Another heuristic is to look at clustering (is there one set of students that is mostly available in the morning, and another in the evening), and pick time slots in different clusters.
answered 2 days ago
Acccumulation
5,7642616
add a comment |Â
up vote
8
down vote
up vote
8
down vote
With those numbers, brute force is still feasible. You have 30 choose 5 = 142506 different combinations. I don't think there's any algorithm other than brute force that is guaranteed to get the best solution, but one heuristic would be to arrange the students in sets from least availability to most. Then rank time slots by how many of the least available students they match, then break ties by how many of second lest available, etc. Take the best time slot according to that criteria. Remove all students that can make that time slot, and apply the same algorithm to the remaining time slots and students, and continue until you've reached your maximum number of time slots. In your example, Frank is the least available student, so 11 am, as the only time slot he can make, is the first choice. This leaves Alice, Bob, and Charlotte without a time slot, and of them, Alice is the least available. 9 am and 10 am both accommodate Alice, so you can take either one (although if you take into account students that were removed in previous steps, then 10 am wins).
You can combine the two: use the heuristic until you get to small enough numbers that you're okay with using brute force.
Another heuristic is to look at clustering (is there one set of students that is mostly available in the morning, and another in the evening), and pick time slots in different clusters.
answered 2 days ago
Acccumulation
5,7642616
With those numbers, brute force is still feasible. You have 30 choose 5 = 142506 different combinations. I don't think there's any algorithm other than brute force that is guaranteed to get the best solution, but one heuristic would be to arrange the students in sets from least availability to most. Then rank time slots by how many of the least available students they match, then break ties by how many of second lest available, etc. Take the best time slot according to that criteria. Remove all students that can make that time slot, and apply the same algorithm to the remaining time slots and students, and continue until you've reached your maximum number of time slots. In your example, Frank is the least available student, so 11 am, as the only time slot he can make, is the first choice. This leaves Alice, Bob, and Charlotte without a time slot, and of them, Alice is the least available. 9 am and 10 am both accommodate Alice, so you can take either one (although if you take into account students that were removed in previous steps, then 10 am wins).
You can combine the two: use the heuristic until you get to small enough numbers that you're okay with using brute force.
Another heuristic is to look at clustering (is there one set of students that is mostly available in the morning, and another in the evening), and pick time slots in different clusters.
answered 2 days ago
Acccumulation
5,7642616
answered 2 days ago
Acccumulation
5,7642616
answered 2 days ago
Acccumulation
5,7642616
answered 2 days ago
Acccumulation
5,7642616
5,7642616
add a comment |Â
add a comment |Â
up vote
3
down vote
Practically speaking, simply vary the office hours each week.
answered yesterday
user38230
462
2
The risk here is low attendance because students end up confused about when your office hours are.
– Misha Lavrov
yesterday
add a comment |Â
up vote
3
down vote
Practically speaking, simply vary the office hours each week.
answered yesterday
user38230
462
2
The risk here is low attendance because students end up confused about when your office hours are.
– Misha Lavrov
yesterday
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Practically speaking, simply vary the office hours each week.
answered yesterday
user38230
462
Practically speaking, simply vary the office hours each week.
answered yesterday
user38230
462
answered yesterday
user38230
462
answered yesterday
user38230
462
answered yesterday
user38230
462
462
2
The risk here is low attendance because students end up confused about when your office hours are.
– Misha Lavrov
yesterday
add a comment |Â
2
The risk here is low attendance because students end up confused about when your office hours are.
– Misha Lavrov
yesterday
2
2
The risk here is low attendance because students end up confused about when your office hours are.
– Misha Lavrov
yesterday
The risk here is low attendance because students end up confused about when your office hours are.
– Misha Lavrov
yesterday
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2912164%2fchoosing-office-hours-to-maximise-number-of-students-who-can-attend-at-least-one%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
8
$binom305$ is just $142506$, which is a small number for a computer. Why not use brute force?
– Misha Lavrov
2 days ago
5
I'm currently writing a program, but I'm also interested in an answer for arbitrarily large problems
– lokodiz
2 days ago
3
Re the formulation: Based on experience, it's much better instead of asking for a hard binary 1/0 is to have them soft-rank each timeslot from 0 (totally impossible, conflict) up to say 3 or 4 (ideal)
– smci
2 days ago
5
Don't start writing your program yet. This open-source program might help you : FET-Free Timetabling software.
– Eric Duminil
yesterday
2
@smci : that solution might also solve a secondary problem: students who do not have that many choices overall might be more important to cover first in an algorithm like Misha's than those available all the time. compare Frank in the example above to Bob/Charlotte/Daniel (those 3 are irrelevant for the solution as they will always be covered when choosing 2 slots of 4).
– Chieron
yesterday