4
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Do you also have constraints like $\sum_j x_{ij}=1$ for all $i$? $\endgroup$
    – RobPratt
    May 17, 2022 at 17:26
  • 1
    $\begingroup$ 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? $\endgroup$
    – prubin ♦
    May 17, 2022 at 18:42
  • 1
    $\begingroup$ @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. $\endgroup$
    – user9659
    May 17, 2022 at 19:14
  • 1
    $\begingroup$ @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$. $\endgroup$
    – user9659
    May 17, 2022 at 19:15
  • 1
    $\begingroup$ OK, do you have constraints like $\sum_j x_{ij} \le 1$ for all $i$? $\endgroup$
    – RobPratt
    May 17, 2022 at 21:06

2 Answers 2

Reset to default
4
$\begingroup$

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

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.