QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems
Eneko Osaba Esther Villar-Rodriguez


QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems
QOPTLib

Osaba and Villar-Rodriguez
Eneko Osaba (Corresponding Author), Esther Villar-Rodriguez TECNALIA, Basque Research and Technology Alliance (BRTA), 48160 Derio, Spain eneko.osaba@tecnalia.com, esther.villar@tecnalia.com

*
    Eneko Osaba and Esther Villar-Rodriguez
    April 29, 2024
===========================================



In this paper, we propose a quantum computing oriented benchmark for combinatorial optimization. This benchmark, coined as , is composed of 40 instances equally distributed over four well-known problems: Traveling Salesman Problem, Vehicle Routing Problem, one-dimensional Bin Packing Problem and the Maximum Cut Problem. The sizes of the instances in  not only correspond to computationally addressable sizes, but also to the maximum length approachable with non-zero likelihood of getting a good result. In this regard, it is important to highlight that hybrid approaches are also taken into consideration. Thus, this benchmark constitutes the first effort to provide users a general-purpose dataset. Also in this paper, we introduce a first full solving of  using two solvers based on quantum annealing. Our main intention with this is to establish a preliminary baseline, hoping to inspire other researchers to beat these outcomes with newly proposed quantum-based algorithms.





§ INTRODUCTION



Quantum Computing is expected to provide researchers and practitioners with a novel and revolutionary paradigm for dealing with complex problems in a more efficient way <cit.>. This kind of computation leverages quantum phenomena to find competent solutions via Quantum Processing Units (QPU). The potential of quantum computing has become apparent in several examples such as the Shor factorization algorithm <cit.> and the Grover quantum search algorithm <cit.>. 

So far, there have been several research areas in which quantum computing has shown its potential, such as cryptography <cit.>, simulation <cit.>, machine learning <cit.> or optimization <cit.>. This paper is focused on the last of this research streams. 

Quantum optimization has generated a profound impact in recent years. How to implement novel quantum solvers or how to introduce quantum methods in already existing classical pipelines or algorithms are currently widespread concerns in the community. In this regard, the fast advances in hardware technology <cit.> and the democratization in its access <cit.> have made research take off, especially in the optimization branch.

Regarding applications fields, transportation <cit.>, finance <cit.>, energy <cit.> or medicine <cit.> are some examples of how quantum optimization can contribute to the development of notable scientific advancements.

Even so, research cannot circumvent the state of the hardware. Current quantum computers suffer from certain limitations that directly affect their capability and performance. The current state of quantum computing is known as noisy intermediate-scale quantum (NISQ, <cit.>) era. Quantum devices available in this NISQ era are characterized by not being completely prepared to reliable deal with large problems.

This situation hinders the evaluation of quantum or hybrid methods being the researchers building their own benchmarks for each scientific proposal. In these very first steps in the quantum algorithmic designs a benchmark helps researchers to fairly assess their contributions. Iris dataset <cit.> or ImageNet <cit.> are excellent representatives of how a benchmark can be a cornerstone to gain momentum. 


Thus, this circumstance pushes researchers to generate their own testing benchmarks whenever they try to solve a particular problem using a quantum computer. This is the case even when dealing with well-known optimization problems, as can be seen in studies such as <cit.>, where authors built ad-hoc problem instances adapted to the limited capacity of quantum computers. This situation directly affects the replicability and comparison of technical approaches.

Taking this situation as main motivation, we present in this paper a quantum computing oriented benchmark for combinatorial optimization problems. This benchmark, coined as , is composed of 40 different instances equally distributed among four problems: the Traveling Salesman Problem (TSP, <cit.>), the Vehicle Routing Problem (VRP, <cit.>), the one dimensional Bin Packing Problem (BPP, <cit.>), and the Maximum Cut Problem (MCP, <cit.>). Characteristics of each dataset are described in upcoming sections.

Also, we conduct a first experimentation in order to extract a preliminary baseline of results. For conducting these tests, two commercial solvers provided by DWAVE have been employed: a pure QPU based , and the quantum-classical . For each instance of , the best solution found by both solvers after 10 independent runs is given.

