1

I have the following constraint that I need to write in an optimization problem but I failed to do it.

Let $x_{ij}$ be a binary variable. So that:

$$ x_{ij} = \begin{cases} 1, & \text{if $i$ and $j$ are in the same group}\\ 0, & \text{otherwise} \end{cases} $$

Now I need to write the constraint that if $x_{ij}=1$ and $x_{ik}=1$ then $x_{jk}=1$.

I wrote it as follows: $x_{jk}=x_{ij}\cdot x_{ik}$. But this is obviously wrong because when $x_{jk}=1$ and $x_{ij}=0$ and $x_{ik}=0$ I will get $1=0$.

Michael Hardy
  • 1
Chiba
  • 181
  • 4
    Would inequalities be acceptable as constraints? Specifically I think $x_{ij}x_{jk} \le x_{ik}$ would work. – celtschk Sep 07 '14 at 17:59
  • Your own claim that the simple (and correct) model $x_{jk}=x_{ij}x_{ik}$ is obviously wrong, is weird. The fact that you get an inconsistent equation is exactly what you want. That case should not be able to happen, hence, it has to lead to an infeasible equation. Assuming that you are modelling if and only if, i.e., $x_{jk} = x_{ij}$ AND $x_{ik}$, this is simply $x_{ij}x_{ik}$, but much better implemented using the linear inequalities in my answer below. – Johan Löfberg Sep 08 '14 at 05:33
  • In my claim, I can get $j$ and $k$ in the same group and $i$ in another group. This means, $x_{jk}=1$ and $x_{ik}=0$ and $x_{ij}=0$ but $x_{jk}\neq x_{ij}\cdot x_{ik}$ which make the claim correct. The problem is that the model is $x_{jk}=x_{ij}\land x_{ik}$ or $x_{jk}=\neg (x_{ij}\oplus x_{ik})$ depending on either $i$ is alone in one group or $i$ is with $j$ and with $k$ together in the same group. – Chiba Sep 08 '14 at 15:21
  • I think the correct answer would be (as celtschk suggested): $x_{jk}\geqslant x_{ij}\cdot x_{ik}$. – Chiba Sep 08 '14 at 15:23
  • As the problem now is specified in the comment above to be about modelling of logical and, and negated xor, I have updated my answer below to describe that. – Johan Löfberg Sep 08 '14 at 18:05

2 Answers2

2

To avoid all the indexing, I simply use the variables $a$, $b$, $c$ as tokens for $x_{ij}$, $x_{ik}$ and $x_{jk}$

Linear representation of $c = a \land b$

$a \geq c, b \geq c, c \geq a+b-1$

Linear representation of $c = \lnot (a \oplus b)$

$c \leq 1-a+b, c \leq 1+a-b, c \geq 1-a-b, c \geq a+b-1$

You do not want to introduce any bilinear products as that unnecessarily renders the problem much harder to solve (more precisely, it will not be possible to use mixed-integer linear programming in this case)

Johan Löfberg
  • 9,497
  • 1
  • 15
  • 15
  • Please, do you know how to linearize $a\cdot b \leqslant c$ ? – Chiba Sep 08 '14 at 21:25
  • You mean for binary variables I hope (otherwise it is impossible). $c \geq a+b -1$. That is what is used in both models to ensure $c$ is true when both $a$ and $b$ are true. – Johan Löfberg Sep 09 '14 at 05:51
0

I would add two constraints:

$x_{ij}\cdot x_{jk} \leq x_{ik} \quad (1)$

$x_{ij}+x_{jk}+x_{ik} \geq 1 \quad (2)$

If $x_{ij}=0$ and $x_{jk}=0$, then $x_{ik}=1$ Without the second constraint, $x_{ik}$ could be also equal to 0.

If $x_{ij}=1$ and $x_{jk}=0$, then $x_{ik}=0$

If $x_{ij}=0$ and $x_{jk}=1$, then $x_{ik}=0$

If $x_{ij}=1$ and $x_{jk}=1$, then $x_{ik}=1$

callculus42
  • 30,550
  • Two problems with this model. First, you introduce a bilinear term which one typically should try to avoid as far as possible. Second, nothing in the question says that some of the three variables always has to be 1, as you enforce with your second constraint, nor is there any reason to have that inequality. Once you've allowed your self to use the bilinear term, you can just as well change the inequality to an equality and use the obvious model for $c=(a$ AND $b)$, i.e., $c = ab$, as done in the original post. – Johan Löfberg Sep 08 '14 at 05:40
  • @JohanLöfberg It was my interpretation of the post. The OP can clarify it. – callculus42 Sep 08 '14 at 06:57