Quadratic unconstrained binary optimization (QUBO) models have garnered growing interests as a strong alternative modelling framework for solving combinatorial optimization problems. A wide variety of optimization problems that are usually studied using conventional Operations Research approaches can be formulated as QUBO problems. However, QUBO solvers do not guarantee optimality when solving optimization problems. Instead, obtaining high quality solutions using QUBO solvers entails tuning of multiple parameters. Here in our work, we conjecture that the initial states adjustment method used in QUBO solvers can be improved, where careful tuning will yield overall better results. We propose a data-driven multi-start algorithm that complements the QUBO solver (namely Fujitsu Digital Annealer) in solving constrained optimization problems. We implemented our algorithm on a variety of capacitated vehicle routing problem instances, and empirical results show that different initial state adjustment methods do make a difference in the quality of solutions obtained by the QUBO solver.
Quadratic unconstrained binary optimization (QUBO) models have garnered growing interests as a strong alternative modelling framework for solving combinatorial optimization problems. A wide variety of optimization problems that are usually studied using conventional Operations Research approaches can be formulated as QUBO problems. However, QUBO solvers do not guarantee optimality when solving optimization problems. Instead, obtaining high quality solutions using QUBO solvers entails tuning of multiple parameters. Here in our work, we conjecture that the initial states adjustment method used in QUBO solvers can be improved, where careful tuning will yield overall better results. We propose a data-driven multi-start algorithm that complements the QUBO solver (namely Fujitsu Digital Annealer) in solving constrained optimization problems. We implemented our algorithm on a variety of capacitated vehicle routing problem instances, and empirical results show that different initial state adjustment methods do make a difference in the quality of solutions obtained by the QUBO solver.
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.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu’s Digital Annealer (DA) and D-Wave’s Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum.We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
Recent hardware developments in quantum technologies have inspired a myriad of special-purpose hardware devices tasked to solve optimization problems. In this paper, we explore the application of Fujitsu's quantum-inspired CMOS-based Digital Annealer (DA) in solving constrained routing problems arising in transportation and logistics. More precisely in this paper, we study the vehicle sharing problem and show that the DA as a QUBO solver can potentially fill the gap between two common methods: exact solvers like Cplex and heuristics. We benchmark the scalability and quality of solutions obtained by DA with Cplex and with a greedy heuristic. Our results show that the DA is a general QUBO solver that is more robust than heuristics, and more scalable than Cplex. Our methodology and framework which focus on QUBO problems is also applicable to other quantum-inspired and fully quantum devices that are undergoing development.
As Moore’s Law slows, alternative computing paradigms are essential for tackling complex combinatorial optimization problems. This paper introduces DigiQUBO, a high-performance digital Quadratic Unconstrained Binary Optimization (QUBO) solver designed for quantum-inspired optimization. DigiQUBO leverages a advanced Digital Annealing (DA) approach to efficiently solve large-scale QUBO problems, offering a competitive alternative to traditional annealing methods. To evaluate its effectiveness, DigiQUBO is applied to the Traveling Salesman Problem (TSP), a well-known NP-hard problem with applications in logistics, network design, and computational biology. In solving a 40-city Traveling Salesman Problem (TSP), DigiQUBO achieved an average route distance improvement of 13% compared to Simulated Annealing (SA), and a reduction of 37% compared to D-Wave’s LeapHybridSampler, while maintaining comparable runtime to Fujitsu DA3. DigiQUBO significantly enhances solution quality and computational efficiency by integrating two key advanced techniques: two-way one-hot group encoding for improved constraint satisfaction and Bayesian Optimization for automated annealing parameter tuning. Performance comparisons against Simulated Annealing (SA), Fujitsu DA3, and D-Wave’s LeapHybridSampler demonstrate superior results in balancing accuracy and execution time. The results highlight DigiQUBO as a promising digital annealing technology that bridges the gap between classical and quantum optimization, offering a practical and efficient solution in the post-Moore’s Law era.
This paper proposes a novel dispatch formulation for micro-mobility vehicles using a Quantum Annealer (QA). In recent years, QA has gained increasing attention as a high-performance solver for combinatorial optimization problems. Meanwhile, micro-mobility services have been rapidly developed as a promising means of realizing efficient and sustainable urban transportation. In this study, the dispatch problem for such micro-mobility services is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, enabling efficient solving through QA. Furthermore, the proposed formulation incorporates historical usage data to enhance operational efficiency. Specifically, customer arrival frequencies and destination distributions are modeled into the QUBO formulation through a Bayesian approach, which guides the allocation of vacant vehicles to designated stations for waiting and charging. Simulation experiments are conducted to evaluate the effectiveness of the proposed method, with comparisons to conventional formulations such as the vehicle routing problem. Additionally, the performance of QA is compared with that of classical solvers to reveal its potential advantages for the proposed dispatch formulation. The effect of reverse annealing on improving solution quality is also investigated.