Our main objective with this study is to propose a benchmark of well-known combinatorial optimization problems as the key element of a testbed in quantum optimization.



The rest of this paper is organized as follows: in Section <ref>, we introduce the problems that have been considered in , highlighting briefly the related work done in each of them in the field of quantum computing. After that, Section <ref> deeply describes . We conduct in Section <ref> a preliminary experimentation with a pure QPU and a quantum-classical solver. This paper finishes in Section <ref> with conclusions and further work.



§ DESCRIPTION OF THE PROBLEMS



As mentioned in the introduction,  contemplates instances regarding four combinatorial optimization problems. This section is devoted to briefly describe each of these problems.



 §.§ Traveling Salesman Problem



The TSP is one of the most widely studied problems in operations research and computer science. Despite being a classical optimization algorithm, the TSP is the focus of many research works even today <cit.>, since transportation problems are still in the hype, and because of the analogy between many real world problems and the TSP formulation. As a result of this interest, the TSP is frequently used as benchmarking problem for testing the quality of newly proposed techniques and solvers <cit.>; and even for tackling real-world oriented transportation problems <cit.>.

The TSP is defined as a complete graph G= (V,A), where V= {v_1,v_2,…,v_n} is the group of nodes and A= {(v_i,v_j): v_i,v_j  ∈ V,i≠ j } is the set of links among these nodes. Additionally, traveling from one node to another has an associated cost c_ij. This cost is the same regardless of the direction, i.e. c_ij = c_ji. Thus, the objective is to find a path which visits each and every node once while minimizing the total cost of the route. Also, the trip must start and finish at the same point. The TSP can be mathematically formulated as follows:

\beginmini!|l|
	𝐗f(𝐗) = ∑_i=1^n ∑_j=1
i≠j^n c_ij x_ij
	∑_j=1
i≠j^n x_ij=1,  ∀j ∈{1,…,n}
	∑_i=1
i≠j^n x_ij=1,  ∀i ∈{1,…,n}
	∑_i∈𝒮
j∈𝒮
i ≠j x_ij≥1,  ∀𝒮 ⊂𝒱,
\endmini!
where x_ij∈{0,1} takes value 1 if edge (i,j) is used in the solution. Additionally, the objective function is depicted in Formula (<ref>) as the sum of all costs associated to the edges that compose the route. Furthermore, Restrictions (<ref>) and (<ref>) represent that each node must be visited once and only once. Finally, (<ref>) assures the non-existence of sub-tours, requiring that any subset of nodes S has to be abandoned at least once.

Being such an interesting problem, the TSP has been one of the first combinatorial optimization problems to be solved by a QPU <cit.>, and many works have followed the lead exploring new solving schemes <cit.>; improving the formulation or proposing novel variants <cit.>; or making use of the TSP to solve similar, from the mathematical perspective, real-world use cases <cit.>.



Despite this interest, few advances have been made to create a TSP benchmarking, complicating the replicability and fair evaluation of the research published. 





 §.§ Vehicle Routing Problem



Like the TSP, the VRP is one of the most renowned and intensively studied problems in artificial intelligence field. In a nutshell, the VRP is an extension of the TSP, in which the objective is to find the optimal route planning for a fleet of vehicles, given the demands of a set of n client. Thus, the problem can be defined in a similar way to the TSP, as a complete G= (V, A) where V represent the set of clients and A the set of connections among them, having each edge (v_i,v_j) an associated cost c_ij (in this case, also c_ij = c_ji). Additionally, in the case of the VRP, the node v_0 represents a depot, in which all vehicles should start and end their route. The rest of nodes represent the clients to serve according to their demands q_i, which are grouped in Q = {q_1, q_2, … , q_n }.

Lastly, each VRP instance counts with a fleet of vehicles K. Each available vehicle has a limited C capacity. Depending on the VRP variant, the size of K could be limited or unlimited, and the use of a certain vehicle could imply an additional cost to the route. In any case, in the majority of the VRP formulations, the fleet is composed of an unlimited number of free-using identical vehicles.

