The Maximum-Entropy-Sampling Clustering Problem

We introduce the maximum-entropy-sampling clustering problem (MESPc), a novel and challenging combinatorial-optimization problem generalizing both the classical maximum-entropy sampling problem (MESP) and the maximum-clique problem. Given a graph and a covariance matrix of a Gaussian vector indexed by the vertex set, we seek a vertex subset of fixed cardinality that induces a clique while maximizing the differential entropy of the associated subvector. We extend to MESPc a convex relaxation for MESP based on the Boolean Quadratic Polytope, using a lifted matrix variable and incorporating a quadratic constraint to enforce the clique structure. Strengthening this relaxation, we develop independent-set valid inequalities and investigate both direct and cutting-plane approaches for their incorporation. We also propose a heuristic to obtain feasible solutions and corresponding lower bounds for MESPc. Computational experiments highlight the strength of the relaxation and the impact of the independent-set inequalities in reducing the gap between upper and lower bounds.