entropicalabs / openqaoa

Multi-backend SDK for quantum optimisation
MIT License
113 stars 59 forks source link

UF: Adding matrix and distance inputs for the VRP #238

Closed alejomonbar closed 1 year ago

alejomonbar commented 1 year ago

Description

One user suggested the inclusion of the matrix distance input for the vehicle routing problem. I added two new ways of encoding the vehicle routing problem. The first, the distance matrix

from openqaoa.problems import VRP
from openqaoa import QAOA
# With this method we cannot generate a visualization of the solutions because there are not coordinates
matrix = [[0, 0.5, 0.3, 0.2, 1], [0, 0, 0.1, 0.8, 3], [0, 0, 0, 0.7, 2.1], [0, 0, 0, 0, 0.2], [0, 0, 0, 0, 0]]  # 5 cities problem with position (i, j) the distance between nodes i and j 
n_vehicles = 1
vrp = VRP.from_distance_matrix(matrix=matrix, n_vehicles=1)
qubo =  vrp.qubo

qaoa = QAOA()
qaoa.compile(qubo)
qaoa.optimize()
results = qaoa.result.lowest_cost_bitstrings(10)

and the second option is to add the (x, y) coordinates of each node

from openqaoa.problems import VRP
from openqaoa import QAOA

pos = [[0,1], [8,3], [4,2], [2,9], [-3, 1]] # coordinates of each node
n_vehicles = 1
vrp = VRP.from_coordinates(pos=pos, n_vehicles=1)
qubo =  vrp.qubo

qaoa = QAOA()
qaoa.compile(qubo)
qaoa.optimize()
results = qaoa.result.lowest_cost_bitstrings(10)

Checklist

Type of change

Please delete options that are not relevant.

How Has This Been Tested?

In the problem tests there are two functions to test it

shahidee44 commented 1 year ago

@alejomonbar We've had to update the requirements for openqaoa-qiskit. You will need to update this branch with the current version of dev so that the tests can pass.