I'm trying to create a linear program to solve a scheduling problem, below is a description of the problem, I'll try my best to keep it short but comprehensive.
The core of the problem is that a daily roster needs to be created where each student is matched with exactly one mentor. In this scenario there are $N$ students and $M$ mentors where M > N, so a solution is basically always possible. In addition, a student-mentor pair should be unlikely (but not impossible) to repeat.
At first I created a very simple model that looks like this:
$$ \max \sum_{n=1}^N \sum_{m=1}^M a_{n,m} x_{n,m} $$
Where $a_{n,m}$ is the weight for a particular pair and $x_{n,m}$ is either $0$ or $1$. For each student $i$ constraint is added that looks like:
$$ \sum_{m=1}^M x_{i,m} = 1 $$
And for each mentor $i$ a constraint is added:
$$ \sum_{n=1}^N x_{n,i} \le 1 $$
These constraints ensure that each student is paired with exactly one mentor and each mentor is paired with at most one student (there are more mentors than students).
The weights ($a_{n,m}$) are initially set to some arbitrary value e.g. $1$. On subsequent days the weights are altered with an exponential decay component that makes it less likely for a pair to occur on consecutive days.
This model is incomplete however, some mentors are also teachers and some students may opt to receive one or more teaching days. In the current model the person who uses the system will manually set those teaching days, and on those days the particular student-teacher pair gets a high weight (e.g. $10$), which all but guarantees that the student-teacher pair is selected for that day. However, a much nicer solution would be to include those teaching days as constraints and generated the rosters for the entire week at once. The model would look like this:
$$ \max \sum_{d=1}^7 \sum_{n=1}^N \sum_{m=1}^M a_{d,n,m} x_{d,n,m} + \sum_{d=1}^7 \sum_{n=1}^N \sum_{t=1}^T a_{d,n,t} x_{d,n,t} $$
Where $T$ is the number of teachers. In this case a constraint would be added for all students $i$ who have opted for teaching days:
$$ \sum_{d=1}^7 \sum_{t=1}^T x_{d,i,t} \ge D $$
where $D$ is the number of teaching days selected ($\>= D$ because teachers are mentors as well. In addition the two sets of constraints listed above would be added as well as a set of constraints that ensure that each teacher has at most one student on each day.
The latter solution is much nicer in my opinion, because it requires far less input from the user. However, I cannot figure out a way to add the exponential decay in this model. So my question is, in the latter model, how do I add a constraint or alter the model such that it becomes unlikely (but not impossible) for a student-mentor or student-teacher pair to occur on consecutive days?
I realize this is a bit much to take in, and I would be happy to clarify any parts of the question that are not clear.
I've tried making a model for each day, as explained above, this works but is incomplete. Also I've created the latter model, which makes a roster for each day of the week at once, but I can't figure out how to add the decay constraint.
I'm assuming $d=1,\dots, 7$ refers to days. (You never stated that in the question.) Rather than "exponential decay", you could add a penalty term $-\sum_{d=2}^7 b_{n,m}y_{d,n,m}$ where $b_{n,m} > 0$ is the penalty for assigning student $n$ to teacher/mentor $m$ on consecutive days $d-1$ and $d$ and $y_{d,n,m}$ is a binary variable indicating that this happened. The constraints to define the $y$ variables would be $$y_{d,n,m}\ge x_{d-1,n,m} + x_{d,n,m} - 1\quad\forall d>1,\forall n,\forall m.$$ The solver will want to make $y_{d,n,m} = 0$ where possible (to avoid the penalty); the constraint will force it to be 1 if both $x_{d-1,n,m}$ and $x_{d,n,m}$ are 1.