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