[Solved]: Suboptimal Solution for a combinatorial problem

Mixed-integer quadratic programming

Given your updated question, this can be formulated as a mixed-integer quadratic programming problem. Let $y_1,dots,y_n$ be $n$ zero-or-one integer variables, subject to the constraint $y_1+dots+y_n=s$, with the intent that if $y_i=1$ then we are selecting the $i$th row from $B$. Then for each $i,j$, the entry $(hat{X}-X)_{i,j}$ can be expressed as a linear function of $y_1,dots,y_n$. We are asking to minimize the objective function $sum_i,j (hat{X}-X)_{i,j}^2$, which is a quadratic objective function. Therefore, this can be expressed as a mixed-integer quadratic programming problem. So, you could try throwing an off-the-shelf solver for mixed-integer quadratic programming at this and see how it does.

Closest vector problem

If everything in sight is an integer, I think this problem could also be approached as the problem of finding the closest point in a lattice to a given vector, the closest vector problem (CVP). Consider the following lattice over a $n+s^2$-dimensional space. For each $i$, we have a basis vector of the form $$(0,dots,0,K,0,dots,0,B_i,0,dots,0),$$ where $K$ is a large constant (to be chosen later) and in the above, $K$ appears in the $i$th column, and $B_i$ is the $i$th row of $B$ and it appears starting in the $n+(i-1)s+1$th column. This gives us $n$ basis vectors, which form a basis for the lattice. Now we want to find the lattice point that is closest to the vector $$(0,dots,0,hat{X}_1,hat{X}_2,dots,hat{X}_s),$$ where the first $n$ columns of this vector are zero and $hat{X}_i$ is the $i$th row of $hat{X}$. If we choose $K$ appropriately, the closest lattice point has a good chance of being a sum of just $s$ of the basis vectors and thus forming a solution to this problem. Now you could try to see if you can find any off-the-shelf CVP solvers, and see if they are effective at this problem. This is only going to work if everything is an integer: if you’ve got real numbers, I don’t think this will work.