Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Access

Trip Planning Based on subQUBO Annealing

Tatsuya Noguchi, Keisuke Fukada, Siya Bao, Nozomu Togawa

Published Jan 1, 2023• 9 citations
Publisher

Abstract

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.

DOI
10.1109/access.2023.3314498

Related papers

Hybrid subQUBO Annealing With a Correction Process for Multi-Day Intermodal Trip Planning

Tatsuya Noguchi, Keisuke Fukada, Siya Bao +1 more

The multi-day intermodal trip planning problem (MITPP) is an optimization problem that seeks to create the optimal route to visit Point-of-Interest (POI) and hotels over days. This problem involves coordinating intermodal transportation, such as walking, public transportation, to create a well-crafted travel itinerary. Quantum annealers have recently been explored as a powerful tool for solving combinatorial optimization problems by converting the problems into Quadratic Unconstrained Binary Optimization (QUBO). However, current quantum annealers have a small QUBO input size so that they cannot directly solve large-scale MITPPs. In this paper, we address this issue by extracting a subQUBO from the original large QUBO based on variable (spin) deviations and randomness. Then, we iteratively solve the subQUBOs by the quantum annealer and update the (quasi-)optimal solution. As the obtained (quasi-)optimal solution may violate constraints, we apply the correction processing till all constraints are satisfied. According to the experiment results using a real quantum annealer, our proposed method obtained high-quality solutions for large-scale MITPPs in the Tokyo area, and compared to the full QUBO method, we achieve a maximum spin reduction of 98.9%. Especially, compared to the method by a conventional computer and two conventional subQUBO methods, POI satisfaction is improved by 10.2%, and travel costs are improved by 23.2% respectively.

IEEE Access•Jan 1, 2025•0 citations

Hybrid Annealing Method Based on subQUBO Model Extraction With Multiple Solution Instances

Yuta Atobe, Masashi Tawada, Nozomu Togawa

Ising machines are expected to solve combinatorial optimization problems efficiently by representing them as Ising models or equivalent quadratic unconstrained binary optimization (QUBO) models . However, upper bound exists on the computable problem size due to the hardware limitations of Ising machines. This paper propose a new hybrid annealing method based on partial QUBO extraction, called subQUBO model extraction, with multiple solution instances. For a given QUBO model, the proposed method obtains$N_I$quasi-optimal solutions (quasi-ground-state solutions) in some way using a classical computer. The solutions giving these quasi-optimal solutions are calledsolution instances. We extract a size-limited subQUBO model as follows based on a strong theoretical background: we randomly select$N_S$$(N_S<N_I)$solution instances among them and focus on a particular binary variable$x_i$in the$N_S$solution instances. If$x_i$value is muchvariedover$N_S$solution instances, it is included in the subQUBO model; otherwise, it is not. We find a (quasi-)ground-state solution of the extracted subQUBO model using an Ising machine and add it as a new solution instance. By repeating this process, we can finally obtain a (quasi-)ground-state solution of the original QUBO model. Experimental evaluations confirm that the proposed method can obtain better quasi-ground-state solution than existing methods for large-sized QUBO models.

IEEE Transactions on Computers•Dec 28, 2021•38 citations

Multi-day Travel Planning Using Ising Machines for Real-world Applications

Siya Bao, Masashi Tawada, Shu Tanaka +1 more

The multi-day travel planning assists users with realistic travel itineraries by searching for the optimal travel routes through a set of candidate hotels and point-of-interests (POIs). The multi-day travel planning problem (MTPP) can be solved as an optimization problem. Although conventional methods using von Neumann computers obtain good approximate solutions to the optimization problems, large computation costs are required to solve large-scale or complex problems due to the combinatorial explosion. On the other hand, Ising machines or quantum annealing machines are non-von Neumann computers, and those machines are developed to deal with complex optimization problems. In this paper, we propose an Ising-machine-based method for the MTPP. Practical factors of the MTPP include the POI satisfaction, travel expenses, and time limits. Those factors are mapped onto quadratic unconstrained binary optimization (QUBO) forms. We evaluate the proposed method using two real-world datasets including Sapporo and Tokyo, Japan. Experimental results show that the MTPP can be effectively solved using Ising machines compared with the conventional methods in terms of the solution quality and the execution time. To the best of our knowledge, this study is the first solution of the MTPP using Ising machines.

