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

arXiv:2406.01887 · IEEE Access

Annealing-Assisted Column Generation for Inequality-Constrained Combinatorial Optimization Problems

Hiroshi Kanai, Masashi Yamashita, Kotaro Tanahashi, Shu Tanaka

Published Jan 1, 2024• 16 citations
arXivHTMLPDF

Abstract

Ising machines are expected to solve combinatorial optimization problems faster than the existing integer programming solvers. These problems, particularly those encountered in practical situations, typically involve inequality constraints. However, owing to the hardware limitations of the current Ising machines, solving combinatorial optimization problems with inequality constraints remains challenging. The Capacitated Vehicle Routing Problem (CVRP) is a typical example of a problem with inequality constraints. The CVRP is classified as${\mathcal {NP}}$-hard and, thus, is commonly solved using heuristic algorithms, such as column generation. Column generation attempts to iteratively generate only the promising routes, as the number of feasible routes increases exponentially. Within this framework, the CVRP is formulated as a set cover problem. The corresponding dual solutions are used to define the pricing subproblem, which is intended to create a new route. By applying Ising machines to this pricing subproblem, the overall computation time can be reduced. This study aims to solve combinatorial optimization problems with inequality constraints using a hybrid algorithm that combines column generation and Ising machines, thereby extending the applications of the latter. Additionally, we introduced limited column generation, wherein we fixed the decision variables to eliminate the overlap between the generated columns. By reducing unnecessary variables, our proposed method can overcome the hardware limitations where a small number of variables is available on real devices. We parameterize the difficulty of the inequality constraints and demonstrate that our annealing-assisted column generation can converge to a better lower bound.

DOI
10.1109/access.2024.3486768

Related papers

Solving Capacitated Vehicle Routing Problem with Quantum Alternating Operator Ansatz and Column Generation

Wei‐Hao Huang, Hiromichi Matsuyama, Yu Yamashiro

This study proposes a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problem (CVRP) by integrating the Column Generation (CG) method with the Quantum Alternating Operator Ansatz (QAOAnsatz). The CG method divides the CVRP into the reduced master problem, which finds the best combination of the routes under the route set, and one or more subproblems, which generate the routes that would be beneficial to add to the route set. This method is iteratively refined by adding new routes identified via subproblems and continues until no improving route can be found. We leverage the QAOAnsatz to solve the subproblems. Our algorithm restricts the search space by designing the QAOAnsatz mixer Hamiltonian to enforce one-hot constraints. Moreover, to handle capacity constraints in QAOAnsatz, we employ an Augmented Lagrangian-inspired method that obviates the need for additional slack variables, reducing the required number of qubits. Experimental results on small-scale CVRP instances (up to 6 customers) show that QAOAnsatz converges more quickly to optimal routes than the standard QAOA approach, demonstrating the potential of this hybrid framework in tackling realworld logistical optimization problems on near-term quantum hardware.

arXiv:2503.17051•International Conference on Quantum Communications, Networking, and Computing (QCNC)•Apr 6, 2026•7 citations

Hybrid Quantum-Classical Algorithm for Solving Capacitated Vehicle Routing Problems

Wei‐Hao Huang, Hiromichi Matsuyama, Yu Yamashiro

This study introduces a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problems (CVRP), combining the Column Generation method and the Quantum Alternating Operator Ansatz (QAOAnsatz). The column generation method divides the problem into a master problem and subproblems to effectively solve the problem. We solved the subproblem by using QAOAnsatz to enhance the optimal solution search. Moreover, we generated the problem Hamiltonian using an Augmented Lagrangian-inspired Method to reduce the number of required qubits to handle the inequality. As a result, our experiments obtained an optimal solution for a CVRP problem with 6 customers. This study demonstrates a practical quantum application in logistics and sets a new technique for hybrid quantum-classical optimization frameworks.

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

Optimization of quantum annealing for the capacitated vehicle routing problem

Akiyoshi Wakatani

We implement and evaluate the performance of two methods to reduce the number of decision variables used in the search for the optimal solution to CVRP (Capacitated Vehicle Routing Problem), which is one of the combinatorial optimization problems. When reducing decision variables in consideration of the number of routes, we evaluated two methods: one is to reduce decision variables by fixing some values of decision variables and the other is to reduce the generation of decision variables themselves. The former method has a limited effect of speeding up the process by decision variable reduction. The latter method, however, achieved a speedup of approximately 2 times, although it depends on the number of cities visited.

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

