4

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?

  • 2
    Do you also have constraints like $\sum_j x_{ij}=1$ for all $i$? – RobPratt May 17 '22 at 17:26
  • 1
    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 '22 at 18:42
  • 1
    @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. –  May 17 '22 at 19:14
  • 1
    @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$. –  May 17 '22 at 19:15
  • 1
    OK, do you have constraints like $\sum_j x_{ij} \le 1$ for all $i$? – RobPratt May 17 '22 at 21:06
  • 1
    @RobPratt each $i$ is assigned to at most 1 $j$. –  May 18 '22 at 04:15

2 Answers2

5

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
4

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 $$

Kuifje
  • 13,324
  • 1
  • 23
  • 56
  • 3
    Maybe I am missing something, but why not just constrain $x_{ij}=y$? – RobPratt May 17 '22 at 17:20
  • 1
    @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 '22 at 17:22
  • 1
    @RobPratt perhaps you cannot have $x_{ij}=1$ for all $i,j \in I \times J$? (if the assignment must be pairwise for example) – Kuifje May 17 '22 at 17:28
  • 1
    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? –  May 17 '22 at 19:19
  • 1
    Yes it makes sense. Can you also confirm that $i$ can be assigned to at most one $j$ ? – Kuifje May 17 '22 at 19:20
  • 1
    @Kuifje Yes, each $i\in I$ can be assigned to at most one $j \in J$. –  May 17 '22 at 19:26