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