With all this, the main objective of the canonical VRP is to find a number of routes minimizing the total cost, considering that i) each trip must start and end at v_0, ii) each client must be visited once and iii) the accumulated demand satisfied by each route does not exceed the vehicle capacity <cit.>. Mathematically, the VRP can be formulated as follows <cit.>:

\beginmini!|l|
	𝐗f(𝐗) = ∑_r=1^p ∑_i=1^n ∑_j=1
i≠j^n c_ij x_rij
	∑_r=1^n ∑_j=1, i≠j^n x_rij=1,  ∀j ∈{1,…,n}
    ∑_j=1^n x_r1j=1,  ∀r ∈{1,…,p}
    ∑_i=1 
 i≠j^n x_rij=∑_i=1^n x_rji,  ∀j ∈{1,…,n},r ∈{1,…,p}
    ∑_i=1^n ∑_j=1, i≠j^n q_j x_rij< C,  ∀r ∈{1,…,p}
    ∑_r=1^p∑_i ∈𝒮 ∑_j ∈𝒮, i≠j x_rij≤|S|-1,  ∀S ⊆{1,…,n}
\endmini!
where the binary variable x_rij is 1 if edge (i,j) is part of the route r, and p is the number of paths that compose the whole solution. Formula <ref> represents the objective function. Restriction <ref> guarantees that each customer is visited once. Constraints <ref> and <ref> assure that each vehicle leaves the deport, and that the number of vehicles arriving to each customer is equal to the amount of vehicles leaving it. Formula <ref> regards the capacity restriction, while Constraint <ref> ensures the non-existence of sub-tours.

The research conducted on the VRP in last decades has been extraordinarily prolific <cit.>, mainly because of the flexibility of the problem to be adapted to a wide variety of real-world settings. As a result of this abundant activity, a plethora of VRP variants have been proposed in the literature, considering different realistic features such as time windows <cit.>, heterogeneous vehicles <cit.>, multiple depots <cit.>, or pickup and deliveries <cit.>. In addition to that, a specific group of variants coined as Rich VRP <cit.> has emerged, which refers to these VRP variant contemplating an elevated number of constraints <cit.>.

One immediate consequence of this increasing community is the vast amount of ad-hoc benchmarks. Some of these VRP datasets have become standards for the community, and they are often used as baseline for testing the quality of newly proposed methods. Some examples are the benchmark of Solomon <cit.>, Cordeau <cit.>, Christofides and Eilon <cit.>, or Fisher <cit.>.

Turning our attention to quantum computing, some interesting research has also been conducted in this field, although practical studies are still scarce <cit.>. In <cit.>, for example, authors 
present a two-step method consisting of a clustering algorithm to estimate the number of vehicles to later solve each route as a TSP problem by the DWAVE. Further hybrid solvers can be found in <cit.> or <cit.>. Also, pure quantum solvers have also been proposed in the last years, as can be seen in <cit.>, <cit.> or <cit.>. In any case, it should be considered that, even for hybrid schemes such as the one proposed in <cit.>, most works do the experimentation on small problems, and those targeting larger instances are just centered on formulating different kind of VRP variants <cit.> in a theoretical framework.





 §.§ Bin Packing Problem



The packing of items (or packages) into a minimum number of containers (or bins) is a common task in logistics and transportation systems. In the field of operation research, this problem, known as Bin Packing Problem (BPP), has been in the spotlight for the last years. Depending on the characteristics of both items to store and bins, different variants of this problem can be formulated. Arguably, the simplest BPP formulation is the so-called one-dimensional BPP (1dBPP, <cit.>), which consists of a set of items I ∈{i_1, i_2,…,i_n} only defined by their weights w_i, and an unlimited number of bins with a maximum capacity C. 

On top of this simple formulation, more complex problems have been introduced in the literature <cit.>: such as the two-dimensional BPP (2dBPP, <cit.>) to define height and width of items and bins, and the three-dimensional BPP (3dBPP, <cit.>), in which the depth is also considered. Besides, all these BPP formulations can be extended to meet new requirements such as fragility <cit.>, time windows <cit.> or compatibilities <cit.>.

