Binary Knapsack¶

Background¶

Given a set of items, determine how many items to put in the knapsack to maximize their summed value.

Define:¶

• $x_i$ is the number of items from each type.

• $v_i$ is the value of each item.

• $w_i$ is the weight of each item.

• $D$ is the range of $x$.

Find $x$ that maximizes the value: $\begin{aligned} \max_{x_i \in D} \Sigma_i v_i x_i\\ \end{aligned}$

and constrained by the weight: $\begin{aligned} \Sigma_i w_i x_i = C \end{aligned}$

Problem Versions¶

Binary Knapsack

Range: $D = \{0, 1\}$

Integer Knapsack

Range: $D = [0, b]$

Knapsack with binary variables and equality constraint¶

Define the optimization problem¶

In [ ]:

import numpy as np
import pyomo.environ as pyo


def define_knapsack_model(weights, values, max_weight):
    model = pyo.ConcreteModel()
    num_items = len(weights)

    model.x = pyo.Var(range(num_items), domain=pyo.Binary)

    x_variables = np.array(list(model.x.values()))

    model.weight_constraint = pyo.Constraint(expr=x_variables @ weights == max_weight)

    model.value = pyo.Objective(expr=x_variables @ values, sense=pyo.maximize)

    return model

import numpy as np import pyomo.environ as pyo def define_knapsack_model(weights, values, max_weight): model = pyo.ConcreteModel() num_items = len(weights) model.x = pyo.Var(range(num_items), domain=pyo.Binary) x_variables = np.array(list(model.x.values())) model.weight_constraint = pyo.Constraint(expr=x_variables @ weights == max_weight) model.value = pyo.Objective(expr=x_variables @ values, sense=pyo.maximize) return model

Initialize the model with parameters¶

In [ ]:

knapsack_model = define_knapsack_model(
    weights=[2, 3, 2.1, 1, 1, 2], values=[3, 5, 2, 1.5, 1.2, 2.7], max_weight=5
)

knapsack_model = define_knapsack_model( weights=[2, 3, 2.1, 1, 1, 2], values=[3, 5, 2, 1.5, 1.2, 2.7], max_weight=5 )

Setting Up the Classiq Problem Instance¶

In order to solve the Pyomo model defined above, we use the Classiq combinatorial optimization engine. For the quantum part of the QAOA algorithm (QAOAConfig) - define the number of repetitions (num_layers):

In [ ]:

from classiq import construct_combinatorial_optimization_model
from classiq.applications.combinatorial_optimization import OptimizerConfig, QAOAConfig

qaoa_config = QAOAConfig(num_layers=5)

from classiq import construct_combinatorial_optimization_model from classiq.applications.combinatorial_optimization import OptimizerConfig, QAOAConfig qaoa_config = QAOAConfig(num_layers=5)

For the classical optimization part of the QAOA algorithm we define the maximum number of classical iterations (max_iteration) and the $\alpha$-parameter (alpha_cvar) for running CVaR-QAOA, an improved variation of the QAOA algorithm [3]:

In [ ]:

optimizer_config = OptimizerConfig(max_iteration=60, alpha_cvar=0.7)

optimizer_config = OptimizerConfig(max_iteration=60, alpha_cvar=0.7)

Lastly, we load the model, based on the problem and algorithm parameters, which we can use to solve the problem:

In [ ]:

qmod = construct_combinatorial_optimization_model(
    pyo_model=knapsack_model,
    qaoa_config=qaoa_config,
    optimizer_config=optimizer_config,
)

qmod = construct_combinatorial_optimization_model( pyo_model=knapsack_model, qaoa_config=qaoa_config, optimizer_config=optimizer_config, )

We also set the quantum backend we want to execute on:

In [ ]:

from classiq import set_execution_preferences
from classiq.execution import ClassiqBackendPreferences, ExecutionPreferences

backend_preferences = ExecutionPreferences(
    backend_preferences=ClassiqBackendPreferences(backend_name="aer_simulator")
)

qmod = set_execution_preferences(qmod, backend_preferences)

from classiq import set_execution_preferences from classiq.execution import ClassiqBackendPreferences, ExecutionPreferences backend_preferences = ExecutionPreferences( backend_preferences=ClassiqBackendPreferences(backend_name="aer_simulator") ) qmod = set_execution_preferences(qmod, backend_preferences)

In [ ]:

with open("knapsack_binary.qmod", "w") as f:
    f.write(qmod)

with open("knapsack_binary.qmod", "w") as f: f.write(qmod)

Synthesizing the QAOA Circuit and Solving the Problem¶

We can now synthesize and view the QAOA circuit (ansatz) used to solve the optimization problem:

In [ ]:

from classiq import show, synthesize

qprog = synthesize(qmod)
show(qprog)

from classiq import show, synthesize qprog = synthesize(qmod) show(qprog)

We now solve the problem using the generated circuit by using the execute method:

In [ ]:

from classiq import execute

res = execute(qprog).result()

from classiq import execute res = execute(qprog).result()

We can check the convergence of the run:

In [ ]:

from classiq.execution import VQESolverResult

vqe_result = res[1].value
vqe_result.convergence_graph

from classiq.execution import VQESolverResult vqe_result = res[1].value vqe_result.convergence_graph

Optimization Results¶

We can also examine the statistics of the algorithm:

In [ ]:

import pandas as pd

optimization_result = pd.DataFrame.from_records(res[0].value)
optimization_result.sort_values(by="cost", ascending=False).head(5)

import pandas as pd optimization_result = pd.DataFrame.from_records(res[0].value) optimization_result.sort_values(by="cost", ascending=False).head(5)

And the histogram:

In [ ]:

optimization_result.hist("cost", weights=optimization_result["probability"])

optimization_result.hist("cost", weights=optimization_result["probability"])

Lastly, we can compare to the classical solution of the problem:

In [ ]:

from pyomo.opt import SolverFactory

solver = SolverFactory("couenne")
solver.solve(knapsack_model)

knapsack_model.display()

from pyomo.opt import SolverFactory solver = SolverFactory("couenne") solver.solve(knapsack_model) knapsack_model.display()