dwave-examples/knapsack

Implementation of knapsack problem, set up for scaling to large problem size

knapsack's Issues

Update to use Ocean SDK 2.0

Improve code explanation

The readme can be improved with:

• explanation on Lucas' equations
• images of Lucas' equations
• obey column 80

The idea is to get this demo's explanation to work better as a standalone (rather than needing a user to go and read a paper)

Use the proper function for the knapsack inequality constraint

currently, the way the inequality constraint is built is very involved. The code can be simplified significantly by using .add_linear_inequality_constraint.

If the goal is to teach users how to work with slack variables, using a higher-level function is not needed. However, more users can expand this example to an application, if it's simplified.

Correct README

According to this paper, https://arxiv.org/pdf/1302.5843.pdf, a constraint is used to make sure only one value of y equals one.

\sum_i y_i = 1

However, in the code, another implementation is used in which a logarithmic number of binary variables are used to create values between 1-N. Any combination is feasible.

Add cqm tag to the knapsack example

Add cqm tag to the knapsack example so it is retrieved in a search in Leap collection of examples

Test failures: ExactSolver doesn't expect 'label' argument

A couple of the examples use the ExactSolver in tests (it's passed in as the sampler). The ExactSolver does not take in any keyword arguments, so passing in 'label' causes the test to fail with TypeError: sample() got an unexpected keyword argument 'label'.

I'm wondering if we should update the ExactSolver to just swallow keyword arguments. Or if this is considered bad practice, in which case we just need to modify a few examples including this one.

Improve readme

Reformat the ReadMe so it's consistent with the other code examples (add Problem Formulation section)

Fix tests

See failed tests. The problems seems to be with the hardcoded solver name. /cc @joelgdwave

Implementation of inequality

knapsack/main.py

Line 44 in 8064923

max_y_index = ceil(log(weight_capacity))

Should this be log2?

Issue with default behaviour on Knapsack example

Opening a new Knapsack example and hitting the green play button gives results that do not satisfy the maximum weight constraint out of the box.