HyCiM: A Hybrid Computing-in-Memory QUBO Solver for General Combinatorial Optimization Problems with Inequality Constraints

Yu Qian, Zeyu Yang, Kai Ni +3 more

Computationally challenging combinatorial optimization problems (COPs) play a fundamental role in various applications. To tackle COPs, many Ising machines and Quadratic Unconstrained Binary Optimization (QUBO) solvers have been proposed, which typically involve direct transformation of COPs into Ising models or equivalent QUBO forms (D-QUBO). However, when addressing COPs with inequality constraints, this D-QUBO approach introduces numerous extra auxiliary variables, resulting in a substantially larger search space, increased hardware costs, and reduced solving efficiency. In this work, we propose HyCiM, a novel hybrid computing-inmemory (CiM) based QUBO solver framework, designed to overcome aforementioned challenges. The proposed framework consists of (i) an innovative transformation method (first to our known) that converts COPs with inequality constraints into an inequality-QUBO form, thus eliminating the need of expensive auxiliary variables and associated calculations; (ii) "inequality filter", a ferroelectric FET (FeFET)-based CiM circuit that accelerates the inequality evaluation, and filters out infeasible input configurations; (iii) a FeFET-based CiM annealer that is capable of approaching global solutions of COPs via iterative QUBO computations within a simulated annealing process. The evaluation results show that HyCiM drastically narrows down the search space, eliminating 2100 to 22536 infeasible input configurations compared to the conventional D-QUBO approach. Consequently, the narrowed search space, reduced to 2100 feasible input configurations, leads to a substantial hardware area overhead reduction, ranging from 88.06% to 99.96%. Additionally, HyCiM consistently exhibits a high solving efficiency, achieving a remarkable average success rate of 98.54%, whereas D-QUBO implementatoin shows only 10.75%.

arXiv:2410.14111•ACM/IEEE Design Automation Conference (DAC)•Jun 23, 2024•9 citations

A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer

Sebastian Feld, Christoph Roch, Thomas Gabor +5 more

The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that has been of great interest for decades for both, science and industry. The CVRP is a variant of the vehicle routing problem characterized by capacity constrained vehicles. The aim is to plan tours for vehicles to supply a given number of customers as efficiently as possible. The problem is the combinatorial explosion of possible solutions, which increases superexponentially with the number of customers. Classical solutions provide good approximations to the globally optimal solution. D-Wave's quantum annealer is a machine designed to solve optimization problems. This machine uses quantum effects to speed up computation time compared to classic computers. The problem on solving the CVRP on the quantum annealer is the particular formulation of the optimization problem. For this, it has to be mapped onto a quadratic unconstrained binary optimization (QUBO) problem. Complex optimization problems such as the CVRP can be translated to smaller subproblems and thus enable a sequential solution of the partitioned problem. This work presents a quantum-classic hybrid solution method for the CVRP. It clarifies whether the implemenation of such a method pays off in comparison to existing classical solution methods regarding computation time and solution quality. Several approaches to solving the CVRP are elaborated, the arising problems are discussed, and the results are evaluated in terms of solution quality and computation time.

arXiv:1811.07403•Frontiers in ICT•Jun 25, 2019•233 citations

Scaling Vehicle Routing Problem Solvers with QUBO-based Specialized Hardware

Hanjing Xu, Hayato Ushijima‐Mwesigwa, Indradeep Ghosh

