Quadratic Knapsack Example

Download Notebook

The Quadratic Knapsack Problem (QKP) extends the classical knapsack by assigning values to pairs of items rather than individuals. It maximizes total pairwise interaction value while respecting a budget constraint.

import getpass
import os

import numpy as np
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.quadratic_knapsack import (
    QuadraticKnapsackCollection,
    QuadraticKnapsackData,
    QuadraticKnapsackFormulation,
    QuadraticKnapsackInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define 4 items with pairwise interaction values, individual costs, and a budget of 8.

interaction_matrix = np.array(
    [
        [8, 2, 5, 0],
        [2, 6, 0, 3],
        [5, 0, 7, 1],
        [0, 3, 1, 4],
    ]
)
costs = [3.0, 4.0, 2.0, 5.0]
budget = 8.0
data = QuadraticKnapsackData.from_matrix(interaction_matrix=interaction_matrix, costs=costs, budget=budget)
print(data.to_string())

Quadratic Knapsack Data:
  Number of items: 4
  Budget: 8.0
  Costs: [3. 4. 2. 5.]
  Interaction matrix shape: (4, 4)

Plot Data

Visualize item interactions and costs.

data.plot()

(<Axes: title={'center': 'Interaction Matrix'}, xlabel='Item', ylabel='Item'>,
 <Axes: title={'center': 'Item Costs & Budget Constraint'}, xlabel='Item', ylabel='Cost'>)

Create Formulation

Maximize quadratic profit from selected items within the budget constraint.

formulation = QuadraticKnapsackFormulation()
print(formulation.to_string(data))

Quadratic Knapsack Formulation:
  Items: 4
  Budget: 8.0

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 3
  x[i] = 1 if item i is selected
  Total: 4 binary variables

Objective:
  maximize sum_{i,j} interaction[i,j] * x[i] * x[j]

Constraints:
  1. Budget constraint (1 constraint):
     sum_i costs[i] * x[i] <= 8.0

Create Instance

Combine data and formulation into a solvable instance.

instance = QuadraticKnapsackInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Quadratic Knapsack Data:
  Number of items: 4
  Budget: 8.0
  Costs: [3. 4. 2. 5.]
  Interaction matrix shape: (4, 4)
Formulation:Quadratic Knapsack Formulation:
  Items: 4
  Budget: 8.0

Decision Variables:
  x[i] in {0,1} for i = 0, ..., 3
  x[i] = 1 if item i is selected
  Total: 4 binary variables

Objective:
  maximize sum_{i,j} interaction[i,j] * x[i] * x[j]

Constraints:
  1. Budget constraint (1 constraint):
     sum_i costs[i] * x[i] <= 8.0

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

Quadratic Knapsack Solution:
  Selected items: [0 2]
  Total value: 25.0
  Total cost: 5.0
  Valid: True

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

<Axes: title={'center': 'QKP Solution — Value: 25.0, Cost: 5.0'}, xlabel='Item', ylabel='Cost'>

Collections

Generate a benchmark collection of random instances for batch processing.

collection = QuadraticKnapsackCollection.from_random(
    min_size=4,
    max_size=6,
    seed=42,
)
model = collection.instances[0].formulate()
print(model)

Model: quadratic_knapsack<quadratic_knapsack>
Maximize
  3 * x_0 * x_1 + 11 * x_0 * x_2 + 13 * x_0 * x_3 + 8 * x_1 * x_2
  + 8 * x_1 * x_3 + 7 * x_2 * x_3
Subject To
  budget_constraint: 5 * x_0 + 7 * x_1 + 5 * x_2 + 10 * x_3 <= 16.2
Binary
  x_0 x_1 x_2 x_3