Thanks in advance for any help, apologies in advance for my ignorance! I am a beginning self-taught dilettante, trying to make a difference at my high school!

We are trying to create a flexible tutorial window that can intelligently schedule students and teachers.

There is time available for tutorials. Teachers of various subjects specify what offerings they are willing to conduct. Students specify what their preferences are among subjects and available kinds of offerings. We want to find what to offer when and who goes to what when. 

My initially favored representation for the decision variables, because it is relatively sparse and implicitly includes important constraints:

• Optional intervals for each teacher offering
• Optional intervals for students, per subject and support type
• Alternatives specified for each student interval determined by the available offerings intervals. So each student can only go to one tutorial

Okay, so solver solves. And I get a list of which intervals actually occur and when, for both sets. BUT I don't know how they match up. Student A may have individual math tutorial at [s,e), but multiple math teachers might have individual tutorials at that time. 

I feel like I am just missing something very basic. My current remedy involves creating attendance arrays, but that seems duplicative.

The thing that is bugging me is that I know the solver made a SPECIFIC assignment from the alternatives for that student when it constructed the solution. And I need access to that, some kind of data trace. But I don't know how. 

Is there a way to get that info? Or is there a fundamental flaw in how I am setting this up? Any suggestions for alternatives? Everything I have so far either massively increases the search space, creates parallel and pointless data structures, or involves recreating all the interval functionality in arrays just so I can see what I need. 

------------------------------
Andrew Milne
------------------------------

#DecisionOptimization

It sounds as though you are thinking about a CP model. Your problem is a variant of what is known in operations research as an (unbalanced) assignment problem, and while it an be solved with a CP model, a linear or integer programming model (using CPLEX rather than CP Optimizer) might be preferable.

I'll start with a simple case, in which each student needs tutoring in only one subject, once per time period (day? week?). We can visualize this as a bipartite graph, as in the following illustration.
Here the S nodes represent two students (student 1 and student 2) and the T nodes represent combinations of teacher (1-3) and time slots when they are available (-1 or -2). An edge represents a compatible assignment: the teacher tutors the subject the student needs, with an appropriate "support type", at a time that works for the student. Where there is no edge, the assignment is forbidden (wrong subject, student cannot make the time slot, student and teacher are incompatible for some reason).

For each edge, the model contains a 0-1 variable indicating whether that assignment is made (1) or not (0). In the standard assignment problem, each student is assigned to exactly one slot (no student goes unassigned) and each teacher can receive at most one assignment in a given time slot, but those constraints can easily be relaxed to allow some students not to be assigned (due to lack of capacity or compatible options) and to allow group tutoring sessions (say, teacher 3 at time 1 can handle up to five students).

In the simplest case, the objective of the model can be to maximize the number of assignments that are made. A more nuanced approach would be to assign a compatibility score to each edge (some function of how convenient the time slot is for the student, how badly the student needs tutoring in that subject, ...) and maximize the overall compatibility of the assignments. Additional constraints are also possible. For instance, teacher 1 might be available at six different times (so is represented by nodes T1-1 ... T1-6) but is only willing to take on three students (so only combinations of at most three of those six nodes can receive assignments).

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

Thank you so much for your reply, and my apologies for my late acknowledgement of it! I am new to the IBM Community boards, and expected some notification on my home page, and thus didn't know you had responded!

My thinking was moving in the direction you suggested, and a way forward is much clearer now. I was hoping to use the "interval" structure, because it would make it easier to add some more sophistication to the model later - in particular, transition times. But it may be that if I want that I will have to code it up in an integer model.

Thanks again for your time and the clarity of your explanation!

------------------------------
Andrew Milne
------------------------------

Original Message:
Sent: Tue June 08, 2021 04:30 PM
From: Paul Rubin
Subject: Scheduling/Alternatives Issue

It sounds as though you are thinking about a CP model. Your problem is a variant of what is known in operations research as an (unbalanced) assignment problem, and while it an be solved with a CP model, a linear or integer programming model (using CPLEX rather than CP Optimizer) might be preferable.

I'll start with a simple case, in which each student needs tutoring in only one subject, once per time period (day? week?). We can visualize this as a bipartite graph, as in the following illustration.

Here the S nodes represent two students (student 1 and student 2) and the T nodes represent combinations of teacher (1-3) and time slots when they are available (-1 or -2). An edge represents a compatible assignment: the teacher tutors the subject the student needs, with an appropriate "support type", at a time that works for the student. Where there is no edge, the assignment is forbidden (wrong subject, student cannot make the time slot, student and teacher are incompatible for some reason).