The Vehicle Routing Problem (VRP) is an NP-Hard optimization problem that has been widely studied over the last decades due to its wide practical applications. The goal of the VRP is to design efficient routes for vehicles performing service functions such as the distribution of goods from one or more central locations. There exist many variants to the VRP. These variations arise due to application-specific constraints such as vehicle capacities, delivery time windows, split deliveries, and many more. Due to the complexity of the problem, solvers are usually designed for specific variants and do not generally scale well to larger problem instances. As we approach the physical scaling limits of Moore's law, different novel special-purpose hardware are being designed for solving combinatorial optimization problems such as quantum and quantum-inspired devices. However, these devices are able to solve problems up to fixed variable sizes. In this work, we carry out experiments on the Fujitsu Digital Annealer (DA), quantum-inspired hardware, and show that we are able to get near-optimal results for instances of the Capacitated VRP (CVRP) that can be directly solved on the DA. We further develop a hybrid method for solving large-scale VRP instances. In order to achieve this, we develop a novel candidate route generation method, whose core solves a multi-objective clustering problem on the DA. Once a set of candidate routes has been selected, we then solve a Set Partitioning Problem on the DA to get a final solution. We apply our method to the CVRP and the CVRP with Time-Windows and show that we are able to get near-optimal solutions for problem instances significantly larger the base solvers could solve directly, within the same amount of computation time.

