knapsack2qubo

Convert knapsack problem to QUBO (Quadratic Unconstrained Binary Optimization)

Since R2025b

Installation Required: This functionality requires MATLAB Support Package for Quantum Computing.

Syntax

qprob = knapsack2qubo(v,w,M)

qprob = knapsack2qubo(v,w,M,Penalty=val)

Description

qprob = knapsack2qubo(v,w,M) converts a knapsack problem given by a vector of item values, a vector of item weights, and a maximum weight to an equivalent QUBO formulation as a qubo object.

qprob = knapsack2qubo(v,w,M,Penalty=val) also specifies a scalar penalty factor to penalize the constraints in the equivalent QUBO formulation.

Examples

Convert Knapsack Problem to QUBO

Define a knapsack problem by creating two 1-by-5 vectors that represent the values and weights of five items. Create a numeric scalar that represents the maximum weight capacity of the knapsack.

v = [5 2 8 4 3];
w = [9 8 4 5 2];
M = 17;

Convert the knapsack problem to a QUBO problem.

qprob = knapsack2qubo(v,w,M)

qprob = 
  qubo with properties:

    QuadraticTerm: [10×10 double]
       LinearTerm: [10×1 double]
     ConstantTerm: 289
     NumVariables: 10

Solve the QUBO problem.

result = solve(qprob)

result = 
  quboResult with properties:

                BestX: [10×1 double]
    BestFunctionValue: -16
      AlgorithmResult: [1×1 tabuSearchResult]

Convert the result of the QUBO problem to the knapsack formulation. The solution to the knapsack problem is to include the first, third, and fifth items in the list. These items have a total value of 16 and a total weight of 15, which is less than the specified maximum weight of 17.

[items,totalValue,totalWeight] = quboResult2knapsack(result,v,w,M)

items = 3×1

     1
     3
     5

totalValue = 
16

totalWeight = 
15

Penalize Constraints in Knapsack QUBO Problem

Define a knapsack problem by creating two 1-by-4 vectors that represent the values and weights of four items. Create a numeric scalar that represents the maximum weight capacity of the knapsack.

v = [50 40 80 10];
w = [3 4 6 2];
M = 10;

Convert the knapsack problem to a QUBO problem and solve it.

qprob = knapsack2qubo(v,w,M);
result = solve(qprob)

result = 
  quboResult with properties:

                BestX: [8×1 double]
    BestFunctionValue: -161
      AlgorithmResult: [1×1 tabuSearchResult]

Convert the result of the QUBO problem to the knapsack formulation.

[items,totalValue,totalWeight] = quboResult2knapsack(result,v,w,M)

items = 3×1

     1
     2
     3

totalValue = 
170

totalWeight = 
13

The total weight of the solution found by solving the QUBO problem, 13, exceeds the maximum weight specified, 10. Convert the knapsack problem to a QUBO problem again, specifying Penalty as 10, and solve the QUBO problem. Convert the result of the constrained QUBO problem to the knapsack formulation. Increasing the penalty factor encourages the QUBO algorithm to prioritize meeting the maximum weight constraint.

qprobP = knapsack2qubo(v,w,M,Penalty=10);
resultP = solve(qprobP);
[itemsP,totalValueP,totalWeightP] = quboResult2knapsack(resultP,v,w,M)

itemsP = 
1

totalValueP = 
50

totalWeightP = 
3

Input Arguments

v — Item values

numeric vector

Item values, specified as a numeric vector. Each element of v corresponds to the value of an item that can be placed in the knapsack. For example, the first item of those that can be placed in the knapsack has value v(1).

Data Types: double

w — Item weights

numeric vector

Item weights, specified as a numeric vector. Each element of w corresponds to the weight of an item that can be placed in the knapsack. For example, the first item of those that can be placed in the knapsack has weight w(1).

Data Types: double

M — Maximum weight capacity of knapsack

numeric scalar

Maximum weight capacity of the knapsack, specified as a numeric scalar.

Data Types: double

val — Penalty factor

1 (default) | numeric scalar

Penalty factor, specified as a numeric scalar. The penalty factor dictates the importance of the maximum weight constraint. As the value of the penalty factor increases, the knapsack2qubo function prioritizes finding a solution whose total weight is less than the maximum weight constraint M over finding a maximum-value solution.

If the maximum weight constraint is not satisfied in the knapsack solution obtained using quboResult2knapsack, try increasing the penalty factor.

Data Types: double

Output Arguments

qprob — QUBO formulation

qubo object

QUBO formulation, returned as a qubo object.

More About

Knapsack Problem

The classic knapsack problem involves a knapsack with a maximum weight capacity that a person must fill with items of varying value and weight. The problem is to maximize the value of the items in the knapsack without exceeding the maximum weight capacity. Each item can be selected only once.

References

[1] Lucas, Andrew. "Ising formulation of many NP problems." Frontiers in Physics 2 (February 2014). https://doi.org/10.3389/fphy.2014.00005.

Version History

Introduced in R2025b