A data-driven system for combinatorial optimization problems (本文)
カズヒロ サイトウ, Kazuhiro Saito, 和広 斉藤
Abstract
In recent years, data-driven systems such as machine learning are expected to solve social problems.the data-driven systems need to connect to various databases to collect the necessary data.In addition, when the problem of utilizing the predicted results from machine learning involves combinatorial optimization, it is difficult to achieve the desired performance using existing classical optimization methods due to the large scale of the problem.To solve these issues, this thesis proposes a data-driven system for combinatorial optimization problems with a virtual integrated data platform by data virtualization and a high-performance optimization environment by quantum annealing.This system integrates multiple data sources into a single virtual database system through data virtualization and provides a unified interface to users without modifying existing data sources.Furthermore, quantum annealing, a metaheuristic for combinatorial optimization based on quantum effects, enables fast solution of combinatorial optimization problems that are difficult to solve with conventional classical computers.We have implemented the proposed data-driven system for several data sources and used an actual quantum annealing machine, in order to evaluate the impact of communication between the data virtualization system and data sources on the system performance and to quantitatively compare quantum annealing and classical methods.The evaluation results show that the proposed data-driven system is effective for large-scale data in data infrastructure environments where a single query processing engine shares multiple data sources, as well as when a single data source is partitioned into multiple data sources.We also show that quantum annealing is effective in the vehicle routing problem and the grouping problem as specific combinatorial optimization problems, and discuss the overall performance of the proposed data-driven system from data collection to solving these optimization problems.