For each edge, the model contains a 0-1 variable indicating whether that assignment is made (1) or not (0). In the standard assignment problem, each student is assigned to exactly one slot (no student goes unassigned) and each teacher can receive at most one assignment in a given time slot, but those constraints can easily be relaxed to allow some students not to be assigned (due to lack of capacity or compatible options) and to allow group tutoring sessions (say, teacher 3 at time 1 can handle up to five students).

In the simplest case, the objective of the model can be to maximize the number of assignments that are made. A more nuanced approach would be to assign a compatibility score to each edge (some function of how convenient the time slot is for the student, how badly the student needs tutoring in that subject, ...) and maximize the overall compatibility of the assignments. Additional constraints are also possible. For instance, teacher 1 might be available at six different times (so is represented by nodes T1-1 ... T1-6) but is only willing to take on three students (so only combinations of at most three of those six nodes can receive assignments).

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

The other issue that I am having trouble with is this: if I am to frame this as a integer assignment problem rather than an interval problem, then I only seem to be able to vary one side of the schedule.

Let me explain. The problem I am seeking to solve is to create both teacher and student schedules. The simple model starts with "These are the available tutorials and their (fixed) times. What I am hoping for is more complicated. On the interval model, I could just create, as a decision variable, something meaning "Teacher 1 will hold up to three individual tutorials of length l" and "Teacher 2 will hold up to two group tutorials of capacity c and length l" within some window of time. But exactly when those are held is open and to be decided, based on student needs, other teacher's availabilities, and the optimization process. I am not sure what the data structure looks like to recreate that outside of intervals. Do I just create every single possible tutorial time for each teacher and then select, say, up to three of them? (And it may be that I am being too optimistic about the complexity of the problems I can solve!)

------------------------------
Andrew Milne
------------------------------

Original Message:
Sent: Mon June 21, 2021 02:05 PM
From: Andrew Milne
Subject: Scheduling/Alternatives Issue

Thank you so much for your reply, and my apologies for my late acknowledgement of it! I am new to the IBM Community boards, and expected some notification on my home page, and thus didn't know you had responded!

My thinking was moving in the direction you suggested, and a way forward is much clearer now. I was hoping to use the "interval" structure, because it would make it easier to add some more sophistication to the model later - in particular, transition times. But it may be that if I want that I will have to code it up in an integer model.

Thanks again for your time and the clarity of your explanation!

------------------------------
Andrew Milne
------------------------------


Original Message:
Sent: Tue June 08, 2021 04:30 PM
From: Paul Rubin
Subject: Scheduling/Alternatives Issue

It sounds as though you are thinking about a CP model. Your problem is a variant of what is known in operations research as an (unbalanced) assignment problem, and while it an be solved with a CP model, a linear or integer programming model (using CPLEX rather than CP Optimizer) might be preferable.

I'll start with a simple case, in which each student needs tutoring in only one subject, once per time period (day? week?). We can visualize this as a bipartite graph, as in the following illustration.

Here the S nodes represent two students (student 1 and student 2) and the T nodes represent combinations of teacher (1-3) and time slots when they are available (-1 or -2). An edge represents a compatible assignment: the teacher tutors the subject the student needs, with an appropriate "support type", at a time that works for the student. Where there is no edge, the assignment is forbidden (wrong subject, student cannot make the time slot, student and teacher are incompatible for some reason).

For each edge, the model contains a 0-1 variable indicating whether that assignment is made (1) or not (0). In the standard assignment problem, each student is assigned to exactly one slot (no student goes unassigned) and each teacher can receive at most one assignment in a given time slot, but those constraints can easily be relaxed to allow some students not to be assigned (due to lack of capacity or compatible options) and to allow group tutoring sessions (say, teacher 3 at time 1 can handle up to five students).

