3
$\begingroup$

Let :

  • $G$ be a undirected graph with nodes $a_1, \ldots, a_n$
  • $x_1, \ldots, x_m$ a set of real values
  • $\epsilon > 0$
  • Var the variance function
  • $d$ the "distance" between sets : $d(X_1, X_2) = \min_{x_1\in X_1, x_2\in X_2, x_1\neq x_2} |x_1-x_2|$. It's not exactly a distance.

I'm looking at finding :

  • $k\in\mathbb{N}$
  • a partition of the nodes $(a_i)_i$ in sets $G_1, \ldots, G_k$
  • a partition of the $(x_i)_i$ in sets $F_1, \ldots, F_k$

such that it maximizes : $$ \sum_j Var(F_j) $$ under the following constraints :

  • For any edge $(a_1, a_2)$ of $G$, denoting $G_i$ and $G_j$ the groups containing $a_1$ and $a_2$, we require that $d(F_i, F_j) > \epsilon$
  • For all $i$, $|F_i| \geq |G_i|$

How to optimize two partitions at the same time under non-linear constraints?

$\endgroup$
8
  • $\begingroup$ Are you requiring that no edge in $G$ be within a single group? $\endgroup$
    – prubin
    Feb 28, 2022 at 20:16
  • $\begingroup$ not necessarily $\endgroup$
    – Jin Kazama
    Feb 28, 2022 at 20:34
  • $\begingroup$ So if $(a_1, a_2)$ is an edge with $a_1$ and $a_2$ both in $G_i$, then you require $d(F_i, F_i) > \epsilon$? That's a problem. $\endgroup$
    – prubin
    Feb 28, 2022 at 20:40
  • $\begingroup$ Thank you, I edited the "distance" because I didn't describe well the case you described $\endgroup$
    – Jin Kazama
    Feb 28, 2022 at 21:13
  • $\begingroup$ So you want $d(X, X) = \min_{x_1 \in X, x_2 \in X, x_1\neq x_2} \vert x_1 - x_2\vert$? (Note that both arguments of the distance function are the same, i.e., we are talking about the distance of a set from itself.) $\endgroup$
    – prubin
    Feb 28, 2022 at 22:20

1 Answer 1

3
$\begingroup$

The simplest/most tractable dispersion measure I can think of is set diameter (maximum absolute difference between two elements of the set), and even then the model (a mixed integer linear program) is going to be rather large.

In what follows, indices $h$ and $i$ will select either numbers (e.g., $x_{h}$) or vertices (e.g., $a_{h}$) while indices $j$ and $\ell$ will select sets of numbers (e.g., $F_{j}$) or sets of vertices (e.g., $G_{j}$). So the range of $h$ and $i$ will be either 1 to $m$ or 1 to $n$, depending on context. The range of $j$ and $\ell$ will be 1 to $K$, where $K$ is an a priori bound on the number of sets to use in the partition. The actual number $k$ of sets used will be determined from the final solution by dropping empty sets. $M$ will be a sufficiently large positive number. (It need not be the same in every constraint, but I will omit subscripts to spare myself some typing.) $E$ represents the set of edges in $G.$

The model will contain the following variables:

  • binary $y_{ij}$ will be 1 if number $x_{i}$ belongs to set $F_{j}$, 0 if not;
  • binary $u_{ij}$ will be 1 if vertex $a_{i}$ belongs to set $G_{j}$, 0 if not;
  • binary $v_{hij}$ will be 1 if numbers $x_{h}$ and $x_{i}$ ($h<i$) both belong to $F_{j}$ and determine the diameter of $F_{j}$ (i.e., are the furthest apart of any pair of numbers in $F_{j};$
  • real $z_{j\ell}\ge0$ will be the distance $d(F_{j},F_{\ell})$ between sets $j$ and $\ell$; and
  • real $w_{j}\ge0$ will be the diameter of set $F_{j}.$

The objective function will be to maximize $\sum_{j}w_{j}.$ The constraints are as follows.

  • Every number belongs to exactly one of the $F$ sets. $$\sum_{j}y_{ij}=1\quad\forall i.$$
  • Every node belongs to exactly one of the $G$ sets. $$\sum_{j}u_{ij}=1\quad\forall i.$$
  • The cardinality of each $F_{j}$ is at least as large as the cardinality of the corresponding $G_{j}$. $$\sum_{i}y_{ij}\ge\sum_{i}u_{ij}\quad\forall j.$$ Note that this prevents using a set $G_{j}$ while leaving $F_{j}$ empty.
  • You cannot use $F_{j}$ while leaving $G_{j}$ empty. $$y_{ij}\le\sum_{h}u_{hj}\quad\forall i,j.$$ Combined with the previous constraint, this ensures that the number of sets $F_{\cdot}$ and the number of sets $G_{\cdot}$ that are used will be the same ($k$).
  • The distance between two sets is at most the minimum distance between (distinct) members of each set. $$z_{j\ell}\le\vert x_{h}-x_{i}\vert+M\left(2-y_{hj}-y_{i\ell}\right)\quad\forall j\le\ell,\forall h\neq i.$$ Note that this constraint is repeated for both $h<i$ and $h>i$.
  • For any edge in the graph, the distance between the number sets corresponding to the vertex sets containing the endpoints of the edge must be at least $\epsilon$. $$z_{j\ell}\ge\epsilon\left(u_{hj}+u_{i\ell}-1\right)\quad\forall j\le\ell,\forall h\neq i\ni(a_{h},a_{i})\in E.$$ Note that this constraint is repeated for both $(a_{h},a_{i})$ and $(a_{i},a_{h}).$
  • For $v_{hij}$ to be 1, it is necessary that both $x_{h}$ and $x_{i}$ belong to $F_{j}$. $$v_{hij}\le y_{hj}\quad\forall h<i,\forall j.$$ $$v_{hij}\le y_{ij}\quad\forall h<i,\forall j.$$
  • Exactly one pair of numbers dictates the diameter of $F_{j}$. $$\sum_{h,i:h<i}v_{hij}=1\quad\forall j.$$
  • The diameter of $F_{j}$ is determined by the $v_{\cdot\cdot j}$ variables. $$w_{j}=\sum_{h,i:h<i}\vert x_{h}-x_{i}\vert v_{hij}\quad\forall j.$$
$\endgroup$
1
  • $\begingroup$ Thanks a lot !! $\endgroup$
    – Jin Kazama
    Mar 1, 2022 at 17:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.