# Modeling an either-or-constraint

We would like to model a constraint for an assignment problem that dictates that either assign a specific subset of nodes $$I\subset\mathcal{I}$$ to a specific subset of nodes $$J\subset\mathcal{J}$$, or don't assign them at all.

In other words, for variable $$x_{ij}\in\{0,1\}, \forall i\in\mathcal{I},j\in\mathcal{J}$$, either $$x_{ij}=1, \forall i\in I, j \in J$$ or $$x_{ij}=0$$.

Is there a way to model this?

• Do you also have constraints like $\sum_j x_{ij}=1$ for all $i$? May 17 at 17:26
• The wording is a bit unclear. Do you mean that either each $i\in \mathcal{I}$ is assigned to some $j\in \mathcal{J}$ (but not to every such $j$) or else $i$ goes unassigned? Do you mean that either every $i\in \mathcal{I}$ is assigned to some $j\in \mathcal{J}$ or else none of the $i\in \mathcal{I}$ get assigned?
– prubin
May 17 at 18:42
• @prubin thank you for mentioning this. $I$ is the set of nodes in a particular region. In that region, if we want to assign $i\in I$ to a $j$, it has to be a $j\in J$. Otherwise, we treat that $i$ differently. But it cannot be assigned to a $j$ in another region.
– user9659
May 17 at 19:14
• @RobPratt Actually, no. It is possible to not assign an $i$ to any $j$ but if we do, for $i\in I$, it has to be $j\in J$.
– user9659
May 17 at 19:15
• OK, do you have constraints like $\sum_j x_{ij} \le 1$ for all $i$? May 17 at 21:06

You can introduce an additional binary variable $$y$$ that takes value $$1$$ if and only if at least one node from $$I$$ is matched with another one from $$J$$:

\begin{align*} x_{ij} &\le y \quad \forall i\in I, j\in J \\ x_{ij} &\le 1-y \quad \forall i\not\in I \; \mbox{or} \; j\not \in J \\ \end{align*}

And then impose that if $$y=1$$, the other nodes belonging to $$I$$ must be assigned to one node from $$J$$: $$y \le \sum_{j \in J} x_{ij} \quad \forall i\in I$$

• Maybe I am missing something, but why not just constrain $x_{ij}=y$? May 17 at 17:20
• @RobPratt Not sure if this answers your question, but...perhaps it's that the $x_{ij}$ in $x_{ij} \le y$ are from a different source than the $x_{ij}$ in $x_{ij} \le 1-y$ ?
– BCLC
May 17 at 17:22
• @RobPratt perhaps you cannot have $x_{ij}=1$ for all $i,j \in I \times J$? (if the assignment must be pairwise for example) May 17 at 17:28
• I think the question was not clear but I think this answer is correct. $I$ is the set of nodes in a particular region. In that region, if we want to assign $i\in I$ to a $j$, that $j$ has to be in $J$. Otherwise, we treat that $i$ differently. But it cannot be assigned to a j in another region. Does this make sense?
– user9659
May 17 at 19:19
• Yes it makes sense. Can you also confirm that $i$ can be assigned to at most one $j$ ? May 17 at 19:20

Based on the clarification about regions, it seems that all you have to do is add the constraints $$x_{ij}=0\quad\forall i\in I,j\notin J.$$ How to handle the "treat it differently" part may require some additional model structure.

• I think you meant sets $I$ and $J$ (vs $\mathcal{I}$ and $\mathcal{J}$), as the condition applies to the subsets. May 17 at 20:25
• @Kuifje Yes, thanks! I fixed it.
– prubin
May 17 at 20:29