A standard technique for bounding combinatorial optimization problems is to obtain a semidefinite relaxation by “lifting” the problem into a higher dimensional space of symmetric matrices. For some combinatorial problems such as the maximum $k$-cluster, the resulting SDP relaxation is not strictly feasible. In the context of the maximum $k$-cluster problem, we present an equivalent strictly feasible SDP relaxation by way of the dimensionality reduction technique known as facial reduction. We then present a recipe to form this strictly feasible SDP relaxation directly from the original problem and generalize this process for any binary quadratic problem with a single linear constraint. Finally, we will discuss how facial reduction is implemented into the BiqCrunch solver for binary quadratic problems.