1
$\begingroup$

I was wondering, how one would linearize such a constraint, to make it applicable to LPs.

$ a_{i}=(a_{i-1}+b_{i})(1-c_{i})-d_{i}$

$a_i$ gives information of the number of assigned jobs to machine $i$. $b_i$ if machine $i$ performs a job. $c_i$ indicates whether a machine breaks down. $d_i$ if a job is finished.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Can you please tell us, what are your decision variables and are they continuous, binary etc.? $\endgroup$
    – PeterD
    Commented Jan 19 at 9:30
  • $\begingroup$ Just updated the OP! $\endgroup$
    – manofthousandnames
    Commented Jan 19 at 9:37
  • $\begingroup$ Your constraint enforces $a_i=-d_i$ when $c_i=1$. Is that really what you want? From your description, it sounds like $a_i$ is a nonnegative integer and $d_i$ is binary, so that would mean that $a_i=0=d_i$. $\endgroup$
    – RobPratt
    Commented Jan 19 at 15:23
  • $\begingroup$ @manofthousandnames, I am unsure I understand what exactly you mean by defining such a constraint. If $a_i$ is defined as the number of assigned jobs to machine $i$, and also $a_{i-1}$ is referred to the number of assigned jobs to machine $i-1$, then suppose $a_{i-1} = 5$, $b_{i} = 1$, $c_{i} = 0$, and $d_{i} = 1$ then $a_{i} = (5+1).(1) - 1 = 5$. In this manner, the number of assigned jobs to machine $i$ would be $5$, which is incorrect! $\endgroup$
    – A.Omidi
    Commented Jan 20 at 8:18

1 Answer 1

Reset to default
3
$\begingroup$

If I understand correctly, $c_i$ is a binary decision variable that is $1$ if machine $i$ breaks down and $0$ otherwise. Also, I assume that $(a_{i-1}+b_i)$ is non-negative. You can introduce the decision variable $z$ which takes the value of $(a_{i-1}+b_i)(1-c_i)$. You can then introduce the following constraints.

\begin{align} a_{i}=z-d_{i}\newline 0 \leq z \leq a_{i-1}+b_i \newline z \geq (a_{i-1}+b_i)-c_iM \newline z \leq M(1−c_i) \end{align}

The first two constraints are straightforward. In the third constraint, if the machine does not break down, i.e., $c_i = 0$, $z$ is forced to take value $a_{i-1}+b_i$. If the machine breaks down ($c_i = 1$), the RHS becomes negative (where $M$ is a large number) and $z$ will take value $0$, because of the fourth constraint.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Well thought of, Peter $\endgroup$
    – Sutanu Majumdar
    Commented Jan 19 at 11:40
  • $\begingroup$ One thing is if $c_i=0$, no enforcement for $z_i=0$, so need a constraint like $0 \le z_i \le M(1-c_i)$ $\endgroup$
    – Sutanu Majumdar
    Commented Jan 19 at 12:37
  • 1
    $\begingroup$ @SutanuMajumdar I dont believe that is needed. If $c_i = 0$, we have $z \geq a_{i−1}+b_i$ (third constraint) and through the second constraint, $z \leq a_{i−1}+b_i$ still holds. Therefore, $z$ must become $a_{i−1}+b_i$. $\endgroup$
    – PeterD
    Commented Jan 19 at 13:20
  • 1
    $\begingroup$ The $c_i=1$ case is what still needs to be enforced, and the suggestion by @SutanuMajumdar does that. $\endgroup$
    – RobPratt
    Commented Jan 19 at 14:01
  • $\begingroup$ Oh yes, now I see it. I will add that to my answer. Thanks @RobPratt and Sutanu Majumdar. $\endgroup$
    – PeterD
    Commented Jan 19 at 14:18

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.