qiskit.optimization.applications.ising.knapsack¶

Convert knapsack parameters instances into Pauli list The parameters are a list of values a list of weights and a maximum weight of the knapsack.

In the Knapsack Problem we are given a list of objects that each has a weight and a value. We are also given a maximum weight we can carry. We need to pick a subset of the objects so as to maximize the total value without going over the maximum weight.

If we have the weights w[i], the values v[i] and the maximum weight W_max. We express the solution as a binary array x[i] where we have a 1 for the items we take in the solution set. We need to maximize sum(x[i]*v[i]) while respecting W_max >= sum(x[i]*w[i])

Functions

 `get_operator`(values, weights, max_weight) Generate Hamiltonian for the knapsack problem. `get_solution`(x, values) Get the solution to the knapsack problem from the bitstring that represents to the ground state of the Hamiltonian `knapsack_value_weight`(solution, values, weights) Get the total wight and value of the items taken in the knapsack.
get_operator(values, weights, max_weight)[source]

Generate Hamiltonian for the knapsack problem.

Notes

To build the cost function for the Hamiltonian we add a term S that will vary with our solution. In order to make it change wit the solution we enhance X with a number of additional bits X’ = [x_0,..x_{n-1},y_{n}..y_{n+m-1}]. The bytes y[i] will be the binary representation of S. In this way the optimizer will be able to optimize S as well as X.

The cost function is \$\$C(X’) = M(W_{max} - sum_{i=0}^{n-1} x_{i}w_{i} - S)^2 - sum_{i}^{n-1} x_{i}v_{i}\$\$ where S = sum(2**j * y[j]), j goes from n to n+log(W_max). M is a number large enough to dominate the sum of values.

Because S can only be positive, when W_max >= sum(x[i]*w[i]) the optimizer can find an S (or better the y[j] that compose S) so that it will take the first term to 0. This way the function is dominated by the sum of values. If W_max < sum(x[i]*w[i]) then the first term can never be 0 and, multiplied by a large M, will always dominate the function.

The minimum value of the function will be that where the constraint is respected and the sum of values is maximized.

Parameters
• values (list of non-negative integers) – a list of values

• weights (list of non-negative integers) – a list of weights

• max_weight (non negative integer) – the maximum weight the knapsack can carry

Returns

operator for the Hamiltonian float: a constant shift for the obj function.

Return type

WeightedPauliOperator

Raises
• ValueError – values and weights have different lengths

• ValueError – A value or a weight is negative

• ValueError – All values are zero

• ValueError – max_weight is negative

get_solution(x, values)[source]

Get the solution to the knapsack problem from the bitstring that represents to the ground state of the Hamiltonian

Parameters
• x (numpy.ndarray) – the ground state of the Hamiltonian.

• values (numpy.ndarray) – the list of values

Returns

a bit string that has a ‘1’ at the indexes

corresponding to values that have been taken in the knapsack. i.e. if the solution has a ‘1’ at index i then the value values[i] has been taken in the knapsack

Return type

numpy.ndarray

knapsack_value_weight(solution, values, weights)[source]

Get the total wight and value of the items taken in the knapsack.

Parameters
• solution (numpy.ndarray) – binary string that represents the solution to the problem.

• values (numpy.ndarray) – the list of values

• weights (numpy.ndarray) – the list of weights

Returns

the total value and weight of the items in the knapsack

Return type

tuple