Partition a pairwise distance matrix that minimize the sum of subset distances Suppose there is a set $X$ of $n$ elements with a metric space(the distance has property: identity of indiscernible, symmetry, triangle inequality, non-negativity). I also have their Gram matrix/pairwise distance matrix $G \in \mathbb{R}^{n \times n}$, $\forall g_{i,j} \in G, g_{i,j} \gt 0 , g_{ij} = g_{ji}$.
How can one find a partition $L,R \subseteq X, L\cup R = X, L \cap R = \emptyset$, such that $\textbf{sum}(G_L) + \textbf{sum}(G_R)$ is minimized?
Here $G_L$ refers to the sub Gram matrix with rows and columns only contained elements from $L$.
And $\textbf{sum}(G)$ is the element-wise sum of a matrix.
 A: This is the maximum weighted cut problem in an undirected graph.  You can solve it via integer linear programming as follows.  For each node $i$, let binary decision variable $x_i$ indicate whether $i\in L$.  For each edge $(i,j)$, with $i<j$, let binary decision variable $y_{i,j}$ indicate whether nodes $i$ and $j$ are on different sides of the bipartition.  The problem is to maximize $\sum_{i,j} g_{i,j} y_{i,j}$ subject to
$$y_{i,j} \le x_i(1-x_j) + x_j(1-x_i) \quad \text{for $i<j$} \tag1$$
This quadratic constraint enforces the logical implication $$y_{i,j} \implies \left((x_i \land \lnot x_j) \lor (x_j \land \lnot x_i)\right).\tag2$$
You can linearize $(1)$ by rewriting $(2)$ in conjunctive normal form:
$$
\lnot y_{i,j} \lor (x_i \land \lnot x_j) \lor (x_j \land \lnot x_i) \\
(\lnot y_{i,j} \lor x_i \lor x_j) \land (\lnot y_{i,j} \lor \lnot x_j \lor \lnot x_i) \\
(1 - y_{i,j} + x_i + x_j \ge 1) \land (1 - y_{i,j} + 1 - x_j + 1 - x_i \ge 1) \\
(y_{i,j} \le x_i + x_j) \land (y_{i,j} + x_i + x_j \le 2) \\
$$
That is, you can replace $(1)$ with linear constraints:
$$y_{i,j} \le x_i + x_j \le 2 - y_{i,j} \quad \text{for $i<j$} \tag3$$