In the simplest case, the objective of the model can be to maximize the number of assignments that are made. A more nuanced approach would be to assign a compatibility score to each edge (some function of how convenient the time slot is for the student, how badly the student needs tutoring in that subject, ...) and maximize the overall compatibility of the assignments. Additional constraints are also possible. For instance, teacher 1 might be available at six different times (so is represented by nodes T1-1 ... T1-6) but is only willing to take on three students (so only combinations of at most three of those six nodes can receive assignments).

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Within the framework of an integer programming model, you can set up a "sink" (let's call it a "session") for each combination of teacher and time window the teacher would be willing to accept. Each session would have a capacity limit as defined by the teacher. If the same teacher is willing to tutor different subjects, you would have a session for each combination of teacher, time slot and subject. So teacher A might have an American History session on Wednesday from 3:00 to 4:00 pm, an American History session on Wednesday from 3:30 to 4:30 pm, and a European History session on Wednesday from 3:00 to 4:00 pm.

You would then define a binary variable for each of those sessions indicating whether or not it was offered. Constraints would prevent you from actually using more sessions from a single instructor than they are willing to offer, and from using two sessions from the same instructor that would overlap in time. You would also have binary variables for each combination of a student and a session they might want. (You do not need variables for combinations that can be ruled out a priori, because the student is not interested in the tutorial subject, cannot make the session time, or is incompatible with the session instructor.) If x[i][j] is the binary variable for assigning student i to session j (1 if the assignment is made, 0 if not) and y[j] is the binary variable for offering session j (1 if the session is offered, 0 if not), the constraint x[i][j] <= y[j] ensures that the assignment is not made unless the session is offered.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

Original Message:
Sent: Mon June 21, 2021 02:18 PM
From: Andrew Milne
Subject: Scheduling/Alternatives Issue

The other issue that I am having trouble with is this: if I am to frame this as a integer assignment problem rather than an interval problem, then I only seem to be able to vary one side of the schedule.

Let me explain. The problem I am seeking to solve is to create both teacher and student schedules. The simple model starts with "These are the available tutorials and their (fixed) times. What I am hoping for is more complicated. On the interval model, I could just create, as a decision variable, something meaning "Teacher 1 will hold up to three individual tutorials of length l" and "Teacher 2 will hold up to two group tutorials of capacity c and length l" within some window of time. But exactly when those are held is open and to be decided, based on student needs, other teacher's availabilities, and the optimization process. I am not sure what the data structure looks like to recreate that outside of intervals. Do I just create every single possible tutorial time for each teacher and then select, say, up to three of them? (And it may be that I am being too optimistic about the complexity of the problems I can solve!)

------------------------------
Andrew Milne
------------------------------


Original Message:
Sent: Mon June 21, 2021 02:05 PM
From: Andrew Milne
Subject: Scheduling/Alternatives Issue

Thank you so much for your reply, and my apologies for my late acknowledgement of it! I am new to the IBM Community boards, and expected some notification on my home page, and thus didn't know you had responded!

My thinking was moving in the direction you suggested, and a way forward is much clearer now. I was hoping to use the "interval" structure, because it would make it easier to add some more sophistication to the model later - in particular, transition times. But it may be that if I want that I will have to code it up in an integer model.

Thanks again for your time and the clarity of your explanation!

------------------------------
Andrew Milne


Original Message:
Sent: Tue June 08, 2021 04:30 PM
From: Paul Rubin
Subject: Scheduling/Alternatives Issue

It sounds as though you are thinking about a CP model. Your problem is a variant of what is known in operations research as an (unbalanced) assignment problem, and while it an be solved with a CP model, a linear or integer programming model (using CPLEX rather than CP Optimizer) might be preferable.

I'll start with a simple case, in which each student needs tutoring in only one subject, once per time period (day? week?). We can visualize this as a bipartite graph, as in the following illustration.

Here the S nodes represent two students (student 1 and student 2) and the T nodes represent combinations of teacher (1-3) and time slots when they are available (-1 or -2). An edge represents a compatible assignment: the teacher tutors the subject the student needs, with an appropriate "support type", at a time that works for the student. Where there is no edge, the assignment is forbidden (wrong subject, student cannot make the time slot, student and teacher are incompatible for some reason).

For each edge, the model contains a 0-1 variable indicating whether that assignment is made (1) or not (0). In the standard assignment problem, each student is assigned to exactly one slot (no student goes unassigned) and each teacher can receive at most one assignment in a given time slot, but those constraints can easily be relaxed to allow some students not to be assigned (due to lack of capacity or compatible options) and to allow group tutoring sessions (say, teacher 3 at time 1 can handle up to five students).

In the simplest case, the objective of the model can be to maximize the number of assignments that are made. A more nuanced approach would be to assign a compatibility score to each edge (some function of how convenient the time slot is for the student, how badly the student needs tutoring in that subject, ...) and maximize the overall compatibility of the assignments. Additional constraints are also possible. For instance, teacher 1 might be available at six different times (so is represented by nodes T1-1 ... T1-6) but is only willing to take on three students (so only combinations of at most three of those six nodes can receive assignments).

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University

Thanks! That is very helpful

------------------------------
Andrew Milne
------------------------------

Original Message:
Sent: Mon June 21, 2021 02:31 PM
From: Paul Rubin
Subject: Scheduling/Alternatives Issue

Within the framework of an integer programming model, you can set up a "sink" (let's call it a "session") for each combination of teacher and time window the teacher would be willing to accept. Each session would have a capacity limit as defined by the teacher. If the same teacher is willing to tutor different subjects, you would have a session for each combination of teacher, time slot and subject. So teacher A might have an American History session on Wednesday from 3:00 to 4:00 pm, an American History session on Wednesday from 3:30 to 4:30 pm, and a European History session on Wednesday from 3:00 to 4:00 pm.

You would then define a binary variable for each of those sessions indicating whether or not it was offered. Constraints would prevent you from actually using more sessions from a single instructor than they are willing to offer, and from using two sessions from the same instructor that would overlap in time. You would also have binary variables for each combination of a student and a session they might want. (You do not need variables for combinations that can be ruled out a priori, because the student is not interested in the tutorial subject, cannot make the session time, or is incompatible with the session instructor.) If x[i][j] is the binary variable for assigning student i to session j (1 if the assignment is made, 0 if not) and y[j] is the binary variable for offering session j (1 if the session is offered, 0 if not), the constraint x[i][j] <= y[j] ensures that the assignment is not made unless the session is offered.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------


Original Message:
Sent: Mon June 21, 2021 02:18 PM
From: Andrew Milne
Subject: Scheduling/Alternatives Issue

The other issue that I am having trouble with is this: if I am to frame this as a integer assignment problem rather than an interval problem, then I only seem to be able to vary one side of the schedule.

Let me explain. The problem I am seeking to solve is to create both teacher and student schedules. The simple model starts with "These are the available tutorials and their (fixed) times. What I am hoping for is more complicated. On the interval model, I could just create, as a decision variable, something meaning "Teacher 1 will hold up to three individual tutorials of length l" and "Teacher 2 will hold up to two group tutorials of capacity c and length l" within some window of time. But exactly when those are held is open and to be decided, based on student needs, other teacher's availabilities, and the optimization process. I am not sure what the data structure looks like to recreate that outside of intervals. Do I just create every single possible tutorial time for each teacher and then select, say, up to three of them? (And it may be that I am being too optimistic about the complexity of the problems I can solve!)

------------------------------
Andrew Milne


Original Message:
Sent: Mon June 21, 2021 02:05 PM
From: Andrew Milne
Subject: Scheduling/Alternatives Issue

Thank you so much for your reply, and my apologies for my late acknowledgement of it! I am new to the IBM Community boards, and expected some notification on my home page, and thus didn't know you had responded!

My thinking was moving in the direction you suggested, and a way forward is much clearer now. I was hoping to use the "interval" structure, because it would make it easier to add some more sophistication to the model later - in particular, transition times. But it may be that if I want that I will have to code it up in an integer model.

Thanks again for your time and the clarity of your explanation!

------------------------------
Andrew Milne


Original Message:
Sent: Tue June 08, 2021 04:30 PM
From: Paul Rubin
Subject: Scheduling/Alternatives Issue

It sounds as though you are thinking about a CP model. Your problem is a variant of what is known in operations research as an (unbalanced) assignment problem, and while it an be solved with a CP model, a linear or integer programming model (using CPLEX rather than CP Optimizer) might be preferable.

I'll start with a simple case, in which each student needs tutoring in only one subject, once per time period (day? week?). We can visualize this as a bipartite graph, as in the following illustration.

Here the S nodes represent two students (student 1 and student 2) and the T nodes represent combinations of teacher (1-3) and time slots when they are available (-1 or -2). An edge represents a compatible assignment: the teacher tutors the subject the student needs, with an appropriate "support type", at a time that works for the student. Where there is no edge, the assignment is forbidden (wrong subject, student cannot make the time slot, student and teacher are incompatible for some reason).

For each edge, the model contains a 0-1 variable indicating whether that assignment is made (1) or not (0). In the standard assignment problem, each student is assigned to exactly one slot (no student goes unassigned) and each teacher can receive at most one assignment in a given time slot, but those constraints can easily be relaxed to allow some students not to be assigned (due to lack of capacity or compatible options) and to allow group tutoring sessions (say, teacher 3 at time 1 can handle up to five students).

In the simplest case, the objective of the model can be to maximize the number of assignments that are made. A more nuanced approach would be to assign a compatibility score to each edge (some function of how convenient the time slot is for the student, how badly the student needs tutoring in that subject, ...) and maximize the overall compatibility of the assignments. Additional constraints are also possible. For instance, teacher 1 might be available at six different times (so is represented by nodes T1-1 ... T1-6) but is only willing to take on three students (so only combinations of at most three of those six nodes can receive assignments).

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University