IEEE International Conference on Intelligent Transportation Systems (ITSC)•Sep 19, 2021•14 citations

Multi-Day Intermodal Trip Planning Using subQUBO Annealing with Correction Processing

Tatsuya Noguchi, Keisuke Fukada, Siya Bao +1 more

The multi-day intermodal trip planning problem (MITPP) is an optimization problem that finds the optimal route to visit points of interest (POIs) and hotels over days with multiple transportation such as walking and trains. Meanwhile, quantum annealers effectively solve the optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO). However, the possible input QUBO size of the current quantum annealer is quite limited. In this paper, we propose a subQUBO annealing method for solving large-scale MITPPs. Also, we apply a correction processing to avoid constraint violation. Evaluation experiments show that the proposed method succeeds in obtaining high-quality solutions for large-scale MITPPs.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•1 citation

SubQUBO Annealing Based on Efficient Binary Variable Selection for Combinatorial Optimization Problems with One-Hot Constraints

Tatsuya Noguchi, Keisuke Fukada, Siya Bao +1 more

In combinatorial optimization problems with one-hot constraints, the number of binary variables that have the value of one in the feasible solution becomes constant and small, so it is important to always consider them to escalate the solution searching process and obtain a more converged solution in annealing. In this paper, we propose a method to preferably select binary variables with the value of one in the subQUBO annealing process using Ising machines such as quantum annealers. Evaluation experiments show that the proposed method obtains a solution with lower energy than a conventional subQUBO method and a full QUBO method.

International Conference on Consumer Electronics•Jan 11, 2025•1 citation

A Novel Classical-Ising Hybrid Annealing Method with QUBO Model Cutting

Yuta Atobe, Masashi Tawada, Nozomu Togawa

Most quantum annealers, or Ising machines have the hardware limitations in its qubit size and thus the computable problem size is much limited. This paper proposes a novel classical-Ising hybrid annealing method which virtually extends the computable size of Ising machines based on a theoretical analysis. Given a quadratic unconstrained binary optimization (QUBO) model, the proposed method selects the cutting binary variable that is most likely to have the same value as the ground-state solution. Then, we recursively cut the QUBO model based on the cutting binary variable until we obtain sufficiently small-sized subQUBO models. Experimental evaluations demonstrate that the proposed hybrid annealing method can give much better quasi-ground-state solutions than state-of-the-art existing methods for large-sized QUBO models.

