hopefully I can get some help on this problem, it's got me quite stumped.
I was given a linear programming problem with the goal of minimizing labor costs. The variables x_t represent the number of workers available in month t (t = 1, 2, …, 12), while o_t represents how many of the workers can work overtime hours in month t. The problem has two constraints on overtime:
"Overtime may not exceed 10% of straight time production in any month, and overtime may not be scheduled for more than two consecutive months."
I've got the 10% restriction done, but I absolutely cannot figure out how to make the constraint for consecutive months. I have a feeling that I need to use binary variables, i.e., if y_t represents whether or not overtime was activated in month t (t = 3, … 12), and y_t is either 0 or 1, then y_t-2 + y_t-1 + y_t ≤ 2. But I can't figure out how to tie this into my overtime constraint.
I appreciate any help I can get. Thank you.
EDIT:
Right now my 10% constraint is: o_t ≤ 0.1*x_t for t = 1, 2, …, 12
Best Answer
You have an if/then constraint, which is if '$O_t \gt 0$ then $y_t = 1$'.
If P then Q is equivalent to (not P) or Q and so we have
$O_t \le 0$ or $y_t = 1$.
Why not $O_t = 0$ instead of $O_t \le 0$?
We will need to add the constraint $O_t \ge 0$ anyway, so this is covered. Later on it will become clear (Godwilling) why we use $O_t \le 0$ rather than $O_t = 0$.
The standard way of dealing with an either X or Y constraint like this (where X and Y are constraints involving integer variables) is to add these 2 constraints:
$O_t \le M_1 \delta$ (where $\delta $ is a binary variable and we choose the constant $M_1$ according to the problem after thinking about it).
$-y_t \le \ M_2(1-\delta)$ (however, since $y_t$ is a binary rather than an integer variable, it's necessary to adapt the method at this point to fit the problem). Since the only possible values for $y_t$ are 0 and 1, why not just try the following:
$y_t = \delta$.
If $\delta = 0$, $O_t \le 0$ (from constraint 1) and so $O_t = 0$ (from non-negativity contraint).
$\delta = 0$ sets $y_t$ to $0$ in the second constraint.
If $\delta = 1$, the first constraint becomes $O_t \le M_1$. What should we choose $M_1$ to be? So as to allow our solution method to consider all possible values of $O_t$ and choose the optimal one, choose $M_1$ to be 0.1 $\times S_t$, where $S_t$ is the value of the straight time production for month t.
$\delta = 1$ sets $y_t$ to 1 as well, as required.
At this point, I realised that since the second constraint tell us that $y_t = \delta$, we don't really need it. We can just replace the binary variable $\delta $ by $y_t$ itself and have just the first constraint (changing $M_1$ to $M$):
$O_t \le My_t$ where M = 0.1 $\times$ straight time production for month t.
The method you use to solve it will now be able to compare the following 2 possibilites and find which produces the optimal solution. To be rigorous, let's just make sure the constraints are all covered:
case 1: $y_t = 0$
Since $y_t$ = 0, we need $O_t = 0$ which it is when $y_t = 0$ is substituted into $O_t \le My_t$.
case 1: $y_t = 1$
Now we just need $O_t \le 0.1S_t$, precisely what we get by substituting $y_t = 1$ into the constraint.