Knapsack Optimizer
Quantum version of the Knapsack algorithm for truck load optimization.
Description
Description
An optimization algorithm by QCentroid
The Knapsack problem is a classic optimization problem. The problem is, essentially, the following:
We have a series of objects with two quantities associated to each, namely weight and value. We also have a knapsack that can carry up to a limited total weight. The problem is then to pick a subset of the objects to maximize the value in the knapsack without exceeding the total weight.
This problem is known to be NP-Complete, that is, it is really hard to find the optimal solution to it. If we have a graph with N nodes, the amount of possible solution grows exponentially. Comparing one solution to another one is easy, but finding the best one is similar to looking for a needle in a haystack.
In this example, we create a set of objects with weights and values to define the problem. Both series of values are introduced into the QCentroid API, who looks for the optimal solution in an easy way. The solution is showed afterwards.
Take into account that the hardest piece of this problem is finding the optimal solution. This step is completely addressed by the QCentroid, while the users / cabin boys and girls do not have to worry about it.
Brand
Brand
QCentroid

Additional information
Additional information
Sustainability focus | |
---|---|
Sector | |
Use case | |
UN SDG supported |
How To
How To
Here you can see an Jupyter Notebook example. This 5 nodes graph have an easy solution to check. You can see that this one is optimal.
from Qapitan import Qapitan
import time
from IPython.display import display, clear_output
Now it is time to define the problem. In particular, the algorithm and provider must be specified. We are in the advent of quantum computing, and thus we will use simulations by now. We use an annealing scheme simulated using the DWave technology.
# Define the problem
limit_weight = 6
weights = [1,5,4,2]
values = [3,4,2,6]
# algorithm = "Solver_Qapitan_QUBO_Framework-Knapsack-annealing_sim-dwave-local"
algorithm = "Solver_Qapitan_QUBO_Framework-Knapsack-geneticalgorithm-classic-local"
provider = "local"
PAYLOAD_KNAPSACK_1 = {
"problem": "maxcut_problem",
"data": {
"limit_weight": limit_weight,
"weights": weights,
"values": values
},
"algorithm": algorithm,
"provider": provider,
"arguments": {
}
}
QAPITAN_PUBLIC_API= "https://api.qcentroid.xyz/"
PAYLOAD_USER = {'username': '...', 'password': '...'}
qapitan_api = Qapitan(QAPITAN_PUBLIC_API, PAYLOAD_USER)
header = qapitan_api.login()
print(header)
{'username': 'your-username', 'password': 'your-password'} {'Authorization': 'Bearer eyJ0eXAiOiJKV1QiLCJhbGciOiJIUzIv ... MjA5gv7md1K990'}
response_json = qapitan_api.execute(header=header, problem='knapsack', payload=PAYLOAD_KNAPSACK_1)
print(response_json)
{'detail': 'Authorized. Processing file', 'job': 'XNLSQH2LEHLK'}
job_name = response_json['job']
result = qapitan_api.get_result(header=header, job_name=job_name)
while(job_name not in result['job'] or (result['job'][job_name]['status'] != 'FINISHED' and result['job'][job_name]['status'] != 'ERROR')):
if(job_name in result['job']):
display(result['job'][job_name]['status'])
else:
display('LOADING')
time.sleep(3)
clear_output(wait=True)
result = qapitan_api.get_result(header=header, job_name=job_name)
clear_output(wait=True)
# Print result
print("Execution Result:")
print(result['job'][job_name])
{'status': 'FINISHED', 'started_at': '02/11/2022, 08:05:02', 'end_at': '02/11/2022, 08:06:32', 'executions': {'Solver_Qapitan_QUBO_Framework-Knapsack-annealing_sim-dwave-local': {'started_at': '', 'end_at': '02/11/2022, 08:06:21', 'status': 'SUCCESS', 'data': {'limit_weight': 6, 'weights': [1, 5, 4, 2], 'values': [3, 4, 2, 6]}, 'arguments': '', 'result': [[0, 2], [5, -0.3333333333333333]]}}}
order = qapitan_api.get_best_result(header, response_json['job'])[0]
order = [int(o) for o in order]
print(order)
[0, 2]