Trip Planning Based on subQUBO Annealing
The trip planning problem (TPP) can be formulated as a combinatorial optimization problem that searches for the best route to visit a series of landmarks and hotels. Meanwhile, Ising machines have attracted attention due to their efficiency in solving combinatorial optimization problems. The Ising m...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10247510/ |
| _version_ | 1797676673172242432 |
|---|---|
| author | Tatsuya Noguchi Keisuke Fukada Siya Bao Nozomu Togawa |
| author_facet | Tatsuya Noguchi Keisuke Fukada Siya Bao Nozomu Togawa |
| author_sort | Tatsuya Noguchi |
| collection | DOAJ |
| description | The trip planning problem (TPP) can be formulated as a combinatorial optimization problem that searches for the best route to visit a series of landmarks and hotels. Meanwhile, Ising machines have attracted attention due to their efficiency in solving combinatorial optimization problems. The Ising machines solve the combinatorial optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO) models. However, the possible input QUBO size of current Ising machines is quite limited. Thus, it is hard to directly embed a large-scale TPP onto the current Ising machines. In this paper, we propose a novel subQUBO annealing method based on the combined variable selection method to solve the TPP. The proposed method finds a quasi-optimal solution to a large problem by repeatedly partitioning the original QUBO model into small subQUBOs that can be embedded onto the Ising machine. Specifically, to construct a subQUBO, we select variables from the original QUBO model, which have small deviation values. Further, we select variables randomly from the original QUBO model, so as not to fall into the local optimum. We have conducted an evaluation experiment using Ising machines on TPP and confirmed that the proposed method outperforms the state-of-the-art methods in terms of POI satisfaction and POI cost. |
| first_indexed | 2024-03-11T22:33:42Z |
| format | Article |
| id | doaj.art-3fd5acc97cd24863bb07ef2e5cee6343 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-03-11T22:33:42Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-3fd5acc97cd24863bb07ef2e5cee63432023-09-22T23:01:24ZengIEEEIEEE Access2169-35362023-01-011110038310039510.1109/ACCESS.2023.331449810247510Trip Planning Based on subQUBO AnnealingTatsuya Noguchi0https://orcid.org/0009-0007-2301-6901Keisuke Fukada1https://orcid.org/0000-0002-6087-1399Siya Bao2https://orcid.org/0000-0003-1993-9133Nozomu Togawa3https://orcid.org/0000-0003-3400-3587Department of Computer Science and Communications Engineering, Waseda University, Shinjuku, Tokyo, JapanDepartment of Computer Science and Communications Engineering, Waseda University, Shinjuku, Tokyo, JapanDepartment of Computer Science and Communications Engineering, Waseda University, Shinjuku, Tokyo, JapanDepartment of Computer Science and Communications Engineering, Waseda University, Shinjuku, Tokyo, JapanThe trip planning problem (TPP) can be formulated as a combinatorial optimization problem that searches for the best route to visit a series of landmarks and hotels. Meanwhile, Ising machines have attracted attention due to their efficiency in solving combinatorial optimization problems. The Ising machines solve the combinatorial optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO) models. However, the possible input QUBO size of current Ising machines is quite limited. Thus, it is hard to directly embed a large-scale TPP onto the current Ising machines. In this paper, we propose a novel subQUBO annealing method based on the combined variable selection method to solve the TPP. The proposed method finds a quasi-optimal solution to a large problem by repeatedly partitioning the original QUBO model into small subQUBOs that can be embedded onto the Ising machine. Specifically, to construct a subQUBO, we select variables from the original QUBO model, which have small deviation values. Further, we select variables randomly from the original QUBO model, so as not to fall into the local optimum. We have conducted an evaluation experiment using Ising machines on TPP and confirmed that the proposed method outperforms the state-of-the-art methods in terms of POI satisfaction and POI cost.https://ieeexplore.ieee.org/document/10247510/Trip planning problemIsing machinequantum computerIsing modelQUBO modelsubQUBO |
| spellingShingle | Tatsuya Noguchi Keisuke Fukada Siya Bao Nozomu Togawa Trip Planning Based on subQUBO Annealing IEEE Access Trip planning problem Ising machine quantum computer Ising model QUBO model subQUBO |
| title | Trip Planning Based on subQUBO Annealing |
| title_full | Trip Planning Based on subQUBO Annealing |
| title_fullStr | Trip Planning Based on subQUBO Annealing |
| title_full_unstemmed | Trip Planning Based on subQUBO Annealing |
| title_short | Trip Planning Based on subQUBO Annealing |
| title_sort | trip planning based on subqubo annealing |
| topic | Trip planning problem Ising machine quantum computer Ising model QUBO model subQUBO |
| url | https://ieeexplore.ieee.org/document/10247510/ |
| work_keys_str_mv | AT tatsuyanoguchi tripplanningbasedonsubquboannealing AT keisukefukada tripplanningbasedonsubquboannealing AT siyabao tripplanningbasedonsubquboannealing AT nozomutogawa tripplanningbasedonsubquboannealing |