2

I wrote different constraints for a problem and some people say that these constraints are not-linear.

My own feeling is that my constraints are linear. Can you help me to prove that?

My first constraint: $$ \sum_{i=1}^{g} \prod_{k=1}^{n} X_{ijk} = 1 ;\forall j=1\dots m $$ with this boolean variable: $$ X_{ijk} = \begin{cases} 1 & \text{ if true } \\ 0 & \text{ otherwise} \end{cases} $$

My second constraint: $$ \sum_{i=1}^{g} \sum_{j=1}^{m} \prod_{k=1}^{n} X_{ijk} = 1 $$

Like these constraints are based on boolean variable {0;1}, then these constraints are linear because each member of the multiplications can not have a value greater than 1. Is that proof is correct?

celtschk
  • 43,384
AkrogAmes
  • 23
  • 3
    Is $\displaystyle\sum_{i=1}^g\displaystyle\sum_{j=1}^m\displaystyle\prod_{k=1}^n X_{ijk} + \displaystyle\sum_{i=1}^g\displaystyle\sum_{j=1}^m\displaystyle\prod_{k=1}^n Y_{ijk} = \displaystyle\sum_{i=1}^g\displaystyle\sum_{j=1}^m\displaystyle\prod_{k=1}^n (X_{ijk} + Y_{ijk})$? If yes, then your constraints are linear, else no. – Sarvesh Ravichandran Iyer Sep 10 '16 at 07:50
  • Also, if $X_{ijk}=1$ and $X_{ijl}=1$, is $X_{ijk}+X_{ijl}\in{0,1}$? – celtschk Sep 10 '16 at 08:04
  • For my first constraint: $$ \sum_{i=1}^{g} \prod_{k=1}^{n} X_{ijk} = 1 ;\forall j=1\dots m $$

    In the worst case i can have that : 1 + 1 + ... + 1 with number of additions = g.

    For my second constraint that is more complex :

     – AkrogAmes Sep 10 '16 at 08:44
  • For my second constraint that is more complex. To think about my second constraint is maybe not-linear. It is an exponential function, I think.

    No, celtschk, the sum can be greater than 1 if you make an addition. Just variable X is boolean, then if you take $X_1 + X_2 = 2 $.

     – AkrogAmes Sep 10 '16 at 08:54
  • No, these constraints are not linear. Linear equality constraints would have the form $Ax=b$, where the vector $x$ is the optimization variable and $A$ is a matrix. – littleO Sep 10 '16 at 21:06

1 Answers1

2

Obviously a product of decision variables is not linear. I.e. you can't just give this to a linear programming (LP) solver. However a product of binary variables can be easily linearized. The expression $v_{i,j}=\prod_{k=1}^n x_{i,j,k}$ with $x_{i,j,k}\in \{0,1\}$ can be expressed as a set of linear inequalities: $$\begin{align} &v_{i,j}\le x_{i,j,k}\\ &v_{i,j}\ge \sum_{k=1}^n x_{i,j,k}-(n-1)\\ &v_{i,j} \in \{0,1\} \end{align}$$ We can even relax $v_{i,j}$ to be continuous between zero and one: $v_{i,j}\in[0,1]$.

Erwin Kalvelagen
  • 4,267
  • Thank you Erwin. I will come back to you when I translated my two constraints in linear format. Have you an explanation or a website that explains why a product of decision variables is not linear? I try to understand ... – AkrogAmes Sep 10 '16 at 18:29
  • 1
    Wow, this is a question I don't often see as it is so basic. You must have slept through quite a few classes. A linear constraint has (by definition) the form $\sum_j a_j x_j {\le,=,\ge} b$ where $a_j$ and $b$ are constants. Obviously a term $x_i x_j$ does not belong in a linear constraint. A linear function $f$ has constant partial derivatives $\frac{\partial f}{\partial x_j}=a_j$ (this is exploited by LP solvers) while $x_i x_j$ has partial derivatives that are not constant. – Erwin Kalvelagen Sep 10 '16 at 20:04
  • Hello Erwin, Before I did not like math, then it's true that this class was not perfect. Now, I try to fix my weaknesses. Thank you. You are a good teacher.

    I have this constraint : $\sum_{i=1}^{g} \prod_{k=1}^{n} X_{ijk} = 1$ and I want linearized this one. So I get this : $\sum_{i=1}^{g} \upsilon {ijk} = 1$. I do what you said, and I get two another constraints : $$ \begin{matrix} \upsilon _{ijk} \leq X{ijk}; \forall k=1\dots n \ \upsilon {ijk} \geq \sum{k=1}^{n} X_{ijk} - (n -1) \ \upsilon _{ijk} \in {0,1} \end{matrix} $$

    It's correct ?

     – AkrogAmes Sep 11 '16 at 09:54
  • Not completely. To be precise we have $v_{i,j} \le x_{i,j,k}> \forall{i,j,k}$. – Erwin Kalvelagen Sep 11 '16 at 17:25