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$

1 Answer 1

Reset to default
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$
4
  • $\begingroup$ That's a good solution. You are the only person who answer such questions:) Thanks for all @Erwin. $\endgroup$ Commented May 24, 2016 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$ Commented May 24, 2016 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$ Commented Feb 2, 2020 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$ Commented Feb 3, 2020 at 6:33

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.