2
$\begingroup$

I was usually using if-then constraints with integer variables but ended up using continuous variables and got confused. I have variables $x_{ij}\in\mathbb{R}_{\geq 0}$, and would like to force the program: if $x_{ij}>0$, then $x_{ji}=0$, where $i,j\in\mathcal{I}$. When I use the following (in which $\mathbb{M}$ is a big number), it looks like the constraint serves to the purpose.

$$x_{ij}\geq \mathbb{M}x_{ji} \qquad \forall i,j\in\mathcal{I}.$$

However, it does a bit further than what is expected and undesired, which is $x_{ji}=0$, when $x_{ij}=0$. The symmetry of this will be conflicting. My variable essentially denotes a flow amount from node $i$ to node $j$, and I would like to ensure: if flow occurs from $i$ to $j$, it should not occur from $j$ to $i$.

$\endgroup$
2
  • $\begingroup$ Let $x_{12}=3$ and $\mathbb{M}=1000$. I would like $x_{21}=0$. My constraint will readily ensure because the r.h.s. variable can only take $x_{21}=0$ to satisfy the constraint. However, based on my constraint, I also define $x_{21}\geq \mathbb{M} x_{12}$ which conflicts with the previous. I do not see a solution by adding your constraint on top of mine because it directly creates a conflict ($x_{12} \leq \mathbb{M}x_{21}$) based on my example. Your comments? $\endgroup$ – tcokyasar Feb 21 at 20:01
  • $\begingroup$ Yes this was wrong i misread the text. $\endgroup$ – user3680510 Feb 21 at 21:02
6
$\begingroup$

Introduce a binary variable $y_{i,j}$ and linear constraints \begin{align} x_{i,j} &\le M y_{i,j} \tag1 \\ y_{i,j} + y_{j,i} &\le 1 \tag2 \end{align} Constraint $(1)$ enforces $x_{i,j} > 0 \implies y_{i,j} = 1$. Constraint $(2)$ enforces $y_{i,j} = 1 \implies y_{j,i} = 0$. Constraint $(1)$ (with the roles of $i$ and $j$ interchanged) enforces $y_{j,i} = 0 \implies x_{j,i} = 0$.

$\endgroup$
3
  • $\begingroup$ Thanks for the solution, @RobPratt ! $\endgroup$ – tcokyasar Feb 21 at 20:12
  • 2
    $\begingroup$ Glad to help. By the way, you should use a small upper bound $M_{i,j}$ rather than an arbitrarily large $M$. $\endgroup$ – RobPratt Feb 21 at 20:13
  • $\begingroup$ Sure, I have a tight upper bound for $x_{ij}$ that can be used as M. $\endgroup$ – tcokyasar Feb 21 at 20:17
3
$\begingroup$

For sake of completeness: An alternative to using an additional binary variable and a big M would be to use an SOS constraint. An SOS constraint specifies a set of variables, at most one of which may be non-zero.

$\endgroup$

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.