1
$\begingroup$

I have an integer program with binary variables $x_{i,j,k}\in \{ 0,1 \}$.

For all $k$, I have that $\sum_i \sum_j =2$. I want to add a constraint that says if $x_{i_0,j,k}$ is equal to $1$ for some $i_0$ and a fixed $j$ and $k$, then $x_{i_1,j,k}$ must also equal to $1$ for some $i_1\neq i_0$ for the same fixed $j$ and $k$.

I'm unsure how to write this constraint, none of my ideas seem to get it right. Any ideas are welcomed and appreciated.

$\endgroup$
3
  • $\begingroup$ This is a nonconvex integer type constraint. Perhaps what you want is equivalent to: $$x_{ijk} \sum_{m} x_{mjk} \geq 2x_{ijk} \quad \forall i,j,k$$ $\endgroup$ Commented Mar 15, 2017 at 22:59
  • $\begingroup$ Allegedly this can be written linearly, perhaps with multiple statements. $\endgroup$ Commented Mar 15, 2017 at 23:06
  • $\begingroup$ It is not clear what $\sum_i \sum_j = 2$ means in your question so I ignored that in my first comment. But if you require $\sum_i \sum_j x_{ijk} = 2$ for all $k$, then for each $k$ the quantity $x_{ijk}$ will surely be 1 for some $(i,j)$ and so it must be 1 for some $x_{mjk}$ with $m\neq i$ (due to your additional constraint). So it seems your constraint just requires, for each $k$, there to be at most one $j$ index for which $x_{ijk}=1$. $\endgroup$ Commented Mar 15, 2017 at 23:28

2 Answers 2

Reset to default
1
$\begingroup$

Here is a way to do it without additional variables.

$\forall i_0,j,k, x_{i_0,j,k} \leq \sum_{i,i\neq i_0} x_{i,j,k} $

In a more general manner, whenever you have an "if A then B" in your head, with A and B taking values in $\{0,1\}$ and which you know how to express with linear expressions on your variables, $A \leq B$ usually does the trick. It is not the case for all logical constraints, some require non-linear constraints or additional variables.

$\endgroup$
0
$\begingroup$

Here's one way do do it (which works even in the absence of the $\sum_i \sum_j x_{ijk} = 2$ constraints).

For each pair $(j,k)$, add a new integer variable $y_{jk}$, with the inequalities $y_{jk} \ge x_{ijk}$ for all $i$. Finally, add the constraint $$\sum_i x_{ijk} \ge 2y_{jk}. \quad (\star)$$ If there is no $i$ with $x_{ijk}=1$, then we can set $y_{jk}$ to $0$ without a problem and make $(\star)$ trivially satisfied. On the other hand, if there is at least one $i$ with $x_{ijk}=1$, then $y_{jk}$ must be $1$, and then $(\star)$ implies that there are at least two distinct $i$ with $x_{ijk}=1$.

$\endgroup$

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.