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

QCentroid

Additional information

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

# 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)