# How do I linearize such a constraint?

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.

• Can you please tell us, what are your decision variables and are they continuous, binary etc.? Jan 19 at 9:30
• Just updated the OP! Jan 19 at 9:37
• 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$. Jan 19 at 15:23
• @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! Jan 20 at 8:18

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.
• 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)$ Jan 19 at 12:37
• @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$. Jan 19 at 13:20
• The $c_i=1$ case is what still needs to be enforced, and the suggestion by @SutanuMajumdar does that. Jan 19 at 14:01