0
$\begingroup$

I have these two constraints, where the indices are $i$ person, $j$ shift and $t$, the day. $x_{ijt}$ is the shift assignment, $m_{ijt}$ the motivation of the person in a shift (only takes values $m_{ijt}>0$ if the corresponding value of $x_{ijt}=1$, otherwise $m_{ijt}=0$) and the slack $s^+_{jt}$. The first constraint ensures that demand is met and the second that if demand is greater than 0, then at least one person works and therefore not everything falls into the slack variable. Is it possible to combine both constraints into one constraint? The reasons for this do not matter for now.

$$ \begin{align} &\sum_{i}^{}m_{ijt}+s^+_{jt}\ge Demand_{jt}&\forall j,t\\ &\sum_{i}^{}x_{ijt}\ge 0.1\cdot Demand_{jt}&\forall j,t \end{align} $$

Improve this question
$\endgroup$
7
  • $\begingroup$ You still want a linear constraint right? If this does not matter for you, you could multiply the two left hand sides with each other and have the demand on the right hand side. $\endgroup$
    – PeterD
    Commented May 23 at 20:10
  • $\begingroup$ Yes, it should be linear $\endgroup$
    – nflgreaternba
    Commented May 23 at 20:25
  • $\begingroup$ Is $m_{ijt}$ a variable or a predefined parameter. It seems a bit odd that the model determines each person’s motivation for taking a given shift at a certain day. $\endgroup$
    – Sune
    Commented May 23 at 20:40
  • $\begingroup$ It is a variable. $\endgroup$
    – nflgreaternba
    Commented May 23 at 20:45
  • 2
    $\begingroup$ Why do you want to combine the constraints into one? From a practical perspective it is often better to just have more constraints. If you observe specific performance issues, we might be able to help with those. $\endgroup$
    – Kevin Dalmeijer
    Commented May 23 at 21:05

2 Answers 2

Reset to default
0
$\begingroup$

I wonder if the second constraint can be replaced by a simple upper bound on $s^+_{jt}$? Something like

$$ \begin{align} &\sum_{i}^{}m_{ijt}+s^+_{jt}\ge Demand_{jt}&\forall j,t\\ &s^+_{jt} \leq \alpha_{i,t}&\forall j,t\\ \end{align} $$

where $\alpha_{i,t} = \max\left(\frac{1}{2} Demand_{jt},\; Demand_{jt}-\epsilon\right)$ for some significant but small $\epsilon > 0$. This specific choice of constant, $\alpha_{i,t}$, implies that $$\sum_{i}^{}m_{ijt} \geq \min\left(\frac{1}{2} Demand_{jt},\; \epsilon\right)$$

which is positive when $Demand_{jt} > 0$ and zero when $Demand_{jt} = 0$. This has the desired effect that when $Demand_{jt} > 0$, at least one of the $m_{ijt}$ in the summation must be positive, which implies that at least one $x_{ijt}=1$, by the relationship you mentioned:

[motivation] only takes values $m_{ijt}>0$ if the corresponding value of $x_{ijt}=1$, otherwise $m_{ijt}=0$) and the slack $s^+_{jt}$.

Improve this answer
$\endgroup$
0
$\begingroup$

Assuming that for fixed $j$ and $t$ there is a lower bound $L_{jt}>0$ on the motivation of anyone assigned to a shift (0.1 is suggested in a comment), the second constraint can be replaced by an upper bound on the slack: $s_{jt}^+ \le Demand_{jt} - L_{jt}.$ That will force nonzero total motivation whenever demand is positive, and nonzero motivation will force at least one assignment given that $x_{ijt}=0\implies m_{ijt}=0.$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks Mr. Rubin. Assuming I have a decomposed model, and I want to add this constraint on the slack to the Master Problem. Do I then need to add the duals of this constraint to the objective of the Subproblems aswell, or is it just a bound rather than a constraint? $\endgroup$
    – nflgreaternba
    Commented May 25 at 9:29
  • $\begingroup$ You would need to include the dual prices for the upper bounds in the subproblems. You can get them from the reduced costs (orinanobworld.blogspot.com/2010/09/…). $\endgroup$
    – prubin ♦
    Commented May 25 at 16:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.