Content area
A standard technique for bounding a combinatorial optimization problem is to form a semidefinite relaxation of the problem by “lifting” the problem into a higher dimensional space of symmetric matrices. For some combinatorial problems such as maximum k-cluster, the resulting semidefinite relaxation is not strictly feasible. In the context of the maximum k-cluster problem, we present an equivalent, strictly feasible semidefinite relaxation by way of the dimensionality reduction technique known as facial reduction. We provide a recipe to form this semidefinite relaxation directly, bypassing the lifting and facial reduction steps entirely. We then present our work on generalizing this result, and provide a recipe for constructing a strictly feasible semidefinite relaxation of binary quadratic problems with a single linear constraint with non-zero right-hand side. In addition, we also present numerical results that support the inclusion of facial reduction in the binary quadratic solver BiqCrunch, as well as results supporting the use of facial reduction when solving a semidefinite relaxation of the maximum k-cluster problem.