Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.23038 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914353638277120 |
|---|---|
| author | Kawase, Eiji Kikuchi, Shuta Tamai, Hideaki Tanaka, Shu |
| author_facet | Kawase, Eiji Kikuchi, Shuta Tamai, Hideaki Tanaka, Shu |
| contents | Combinatorial 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_23038 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Parallelizable Search-Space Decomposition for Large-Scale Combinatorial Optimization Problems Using Ising Machines Kawase, Eiji Kikuchi, Shuta Tamai, Hideaki Tanaka, Shu Emerging Technologies Combinatorial 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. |
| title | Parallelizable Search-Space Decomposition for Large-Scale Combinatorial Optimization Problems Using Ising Machines |
| topic | Emerging Technologies |
| url | https://arxiv.org/abs/2602.23038 |