Anyway, even though BPP is still the kingpin of many industrial processes, it was not until 2022 that the first research purely focused on this kind of problems was conducted by the quantum community <cit.>. 
Besides those two papers, in <cit.> we can find a study tackling with the problem of filling spent nuclear fuel in deep-repository canisters. Authors formulate this problem as a 1dBPP, solving it using the D-Wave quantum annealer. More recently, authors in <cit.> explore the first solving algorithm for a 3dBPP through a hybrid quantum solver. 

Finally, similarly to what occurs with the aforementioned problems, no standard benchmarking for quantum solvers exists, in spite of the fact that there are public datasets such as the BPPLib <cit.>. This situation contributes to the value of , which includes 10 instances of the 1dBPP.





 §.§ Maximum Cut Problem



The Maximum Cut Problem, also known as Max-Cut, is a combinatorial optimization problem which principal objective is to divide the vertices of a graph into two disjoint subsets, in such a way that the number (or the sum of weights in a weighted graph) of crossing edges between these two subgroups is maximum. Proven to be an NP-Hard <cit.> problem, the MCP has been applied up to now to diverse fields such as network science <cit.> or clustering <cit.>.

The MCP can be formally defined as an undirected graph G= (V, A), where V is the set of nodes and A the set of edges. Also, the weight of the edge linking v_i and v_j is defined as w_i,j. Thus, a cut (S,S') is a partition of V into two subgraphs S, S' = V/S. The value of this cut is calculated as the sum of the weights w_ij of the edges that connect the two disjoint subsets S and S'. As explained before, the goal of the MCP is to maximize the value of a cut.

The MCP has been the focus of a myriad number of works along the last decades <cit.>, giving rise to a wide variety of datasets. In this context, the Stanford university published  as a standard format for creating problem instances[https://web.stanford.edu/ yyye/yyye/Gset/]. In addition, many quantum algorithms have been applied to the resolution of MCPs, like QAOA <cit.> and quantum annealers <cit.>. Due to the importance of MCP in the bibliography, it is a good practice to include it in our benchmark.



§ INTRODUCING THE GENERATED  BENCHMARKS



With all this, we introduce  in this paper, which is a benchmark comprised of 40 different instances, evenly distributed among the problems described in Section <ref>: TSP, VRP, 1dBPP and MCP.  is openly available under demand, or online at <cit.>. 

The problem sizes have been selected to comprehend both small toy samples and more complex, yet approachable, instances to be solved by a QPU. Furthermore, the biggest instances have been empirically designed according to the capacity of the hybrid methods provided by DWAVE and the practical problem size with a non-zero probability of achieving good results. In this regard, DWAVE has been considered for this study since it is the platform that accepts the largest problem sizes. 

Being more specific, it is known that current quantum annealers, such as DWAVE, can deal with larger problems in comparison with quantum gate based methods, such as QAOA <cit.>. Similarly, in the context of quantum annealers, commercial hybrid approaches can deal with even bigger problem with respect to purely quantum based alternatives <cit.>.

Thus, our goal is to create a benchmark with a number of instances able to evaluate any quantum solver in any QPU. In addition to this, the instances built should suppose a challenge for both the most restrictive and the most advanced algorithms. Now, we proceed to describe the four different datasets included in our benchmark.

Benchmarking instances for the TSP: the dataset generated for the TSP is composed of 10 different instance with sizes ranging 4 nodes to 25. For the generation of this dataset, two well-known  instances have been selected as base:  and . These original instances have been then reduced to produce 10 different use cases: , , , , , , , ,  and . To keep track of the original instance in , each instance has been named as  and , where X is the size of the problem. Regarding the format, it is  standard compliant, being readable by existent libraries, such as the [https://qiskit.org/documentation/optimization/stubs/qiskit_optimization.applications.Tsp.html]. Figure <ref> illustrates the structure of  instance.



Benchmarking instances for the VRP: 10 newly created instances of the VRP have been included in , composed of 4 to 8 nodes. All these cases are reductions of the well-known  and  instances from the Augerat CVRP benchmark <cit.>. Furthermore, in order to relax the complexity of the problem, the demands q of all clients have been set to 1, and the vehicle capacity C has been choosen to ensure that the optimum solution contains only two routes. Each instance has been named as , where X is the number of nodes and Y is the suffix to distinguish the set of instances with same X. Additionally, the VRP dataset built is [http://vrp.galgos.inf.puc-rio.br/index.php/en/] compliant. We depict in Figure <ref> an example of instance, specifically focused on . 



Benchmarking instances for the 1dBPP: in  10 cases for the 1dBPP have been incorporated. In this case, these 10 instances have been crafted by the authors of this paper, following the format described in already published studies such as <cit.> and <cit.>. They have been randomly configured while keeping set boundaries: from 3 to 14 for number of packages; {10,12,15} for bin capacities and 2 or 5 as for the values of package weights. Additionally, the number of bins available on each instance is the same as the number of packages that compose it.  

Benchmarking instances for the MCP: the dataset included in  for the MCP is composed of 10 instances with sizes ranging from 10 to 300 nodes. Each case has been coined as , being X the cardinality of graph G. All these instances have been randomly generated through a Python script which has been implemented for this specific research. This instance generation script is also openly available in the Mendeley Data repository <cit.>. It is also interesting to mention that all use cases have the standard format , which eases their automatic reading by already implemented libraries[https://qiskit.org/documentation/optimization/stubs/qiskit_optimization.applications.Maxcut.html]. Figure <ref> describes the structure of an instance with thess parameters: cardinality of G and total sum of weights (first line), edge {i,j,w} (the rest of the lines), where i is the origin node, j the destination node, and w the weight of this link.





§ PRELIMINARY EXPERIMENTATION



Despite not being the main objective of this paper, we present in this section a first complete set of results for . For this purpose, we resort to the DWAVE system, embracing two different solving approaches. On the one hand, we use the  as a quantum pure alternative. This computer has 5616 working qubits, which are distributed using a Pegasus topology. On the other hand, we employ the , which is a hybrid solver of DWAVE to deal with general, often larger, binary quadratic problems.



Having said this, Table <ref> shows the results obtained by both approaches. As mentioned, hybrid solver of leap allows addressing larger problems. Consequently, this hybrid scheme can deal with the whole , whereas the pure quantum  can only cope with a smaller proportion of the entire benchmark due to its limited capacity. For each problem instance, 10 independent runs have been executed. For each case, we depict the best results obtained as a baseline for future studies. Furthermore, Symbol  represent 'no outcome' when the instance is unprocessable for the pure quantum approach.



§ CONCLUSIONS AND FURTHER WORK



In the field of quantum optimization, the evaluation of novel resolution methods often faces the problem of the non-existence of benchmarks as standards for fair comparisons.
The community working on TSP and BPP, for example, relies on well-know libraries, such as  or the . However, these benchmarks are not suitable for current quantum devices.
This situation pushes researchers to create their own instances adapted to the quantum computers they are using. This has a significant impact on the replicability of the studies and the generation of common knowledge. 

With this motivation in mind, we have introduced  in this paper, which is a quantum computing oriented benchmark for combinatorial optimization.  includes 40 different instances, equally distributed among four well-known problems: Traveling Salesman Problem, Vehicle Routing Problem, one-dimensional Bin Packing Problem and the Maximum Cut Problem. In addition to that, we have also presented a first complete solving of  using two commercial solvers provided by DWAVE: the pure quantum , and the . The principal objective is not find the optimality of , but to provide with a baseline results, hoping that future works beat these outcomes with newly proposed algorithms.

Our team has now the sights set on two main research lines. In the short-term, we plan to increase the scope of , aggregating further instances to accommodate additional combinatorial optimization problems, such as the Job-Shop Scheduling Problem <cit.> or other problems related with economics <cit.> or energy <cit.> fields. In the medium-term, we will also propose new quantum procedures tested on , with the main goal of assessing newly proposed quantum computing based solvers.


This work was supported by the Basque Government through ELKARTEK program (BRTA-QUANTUM project, KK-2022/00041), and through HAZITEK program (Q4_Real project, ZE-2022/00033). This work was also supported by the Spanish CDTI through Plan complementario comunicación cuántica (EXP. 2022/01341)(A/20220551).



splncs


