2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\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
  • $\begingroup$ In my case it was like this z1 = x0 * y1, i convert to linear equation like z1 ≤ x1 and z1 ≥ x0 + y0 -1 . zi, xi, yi belongs to binary {0,1} is it correct can we write like this? $\endgroup$ – smsivaprakaash Feb 2 at 10:17
  • $\begingroup$ @smsivaprakaash You notation is way too sloppy to answer this (x0 vs x1??). You probably should ask again but a bit more precisely. $\endgroup$ – Erwin Kalvelagen Feb 3 at 6:33

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.