Parallelizable search-space decomposition for large-scale combinatorial optimization problems using quadratic unconstrained binary optimization Authors: Eiji Kawase, Shuta Kikuchi, Hideaki Tamai, Shu Tanaka Published: 2026 ABSTRACT AbstractCombinatorial optimization problems are crucial in industry. However, many COPs are NP-hard, causing the search space to grow exponentially with problem size and rendering large-scale instances computationally intractable. Conventional solvers typically treat problems as monolithic entities, leading to significant efficiency degradation as structural complexity increases. To address this issue, we propose a novel search-space decomposition method that leverages the inherent structure of variables to systematically reduce the size of the master problem. We formulate interaction costs between variables and individual variable costs as a constrained maximum cut problem and convert it into a quadratic unconstrained binary optimization formulation using penalty terms. An Ising-model solver is used to rapidly decompose the problem into independent small-scale subproblems, which are subsequently solved in parallel using mathematical optimization solvers. We validated this method on the capacitated vehicle routing problem. Results demonstrate three significant benefits: a substantial enhancement in feasible solution rates, accelerated convergence, achieving in 1 min the accuracy that the naive method required 30 min to reach, and a variable reduction of up to 95.32%. These findings suggest that search-space decomposition is a promising strategy for efficiently solving large-scale combinatorial optimization problems.Keywords: Capacitated vehicle routing problem, Combinatorial optimization problem, Ising machine, Quadratic unconstrained binary optimization, Search-space decompositionSubject terms: Engineering, Mathematics and computing Introduction Combinatorial optimization problems (COPs) are defined as problems of finding a combination of discrete variables that minimize or maximize an objective function under given constraints1. These problems arise in diverse real-world fields, such as vehicle routing2, production scheduling3, facility location4, and portfolio optimization5, and play a critical role in industry. However, many COPs are NP-hard, implying that the required computational effort may grow exponentially with problem size, making large-scale instances computationally challenging. In addition, complex constraints significantly restrict the feasible region, further complicating the search process6. Exhaustively exploring such vast and complex search spaces to guarantee optimality is computationally impractical for most realistic large-scale instances. To address this intractability, various approaches have been developed. From a mathematical perspective, approximation algorithms7 provide polynomial-time solutions with theoretical guarantees, such as Christofides’ algorithm8 for the traveling salesman problem (TSP). However, deriving such guarantees for complex, highly constrained industrial problems is often infeasible. Consequently, metaheuristics such as simulated annealing9, tabu search10, genetic algorithms11, particle swarm optimization12, and ant colony optimization13 have become standard approaches for obtaining high-quality approximate solutions within a reasonable time frame14. In parallel, commercial mathematical optimization solvers (e.g., Gurobi15, CPLEX16) have evolved to incorporate sophisticated heuristics alongside exact methods such as branch-and-bound. Despite these advancements, conventional solvers typically treat the problem as a single monolithic task. Consequently, as the problem size increases, the search space expands rapidly and structural parallelization becomes challenging. As a result, large-scale problems with complex structures may require prohibitively long computation times to obtain practically satisfactory solutions. Decomposition methods provide a potential pathway to improved scalability by dividing large problems into manageable subproblems. Classical techniques such as Benders decomposition17 or Dantzig–Wolfe decomposition18 partition problems according to their mathematical structure, including separable constraints or block-angular formulations. While theoretically sound, these methods generally require iterative coordination and information exchange between a master problem and subproblems, making fully independent parallel execution difficult. To achieve high scalability through parallelism, a method is required that can rapidly partition a large-scale problem into multiple weakly coupled subproblems based on the intrinsic structure of the variables. Our approach serves as a high-speed preprocessor that enhances the performance of conventional solvers, as shown in Fig. 1. Overview of the proposed method. Circles represent customers and the star represents the depot. (a) Master problem. (b) Partitioning of variables into red and blue sets. (c) Parallel solution of subproblems using a mathematical optimization solver. (d) Integration of subproblem solutions. Reprinted with permission from19, ©2025 IEEE. Therefore, this paper proposes a novel search-space decomposition method that exploits interaction costs between variables to generate weakly coupled subproblems. The proposed method focuses on clusters of closely related variables inherent in the problem and decomposes it at points where relationships between variables are weak. This strategy reduces the scale of the master problem by partitioning it into multiple weakly coupled subproblems, significantly improving search efficiency through parallel computing. To realize this decomposition, we introduce the constrained maximum cut problem (CMC), which uses interaction costs between variables and individual variable costs as edge and node weights, respectively. By casting the variable partitioning of variables into a weighted graph cut framework with balance constraints, the search-space decomposition can be rigorously formulated as the CMC. The maximum cut problem (MAX-CUT) is NP-hard, as shown by Karp20. Theoretical research has advanced in this area, including the approximation algorithm proposed by Goemans and Williamson21. Additionally, MAX-CUT is equivalent to finding the ground state of an Ising spin glass model22. Quantum annealing (QA) machines and other Ising machines are expected to efficiently search for low-energy states of the quadratic unconstrained binary optimization (QUBO) formulation or Ising model23–27. Recent comprehensive reviews have underscored the rapid evolution of quantum, hybrid, and quantum-inspired optimization algorithms, positioning them as essential methodologies for modern COPs28,29. Within this context, QA and hybrid frameworks have demonstrated significant promise in addressing a broad spectrum of NP-hard problems. For instance, these approaches have been successfully applied to financial portfolio optimization30, complex trajectory de-conflicting in air traffic management31, and the facility location problem32. An Ising model33 is defined on a graph G=(V,E), where V and E denote the sets of vertices and edges, respectively. The Hamiltonian H of the Ising model is defined as: where denotes the spin on vertex i ∈ V. The coefficients on the right-hand side, and , denote the interaction strength on edge (i, j) ∈ E and the external magnetic field at vertex i ∈ V, respectively. By incorporating the constraints of the CMC as penalty terms and expressing the resulting problem in a QUBO formulation34 or its equivalent representation, the Ising model, rapid decomposition becomes possible using QA machines or Ising machines. Therefore, the core methodological contribution of this study lies in the formulation of a novel CMC model, specifically designed to preserve the feasibility of solutions during the decomposition of large-scale COPs. Once the search space is decomposed using a QUBO formulation, the resulting subproblems are solved in parallel using mathematical optimization solvers. The remainder of this paper is organized as follows: Results, Discussion, and Methods. The Results section describes the proposed method and the experimental results. The Discussion section presents the insights gained from the experimental findings. The Methods section describes the dataset used in the experiments, the parameter settings for the proposed method, and the procedures used to generate the graphs of the experimental results. Results This section describes the proposed search-space decomposition method for large-scale COPs, the interaction costs used for decomposition, and the procedure for solving the resulting subproblems and constructing the final solution to the master problem. Finally, we present experimental results evaluated in terms of the feasible solution rate (FS rate), convergence speed, and variable reduction rate (VR rate). Formulation of the capacitated vehicle routing problem (CVRP) The CVRP addressed in this study is a variant of the vehicle routing problem (VRP) in which vehicles deliver customer demands from a single depot to multiple customers. Specifically, it involves assigning vehicles to customers and determining the visiting order to minimize the total distance or total transportation cost. In addition, each vehicle has a capacity limit, and all deliveries must satisfy these capacity constraints. The CVRP is defined on a graph G=(V,E), where denotes the set of vertices and E denotes the set of edges. Vertex 0 represents the depot, and the set denotes the customers. Each customer i ∈ S has a positive demand . Let denote the set of vehicles. There are K vehicles located at the depot, each with capacity Q. A non-negative travel cost is associated with each edge (i,j) ∈ E. The binary variable takes the value 1 if vehicle k travels from vertex i to vertex j, and 0 otherwise. In addition, the auxiliary variable represents the visiting order of customer i on vehicle k’s route and is used for subtour-elimination constraints. The formulation of the CVRP is as follows: Here, Eq. (2a) is the objective function, representing the minimization of the total travel cost. In addition, the roles of the constraints are described as follows. Equations (2b) and (2c) ensure that each vehicle k departs from the depot and returns to the depot. Equations (2d) and (2e) guarantee that exactly one vehicle visits and departs from each customer i. Equation (2f) is the flow conservation constraint, indicating that a vehicle entering a customer must also leave that customer. Equation (2g) is the capacity constraint, ensuring that the load of each vehicle does not exceed Q. Equations (2h) and (2i) eliminate subtours, defined as loops that do not pass through the depot. In this study, we use the capacity utilization rate (CUR) as an indicator of constraint tightness. The CUR is defined as the ratio of the total demand to the total vehicle capacity: A higher CUR indicates tighter capacity constraints and requires more accurate decomposition. Variable-based search-space decomposition algorithm This section describes Algorithm 1, which decomposes the search space. As a preprocessing step, we identify the index set to be partitioned for search-space decomposition. Typically, an index set with large cardinality is selected because its partitioning substantially reduces the subproblem size. Examples include the customer set () in the VRP and the item set in the multiple knapsack problem. We then set an upper bound on the subproblem size to ensure that each resulting subproblem remains manageable for a mathematical optimization solver. The algorithm stores the initial set in a list and repeats the following procedure until becomes empty. At each iteration, the algorithm retrieves a set from . If , it is added to the final list of subsets . Otherwise, is decomposed into two subsets and using the CMC, and these subsets are returned to . By recursively repeating these steps, the search space is decomposed until all sets eventually satisfy the specified upper bound. Decomposition of search spaces using the CMC The CMC-based decomposition algorithm for the search space was first proposed in our previous work19. This section explains the CMC formulation used to decompose the search space in Algorithm 1. The CMC is formulated using the binary decision variable in the objective function Eq. (4a) and the constraint Eq. (4b) as follows: Here, by utilizing the interaction costs between variables as edge weights and the individual variable costs as node weights, the multivariate problem is partitioned into two weakly coupled sets of variables. The parameter α () controls the desired fraction of the total individual variable cost assigned to one of the two subsets. Furthermore, this formulation corresponds to a quadratic binary optimization problem derived from MAX-CUT. The objective in Eq. (4a) corresponds to the weighted cut value of a graph, where assigning determines the partition of the vertex set. By incorporating the constraint as a quadratic penalty term into the objective function, the problem can be reformulated as a QUBO formulation as follows: Here, μ is a hyperparameter that controls the strength of the constraint term. Note that the sign change between Eqs. (4a) and (5) reflects the conversion from a maximization problem to an equivalent energy minimization formulation. In Eq. (5), the decomposition is achieved by maximizing the interaction costs between variables while enforcing balance between the two subsets through the parameters μ and α. Recursive search-space decomposition. Application of the proposed method to the CVRP This section describes how the search-space decomposition based on Eq. (5) is applied to large-scale CVRP instances. In the CVRP, the size of the search space primarily depends on the number of customers and grows exponentially as the number of customers increases. Therefore, the method focuses on partitioning the customer index set. In Eq. (5), the travel cost between customers is used as the edge weight representing interaction costs, and the customer demand is used as the node weight , enabling effective partitioning of the customer set. Furthermore, this paper examines two definitions of the interaction cost between customers. : Distance-based decomposition : Distance-based decomposition : Angular-based decomposition : Angular-based decomposition Distance-based decomposition The first method employs a distance metric based on physical proximity between customers as the interaction cost in the CMC. We refer to this method as distance-based decomposition (DBD). The interaction cost between variables, denoted as , is defined as the Euclidean distance between customers i and j. Because the underlying MAX-CUT objective seeks to maximize the weighted cut value, larger distances encourage edges between distant customers to be cut, placing them in different subsets, whereas nearby customers tend to remain in the same subset. This decomposition method is expected to reduce unnecessary long-distance travel when constructing the final delivery route. Furthermore, the demand quantity for each customer is incorporated as the node weight in the formulation. This design is motivated by the potential demand imbalance that may arise between the decomposed subsets. If the total demand becomes skewed between the subsets, solving the CVRP for each set may yield solutions that require more vehicles than defined in the master problem. Although such solutions are feasible at the subproblem level, they may violate the global vehicle constraints of the master problem. The Hamiltonian for the QUBO formulation in the first method is defined as follows: where represents the distance between customers i and j, and indicates the demand quantity for customer i. Furthermore, the demand balance coefficient represents the desired proportion of total demand assigned to one subset when vehicle capacities are identical. The coefficient α is defined as follows: The demand balance coefficient α is determined based on the number of vehicles. Therefore, the CMC formulation partitions customer variables by maximizing the total weighted cut value based on while enforcing demand balance through the parameters μ and α. Figure 2aillustrates the delivery area of the master problem. Figure 2billustrates the decomposition performed using DBD when there is no constraint term (i.e., μ =0), while Fig. 2cillustrates the case with a constraint term (i.e., μ>0). Illustration of DBD. (a) Delivery area of the master problem. (b) Decomposition result with μ = 0 and α = 0.5. (c) Decomposition result with μ> 0 and α = 0.5. The orange dashed line indicates the edges that are cut. Home icons (A–E) denote customers, the warehouse icon denotes the depot, vehicle icons indicate the number of vehicles, and cardboard box icons indicate customer demands. In this example, the demands of customers A, B, C, D, and E are 1, 3, 3, 4, and 2, respectively. Here, there are two vehicles, and α =0.5 is obtained from Eq. (7). In Fig. 2b, because the penalty term is absent, edges with larger distance weights are preferentially cut. Consequently, the graph is partitioned into two sets: and . The total demand in each set is and , respectively. In Fig. 2c, the penalty term is applied to balance the demand between the two subsets while still favoring the cutting of edges with large distance weights. Consequently, the graph is partitioned into and . This example illustrates the trade-off between maximizing the weighted cut value and satisfying the demand balance constraint controlled by μ. Angular-based decomposition The second method employs an angular indicator based on the relative direction from the depot. We refer to this method as angular-based decomposition (ABD). First, the location coordinates of the depot and customers in Euclidean space are transformed into a polar coordinate system centered at the depot. Then, the dissimilarity measure derived from the angular difference between two customers is defined as a feature representing their relative angular positions with respect to the depot, denoted as . The dissimilarity value is defined using θ as follows: where and denote the polar angles of customers i and j measured from the depot. Figure 3 illustrates the values of Eq. (8) as a function of and . Values of the dissimilarity measure as a function of and . Using this feature enables decomposition of customer variables while explicitly incorporating their positional relationship with the depot, which was not considered in the first method. Specifically, the larger the angular separation between two customers relative to the depot, the more likely they are to be classified into different clusters; conversely, smaller angular differences favor assignment to the same subset. As a result, customers located in similar directions from the depot are aggregated into the same cluster. This radial grouping reflects the geometric structure of the service area and facilitates construction of more efficient delivery routes in the subsequent routing phase. Unlike DBD, ABD captures directional structure relative to the depot, which is particularly relevant in capacitated routing problems where route efficiency depends on radial customer distribution. The Hamiltonian for the QUBO formulation of ABD is defined as follows: where represents the dissimilarity value defined in Eq. (8), and and α are as defined in the previous section. Figure 4 illustrates the decomposition performed using ABD. Here, each customer’s color represents the group to which the customer belongs, and the decomposition is performed such that customers located in the same angular direction from the depot belong to the same set. Schematic illustration of ABD. (a) Mapping of all customers onto a polar coordinate system with the depot as the origin. (b) Example result of solving the CMC using . The circles and the star denote customers and the depot, respectively. Subproblems after search-space decomposition After recursively applying the CMC-based decomposition until the stopping criteria are satisfied, the customer set of the master problem is partitioned into multiple subsets. The number of vehicles assigned to each subproblem is determined based on the total demand of the subset as , where Q denotes the vehicle capacity. Note that, due to the ceiling operation in the definition of , the total number of vehicles assigned to all subproblems, , may exceed the number of vehicles K in the master problem. However, the demand balance constraint controlled by α in the CMC formulation promotes an approximately even distribution of total demand across subsets, thereby limiting excessive fragmentation of vehicle assignments. Each CVRP subproblem is constructed by adding the depot and the corresponding number of vehicles to the customer subset. The routes obtained from all subproblems are then integrated to construct the solution to the master problem. The final solution is defined as the union of all routes generated for each subset, without additional re-optimization across subsets. FS rate and solution accuracy We calculated the FS rate, average gap (Avg. best-known solution (BKS) gap), and minimum gap (Min. BKS gap) with respect to the BKS for instances in which feasible solutions were obtained within 10 trials. Let FS obj. and BKS obj. denote the objective values of a feasible solution and the BKS, respectively. The gap is defined as: The experimental results for each method are shown in Table 1. As a baseline, hereafter referred to as the naive method, the CVRP is solved directly using only a mathematical optimization solver without decomposition. As the mathematical optimization solver, we use the heuristic functionality of Gurobi (v12.0.0), a state-of-the-art commercial solver widely used in academia and industry. For comparison purposes, the time limit for Gurobi was set to 30 min in the naive method. In the proposed method, each decomposed subproblem is solved independently, enabling parallel computation. Therefore, the computation time was set to 30 min for each subproblem in the proposed method. Consequently, the wall-clock time of the proposed method is at most 30 min, which is equal to that of the naive method. In the proposed method, in addition to Gurobi, we used neal35, an SA from the D-Wave Ocean SDK, to solve the CMC. We report the computation time of SA, denoted as SA time, required for partitioning. During decomposition, SA was executed 100 times per partitioning step, and the solution with the minimum energy was adopted. The SA time increases with the number of variables because partitioning is performed iteratively. The SA computation time is reported separately from the time limit imposed on the subproblem optimization. Table 1Comparison of results: FS rate, BKS gap, and SA time.MethodInstanceFS rateAvg. BKS gapMin. BKS gapSA time Naive methodM-n151-k12100%6.83%6.83%-M-n200-k17100%16.04%15.81%-X-n101-k250%---X-n200-k360%---X-n261-k13100%65.84%64.35%-X-n401-k290%---DBDM-n151-k12100%3.47%3.47%0.22sM-n200-k17100%9.17%9.17%1.56sX-n101-k250%---X-n200-k3630%3.94%3.39%0.47sX-n261-k13100%8.16%8.16%2.40sX-n401-k2910%11.20%11.20%5.57sABDM-n151-k12100%5.61%5.61%0.19sM-n200-k17100%8.95%8.95%1.23sX-n101-k250%---X-n200-k3660%5.61%4.59%0.48sX-n261-k13100%9.49%9.01%2.14sX-n401-k29100%8.66%6.92%5.41s Comparison of results: FS rate, BKS gap, and SA time. The results indicate that for large-scale instances with a CUR exceeding approximately 98% (e.g., X-n200-k36, X-n401-k29, listed in Table 3), the naive method failed to find feasible solutions within the time limit. In contrast, the proposed method successfully obtained feasible solutions for these instances. Notably, ABD achieved a 100% success rate for the X-n401-k29 instance. Regarding solution accuracy, the proposed method demonstrated substantial improvements over the naive method in terms of the gap to the BKS (Table 1). In instances where the naive method found feasible solutions, the proposed method improved solution accuracy by approximately 3–50 percentage points. For example, in the X-n261-k13 instance, the naive method had an average BKS gap of 65.84%, whereas the proposed method using DBD reduced this value to 8.16%. Notably, for all instances where feasible solutions were obtained, ABD consistently provided high-quality solutions, with the average BKS gap ranging from 5.61% to 9.49%. Table 3CVRPLIB instance information.InstanceThe number of customersThe number of vehiclesCapacityBKSCURM-n151-k121501220010530.9313M-n200-k171991720013730.9371X-n101-k2510025206275910.9994X-n200-k3619936402585780.9856X-n261-k13260131081265580.9522X-n401-k2940029745661540.9847 CVRPLIB instance information. Improved convergence speed of solutions We measured the time from acquisition of the initial feasible solution until the gap with respect to the BKS stabilized. Figure 5 shows the convergence curves of the gap for the three instances in which feasible solutions were obtained using all methods. The proposed method converged substantially faster than the naive method. Specifically, the solution accuracy achieved by the naive method in 30 min was attained by the proposed method in approximately 1 min. Furthermore, the advantage in convergence speed became more pronounced as problem size increased. Convergence performance over time for the naive method and the two proposed methods. (a) M-n151-k12. (b) M-n200-k17. (c) X-n261-k13. Variable reduction through search-space decomposition Table 2 presents the difference in the number of variables as an indicator of the search space reduction achieved by the proposed method. The number of variables is calculated as , where |V| denotes the number of vertices including both customers and the depot, |S| denotes the number of customers, and K denotes the number of vehicles. In the proposed method, the number of variables is calculated for each subproblem, and the sum is taken as the final number of variables. The choice of interaction cost had no significant effect on the VR rate. Compared with the naive method, the proposed method achieved reductions ranging from approximately 74.65% to 95.32%. The reduction rate tended to increase as the number of customers increased, indicating scalability for large-scale problems. These results quantitatively demonstrate that recursive decomposition substantially reduces the dimensionality of the optimization problem. Table 2Number of variables and VR rates for the naive and proposed methods.InstanceNaive methodDBDABDVR rateVR rateM-n151-k12273,60069,30074.67%69,34874.65%M-n200-k17679,98399,95285.30%101,89685.01%X-n200-k361,439,964224,23584.43%221,79684.60%X-n261-k13885,56057,43893.51%58,33493.41%X-n401-k294,663,200218,61395.31%218,37095.32% Number of variables and VR rates for the naive and proposed methods. Discussion The results of this study indicate that recursive search-space decomposition using the CMC, solved via a QUBO formulation, is a highly effective hybrid approach for large-scale COPs. It is important to note that although the CVRP was used as the main benchmark in this study, the proposed CMC-based decomposition is intended to be a framework that is not specific to a particular problem. The CMC’s mathematical structure depends solely on the definition of interaction weights between variables and node-specific costs. Therefore, this approach can be theoretically extended to other large-scale COPs, such as facility location or scheduling, as long as the coupling between variables can be mapped onto an edge-weighted graph. While conventional solvers struggle with monolithic instances because of exponential expansion of the search space, the proposed method systematically reduces complexity by partitioning the master problem into independent subproblems. A key finding is the clear advantage of ABD over DBD in high-CUR instances. By utilizing the dissimilarity value based on the relative direction from the depot, ABD tends to produce subproblems that include a more balanced distribution of customers from both near and distant locations. This approach facilitates generation of more efficient delivery routes compared with DBD, which primarily emphasizes physical proximity without explicitly incorporating directional structure relative to the depot. The successful application of both DBD and ABD shows that our decomposition, the CMC-based approach, is not over-fitted to a specific distance metric, but rather, it can handle diverse definitions of variable relationships. However, for the X-n101-k25 instance, which has the highest CUR (0.9994) among all tested instances, none of the methods, including ABD, found feasible solutions. This finding suggests that when the capacity constraint is nearly saturated, even balanced decomposition cannot guarantee feasibility, and additional strategies, such as relaxing the vehicle count or incorporating slack variables, may be required. Another practical consideration is tuning of the penalty coefficient μ. In the current implementation, μ is incremented in steps whose granularity depends on the scale of the interaction cost, with integer steps for DBD and finer steps of 0.001 for ABD. While this ensured feasibility for the tested instances, it should be emphasized that μ can be efficiently determined using a binary search algorithm. By applying a binary search to find the minimum μ that satisfies the constraints, the parameter selection process becomes entirely systematic and reproducible, regardless of the cost scale of the problem instance. Developing a fully adaptive or automated strategy for setting μ (e.g., based on the ratio of objective and penalty scales) is another important direction for future work. It is worth noting that classical graph partitioning tools such as METIS36 and clustering methods such as k-means can also partition customer sets. METIS supports vertex-weighted and multi-constraint partitioning, and can in principle enforce a demand-balancing constraint by assigning customer demand as the vertex weight. The key distinction of the present framework therefore does not lie in the ability to balance demand intrinsically, but in two other aspects. First, METIS minimizes the edge cut using a tailored multilevel heuristic specific to classical hardware, whereas our formulation expresses the partitioning task as a MAX-CUT-based QUBO so that the same mathematical problem can be delegated to any Ising-model solver, including simulated annealing-based solvers, digital Ising machines, and quantum annealers. Second, the choice of a MAX-CUT objective with dissimilarity-based edge weights (such as the distance or the angular dissimilarity ) makes it natural to express routing-oriented heuristics, placing distant customers in different subproblems, or grouping customers sharing a radial direction from the depot, which would instead require a dedicated similarity transformation under a MIN-CUT formulation. An empirical benchmark against METIS and other classical partitioners under matched weight definitions is an important direction for future work. Although this formulation provides a clear conceptual advantage for highly constrained problems, a systematic experimental comparison with alternative partitioning strategies remains an important topic for future investigation. The computational overhead of this decomposition is minimal, with SA times on the order of seconds. This high-speed preprocessing enables mathematical optimization solvers to reach high-quality solutions up to 30 times faster than the naive method in certain instances. Although the experiments were conducted on a single multi-core machine (Apple M3 Max), the proposed method is inherently suitable for distributed computing environments, where each subproblem can be dispatched to a separate node. In such settings, the wall-clock time advantage is expected to be even more pronounced, particularly for large-scale industrial instances that yield many subproblems. Furthermore, a VR rate of up to 95.32% indicates the scalability of this approach for real-world industrial applications. Future work will explore the application of this framework to other optimization domains such as scheduling and facility location problems. Methods This section describes the experimental setup used to compare the naive and proposed methods. Experimental setup We evaluated the proposed method using benchmark instances from CVRPLIB37 for the CVRP, a representative COP. Table 3 summarizes the characteristics of the six instances used in this study. The instance names follow the standard CVRPLIB naming convention S-nY-kZ, where S denotes the instance set or series (e.g., M, X), nY represents the total number of nodes Y including customers and the single depot and kZ indicates the number of vehicles Z required for the BKS. The six instances from CVRPLIB were strategically selected to encompass a wide range of problem characteristics that define the complexity of the CVRP. These characteristics include, as follows: Scale: With the number of customers ranging from 100 to 400 Scale: With the number of customers ranging from 100 to 400 Depot Positioning: Covering both centralized locations (e.g., M-n151, X-n101) and corner or edge positions (e.g., X-n401, X-n261) Depot Positioning: Covering both centralized locations (e.g., M-n151, X-n101) and corner or edge positions (e.g., X-n401, X-n261) Constraint tightness: Represented by the Capacity Utilization Ratio (CUR), including highly saturated instances such as X-n101-k25 Constraint tightness: Represented by the Capacity Utilization Ratio (CUR), including highly saturated instances such as X-n101-k25 Spatial distribution: Including both uniform radial patterns and irregular clustered distributions Spatial distribution: Including both uniform radial patterns and irregular clustered distributions This selection ensures a comprehensive evaluation across diverse topological and constraint-related problem settings. All computational tasks in this study were executed on a MacBook Pro with an Apple M3 Max chip (16-core CPU, 40-core GPU) and 128 GB of Unified Memory. This includes executing the D-Wave neal (simulated annealing sampler) solver to solve the CMC-based search-space decomposition and executing the Gurobi optimizer (version 12.0.0) to optimize both the naive and proposed methods. Details of solvers used in the experiments This section explains the solvers used to solve the CMC and CVRP in the naive and proposed methods. As a baseline, hereafter referred to as the naive method, the CVRP is solved directly using only a mathematical optimization solver without decomposition. As the mathematical optimization solver, we use the heuristic functionality of Gurobi (v12.0.0), a state-of-the-art commercial solver widely used in academia and industry. For comparison purposes, the time limit for Gurobi was set to 30 min in the naive method. In the proposed method, each decomposed subproblem is solved independently, enabling parallel computation. Therefore, the computation time was set to 30 min for each subproblem. Consequently, the wall-clock time of the proposed method is at most 30 min, which is equal to that of the naive method. In the proposed method, in addition to Gurobi, we used neal, an SA from the D-Wave Ocean SDK, to solve the CMC. We report the computation time of SA, denoted as SA time, required for partitioning. During decomposition, SA was executed 100 times per partitioning step, and the solution with the minimum energy was adopted. The SA time increases with the number of variables because partitioning is performed iteratively. The SA computation time is reported separately from the time limit imposed on subproblem optimization. Experiments using Gurobi were conducted with default parameter settings except for the computation time. Similarly, experiments using SA were conducted with default parameter settings except for the number of executions. Parameter settings of the proposed method This section explains the various parameters involved in solving the CMC in the proposed method. First, the value of , which determines the recursive application of the CMC in Algorithm 1, was set to 100. This choice was made because the Gurobi heuristic can compute an initial solution within tens of seconds at this scale. The hyperparameter μ, which represents the strength of the constraint term in the proposed method, was determined appropriately for each cost scale and each problem instance. Specifically, in Eq. (6) for DBD, the range of is wide because it represents actual distances. Therefore, μ was incremented as until the penalty term was sufficiently strong to enforce the demand balance specified by α. In contrast, in Eq. (9) for ABD, the range of is limited (). Therefore, μ was incremented in finer steps as . The same stopping criterion as in DBD was applied. Construction of convergence curves This section explains how the convergence curves in Fig. 5 are constructed to compare the naive method with the two proposed methods. Because the proposed method solves each subproblem in parallel, the initial plot corresponds to the maximum time required to obtain initial feasible solutions across all subproblems and the gap between the resulting total objective value and the BKS. Subsequently, whenever an improved solution is obtained for a subproblem, the elapsed wall-clock time is updated and the previous FS obj. is replaced with the FS obj. of the improved solution. This procedure is repeated until the time limit is reached, yielding the convergence curves. Acknowledgements This work was partially supported by the Council for Science, Technology, and Innovation (CSTI) through the Cross-ministerial Strategic Innovation Promotion Program (SIP), “Promoting the application of advanced quantum technology platforms to social issues” (Funding agency: QST), Japan Science and Technology Agency (JST) (Grant Number JPMJPF2221). S. Tanaka expresses gratitude to the World Premier International Research Center Initiative (WPI), MEXT, Japan, for their support of the Human Biology-Microbiome-Quantum Research Center (Bio2Q). The authors would like to thank IEEE for permission to reuse Fig. 1 from our previous conference paper19. We would like to thank Editage (www.editage.jp) for English language editing. Author contributions E. K. conceived the idea, performed simulations, and wrote the manuscript. S. K., H. T., and S. T. discussed and commented on the manuscript, and S. T. supervised the project. All authors reviewed the manuscript. Data availability The data that support the findings of this study are available from the corresponding author upon reasonable request. Declarations Competing interests The authors declare no competing interests. Footnotes Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. References Associated Data Data Availability Statement The data that support the findings of this study are available from the corresponding author upon reasonable request.