The set partitioning problem and its decision variant (i.e., the exact cover problem) are combinatorial optimization problems that were historically crucial in the quantum optimization community. This problem is also employed in the main problem of the branch-and-price approach in many real-world optimization problems, including, but not limited to, redistricting and scheduling. Motivated by recent claims on the capability of quantum computers in “solving” hard combinatorial optimization problems, we propose a quadratic unconstrained binary optimization (QUBO) formulation for the set partitioning problem with tight penalty coefficients. We also employ five reduction techniques of Garfinkel and Nemhauser (Operations Research, 1969) to reduce the size of an existing set of benchmark instances. We finally use variational quantum eigensolver (VQE) as a heuristic to find feasible solutions for the problem. Our computational experiments show the efficacy of employing the tight penalty coefficients and the existing classical reduction techniques in the quantum context. Our codes and data are available on GitHub.
Citation
Accepted at Optimization Letters