A Hybrid Solution Method for the Multi-Service Location Set Covering Problem
conference paper
The Multi-Service Location Set Covering Problem is an extension of the well-known Set Covering Problem. It arises in practical applications where a set of physical locations need to be equipped with services to satisfy demand within a certain area, while minimizing costs. In this paper we formulate the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, apply the hybrid framework of the D-Wave quantum annealer to solve it, and investigate the feasibility of this approach. To improve the often suboptimal initial solutions found on the D-Wave system, we develop a hybrid quantum/classical optimization algorithm that starts from the seed solution and iteratively creates small subproblems that are more efficiently solved on the D-Wave but often still converge to feasible and improved solutions of the original problem. Finally we suggest some opportunities for increasing the accuracy of our algorithm.
TNO Identifier
875833
Publisher
ICCS
Source title
International Conference on Computational Sciences (ICCS)
Files
To receive the publication files, please send an e-mail request to TNO Repository.