IEEE International Midwest Symposium on Circuits and Systems (MWSCAS)•Aug 11, 2024•0 citations
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.
The multi-day intermodal trip planning problem (MITPP) is an optimization problem that seeks to create the optimal route to visit Point-of-Interest (POI) and hotels over days. This problem involves coordinating intermodal transportation, such as walking, public transportation, to create a well-crafted travel itinerary. Quantum annealers have recently been explored as a powerful tool for solving combinatorial optimization problems by converting the problems into Quadratic Unconstrained Binary Optimization (QUBO). However, current quantum annealers have a small QUBO input size so that they cannot directly solve large-scale MITPPs. In this paper, we address this issue by extracting a subQUBO from the original large QUBO based on variable (spin) deviations and randomness. Then, we iteratively solve the subQUBOs by the quantum annealer and update the (quasi-)optimal solution. As the obtained (quasi-)optimal solution may violate constraints, we apply the correction processing till all constraints are satisfied. According to the experiment results using a real quantum annealer, our proposed method obtained high-quality solutions for large-scale MITPPs in the Tokyo area, and compared to the full QUBO method, we achieve a maximum spin reduction of 98.9%. Especially, compared to the method by a conventional computer and two conventional subQUBO methods, POI satisfaction is improved by 10.2%, and travel costs are improved by 23.2% respectively.
Ising machines are expected to solve combinatorial optimization problems efficiently by representing them as Ising models or equivalent quadratic unconstrained binary optimization (QUBO) models . However, upper bound exists on the computable problem size due to the hardware limitations of Ising machines. This paper propose a new hybrid annealing method based on partial QUBO extraction, called subQUBO model extraction, with multiple solution instances. For a given QUBO model, the proposed method obtainsNIN_INI​quasi-optimal solutions (quasi-ground-state solutions) in some way using a classical computer. The solutions giving these quasi-optimal solutions are calledsolution instances. We extract a size-limited subQUBO model as follows based on a strong theoretical background: we randomly selectNSN_SNS​(NS<NI)(N_S<N_I)(NS​<NI​)solution instances among them and focus on a particular binary variablexix_ixi​in theNSN_SNS​solution instances. Ifxix_ixi​value is muchvariedoverNSN_SNS​solution instances, it is included in the subQUBO model; otherwise, it is not. We find a (quasi-)ground-state solution of the extracted subQUBO model using an Ising machine and add it as a new solution instance. By repeating this process, we can finally obtain a (quasi-)ground-state solution of the original QUBO model. Experimental evaluations confirm that the proposed method can obtain better quasi-ground-state solution than existing methods for large-sized QUBO models.
The multi-day travel planning assists users with realistic travel itineraries by searching for the optimal travel routes through a set of candidate hotels and point-of-interests (POIs). The multi-day travel planning problem (MTPP) can be solved as an optimization problem. Although conventional methods using von Neumann computers obtain good approximate solutions to the optimization problems, large computation costs are required to solve large-scale or complex problems due to the combinatorial explosion. On the other hand, Ising machines or quantum annealing machines are non-von Neumann computers, and those machines are developed to deal with complex optimization problems. In this paper, we propose an Ising-machine-based method for the MTPP. Practical factors of the MTPP include the POI satisfaction, travel expenses, and time limits. Those factors are mapped onto quadratic unconstrained binary optimization (QUBO) forms. We evaluate the proposed method using two real-world datasets including Sapporo and Tokyo, Japan. Experimental results show that the MTPP can be effectively solved using Ising machines compared with the conventional methods in terms of the solution quality and the execution time. To the best of our knowledge, this study is the first solution of the MTPP using Ising machines.
The multi-day intermodal trip planning problem (MITPP) is an optimization problem that finds the optimal route to visit points of interest (POIs) and hotels over days with multiple transportation such as walking and trains. Meanwhile, quantum annealers effectively solve the optimization problems by transforming the problems into quadratic unconstrained binary optimization (QUBO). However, the possible input QUBO size of the current quantum annealer is quite limited. In this paper, we propose a subQUBO annealing method for solving large-scale MITPPs. Also, we apply a correction processing to avoid constraint violation. Evaluation experiments show that the proposed method succeeds in obtaining high-quality solutions for large-scale MITPPs.
In combinatorial optimization problems with one-hot constraints, the number of binary variables that have the value of one in the feasible solution becomes constant and small, so it is important to always consider them to escalate the solution searching process and obtain a more converged solution in annealing. In this paper, we propose a method to preferably select binary variables with the value of one in the subQUBO annealing process using Ising machines such as quantum annealers. Evaluation experiments show that the proposed method obtains a solution with lower energy than a conventional subQUBO method and a full QUBO method.
Most quantum annealers, or Ising machines have the hardware limitations in its qubit size and thus the computable problem size is much limited. This paper proposes a novel classical-Ising hybrid annealing method which virtually extends the computable size of Ising machines based on a theoretical analysis. Given a quadratic unconstrained binary optimization (QUBO) model, the proposed method selects the cutting binary variable that is most likely to have the same value as the ground-state solution. Then, we recursively cut the QUBO model based on the cutting binary variable until we obtain sufficiently small-sized subQUBO models. Experimental evaluations demonstrate that the proposed hybrid annealing method can give much better quasi-ground-state solutions than state-of-the-art existing methods for large-sized QUBO models.