IEEE/ACM Symposium on Edge Computing (SEC)•Dec 1, 2022•3 citations
Ising machines are expected to solve combinatorial optimization problems faster than the existing integer programming solvers. These problems, particularly those encountered in practical situations, typically involve inequality constraints. However, owing to the hardware limitations of the current Ising machines, solving combinatorial optimization problems with inequality constraints remains challenging. The Capacitated Vehicle Routing Problem (CVRP) is a typical example of a problem with inequality constraints. The CVRP is classified asNP{\mathcal {NP}}NP-hard and, thus, is commonly solved using heuristic algorithms, such as column generation. Column generation attempts to iteratively generate only the promising routes, as the number of feasible routes increases exponentially. Within this framework, the CVRP is formulated as a set cover problem. The corresponding dual solutions are used to define the pricing subproblem, which is intended to create a new route. By applying Ising machines to this pricing subproblem, the overall computation time can be reduced. This study aims to solve combinatorial optimization problems with inequality constraints using a hybrid algorithm that combines column generation and Ising machines, thereby extending the applications of the latter. Additionally, we introduced limited column generation, wherein we fixed the decision variables to eliminate the overlap between the generated columns. By reducing unnecessary variables, our proposed method can overcome the hardware limitations where a small number of variables is available on real devices. We parameterize the difficulty of the inequality constraints and demonstrate that our annealing-assisted column generation can converge to a better lower bound.
This study proposes a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problem (CVRP) by integrating the Column Generation (CG) method with the Quantum Alternating Operator Ansatz (QAOAnsatz). The CG method divides the CVRP into the reduced master problem, which finds the best combination of the routes under the route set, and one or more subproblems, which generate the routes that would be beneficial to add to the route set. This method is iteratively refined by adding new routes identified via subproblems and continues until no improving route can be found. We leverage the QAOAnsatz to solve the subproblems. Our algorithm restricts the search space by designing the QAOAnsatz mixer Hamiltonian to enforce one-hot constraints. Moreover, to handle capacity constraints in QAOAnsatz, we employ an Augmented Lagrangian-inspired method that obviates the need for additional slack variables, reducing the required number of qubits. Experimental results on small-scale CVRP instances (up to 6 customers) show that QAOAnsatz converges more quickly to optimal routes than the standard QAOA approach, demonstrating the potential of this hybrid framework in tackling realworld logistical optimization problems on near-term quantum hardware.
This study introduces a hybrid quantum-classical approach to solving the Capacitated Vehicle Routing Problems (CVRP), combining the Column Generation method and the Quantum Alternating Operator Ansatz (QAOAnsatz). The column generation method divides the problem into a master problem and subproblems to effectively solve the problem. We solved the subproblem by using QAOAnsatz to enhance the optimal solution search. Moreover, we generated the problem Hamiltonian using an Augmented Lagrangian-inspired Method to reduce the number of required qubits to handle the inequality. As a result, our experiments obtained an optimal solution for a CVRP problem with 6 customers. This study demonstrates a practical quantum application in logistics and sets a new technique for hybrid quantum-classical optimization frameworks.
We implement and evaluate the performance of two methods to reduce the number of decision variables used in the search for the optimal solution to CVRP (Capacitated Vehicle Routing Problem), which is one of the combinatorial optimization problems. When reducing decision variables in consideration of the number of routes, we evaluated two methods: one is to reduce decision variables by fixing some values of decision variables and the other is to reduce the generation of decision variables themselves. The former method has a limited effect of speeding up the process by decision variable reduction. The latter method, however, achieved a speedup of approximately 2 times, although it depends on the number of cities visited.
Computationally challenging combinatorial optimization problems (COPs) play a fundamental role in various applications. To tackle COPs, many Ising machines and Quadratic Unconstrained Binary Optimization (QUBO) solvers have been proposed, which typically involve direct transformation of COPs into Ising models or equivalent QUBO forms (D-QUBO). However, when addressing COPs with inequality constraints, this D-QUBO approach introduces numerous extra auxiliary variables, resulting in a substantially larger search space, increased hardware costs, and reduced solving efficiency. In this work, we propose HyCiM, a novel hybrid computing-inmemory (CiM) based QUBO solver framework, designed to overcome aforementioned challenges. The proposed framework consists of (i) an innovative transformation method (first to our known) that converts COPs with inequality constraints into an inequality-QUBO form, thus eliminating the need of expensive auxiliary variables and associated calculations; (ii) "inequality filter", a ferroelectric FET (FeFET)-based CiM circuit that accelerates the inequality evaluation, and filters out infeasible input configurations; (iii) a FeFET-based CiM annealer that is capable of approaching global solutions of COPs via iterative QUBO computations within a simulated annealing process. The evaluation results show that HyCiM drastically narrows down the search space, eliminating 2100 to 22536 infeasible input configurations compared to the conventional D-QUBO approach. Consequently, the narrowed search space, reduced to 2100 feasible input configurations, leads to a substantial hardware area overhead reduction, ranging from 88.06% to 99.96%. Additionally, HyCiM consistently exhibits a high solving efficiency, achieving a remarkable average success rate of 98.54%, whereas D-QUBO implementatoin shows only 10.75%.
The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that has been of great interest for decades for both, science and industry. The CVRP is a variant of the vehicle routing problem characterized by capacity constrained vehicles. The aim is to plan tours for vehicles to supply a given number of customers as efficiently as possible. The problem is the combinatorial explosion of possible solutions, which increases superexponentially with the number of customers. Classical solutions provide good approximations to the globally optimal solution. D-Wave's quantum annealer is a machine designed to solve optimization problems. This machine uses quantum effects to speed up computation time compared to classic computers. The problem on solving the CVRP on the quantum annealer is the particular formulation of the optimization problem. For this, it has to be mapped onto a quadratic unconstrained binary optimization (QUBO) problem. Complex optimization problems such as the CVRP can be translated to smaller subproblems and thus enable a sequential solution of the partitioned problem. This work presents a quantum-classic hybrid solution method for the CVRP. It clarifies whether the implemenation of such a method pays off in comparison to existing classical solution methods regarding computation time and solution quality. Several approaches to solving the CVRP are elaborated, the arising problems are discussed, and the results are evaluated in terms of solution quality and computation time.
The Vehicle Routing Problem (VRP) is an NP-Hard optimization problem that has been widely studied over the last decades due to its wide practical applications. The goal of the VRP is to design efficient routes for vehicles performing service functions such as the distribution of goods from one or more central locations. There exist many variants to the VRP. These variations arise due to application-specific constraints such as vehicle capacities, delivery time windows, split deliveries, and many more. Due to the complexity of the problem, solvers are usually designed for specific variants and do not generally scale well to larger problem instances. As we approach the physical scaling limits of Moore's law, different novel special-purpose hardware are being designed for solving combinatorial optimization problems such as quantum and quantum-inspired devices. However, these devices are able to solve problems up to fixed variable sizes. In this work, we carry out experiments on the Fujitsu Digital Annealer (DA), quantum-inspired hardware, and show that we are able to get near-optimal results for instances of the Capacitated VRP (CVRP) that can be directly solved on the DA. We further develop a hybrid method for solving large-scale VRP instances. In order to achieve this, we develop a novel candidate route generation method, whose core solves a multi-objective clustering problem on the DA. Once a set of candidate routes has been selected, we then solve a Set Partitioning Problem on the DA to get a final solution. We apply our method to the CVRP and the CVRP with Time-Windows and show that we are able to get near-optimal solutions for problem instances significantly larger the base solvers could solve directly, within the same amount of computation time.