I have non-linear scheduling model and I want to convert it to a linear model. But I have no idea about how can I do it.

The nonlinear constraint is:

For each $i, i'\in I$ and $j, j' \in J$ and $q, q' \in Q$ and $k \in K$

$$s_{ij} \geq (\sum_{q'=q}^5 o_{i'j'q'} * c_{i'j'} * x_{i'j'k}) * x_{ijk}*o_{ijq}$$

In this constraint:

$s$ is continuous positive variable,

$o$ and $x$ are binary variables

I can do the $x_{ijk}*o_{ijq}$ part using a Big M number but I don't know any about the summation inside the paranthesis. How can I do it? Please help.


Expand the summation. You will get something like $\sum c \cdot o \cdot x \cdot x \cdot o$. This is constant * binary * binary * binary * binary. The multiplication of 4 binary variables $y=x_1x_2x_3x_4$ can be linearized as: \begin{align} &y \le x_i \\ &y \ge x_1+x_2+x_3+x_4-3 \\ &y \in \{0,1\} \>\text{(note: $y$ can even be relaxed to continuous)} \end{align} No big-Ms needed I think.

  • $\begingroup$ That's a good solution. You are the only person who answer such questions:) Thanks for all @Erwin. $\endgroup$ – Ali Tor May 24 '16 at 23:29
  • $\begingroup$ By the way, the variable c is not constraint, it is a continuous variable. It was my fault cause I forgot it to add. $\endgroup$ – Ali Tor May 24 '16 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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