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
get_operator(values, weights, max_weight)
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
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
get_solution(x, values)
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
knapsack_value_weight(solution, values, weights)
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