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.

$\endgroup$
4
  • 1
    $\begingroup$ Can you please tell us, what are your decision variables and are they continuous, binary etc.? $\endgroup$
    – PeterD
    Jan 19 at 9:30
  • $\begingroup$ Just updated the OP! $\endgroup$ 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
    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
    Jan 20 at 8:18

1 Answer 1

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.

$\endgroup$
5
  • $\begingroup$ Well thought of, Peter $\endgroup$ 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$ 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
    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
    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
    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.