Quadratic Knapsack Problem (QKP) API Reference
Data
Data model for Quadratic Knapsack use case.
QuadraticKnapsackData
Bases: UcData
Data for the Quadratic Knapsack Problem (QKP) use case.
The Quadratic Knapsack Problem extends the classical knapsack by assigning values to pairs of items rather than individual items. The objective is to select a subset of items maximizing the total pairwise interaction value while staying within a budget constraint.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['quadratic_knapsack']
|
A constant identifier for this data type. |
interaction_matrix |
NumPyArray
|
Symmetric n x n matrix where element [i, j] represents the value obtained when both items i and j are selected. |
costs |
NumPyArray
|
Cost of selecting each item. |
budget |
float
|
Maximum total cost allowed. |
plot(*, ax: Axes | None = None) -> Axes | tuple[Axes, Axes]
Plot the interaction matrix as a heatmap and item costs with budget.
When ax is None a figure with two subplots is created: the left
panel shows the interaction-value heatmap and the right panel shows
per-item costs as a bar chart with a dashed line for the budget
constraint. When an existing ax is provided, only the heatmap is
drawn on that axes.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
Axes | tuple[Axes, Axes]
|
A single axes when ax is provided, or a |
to_string() -> str
Return a string describing the data.
from_matrix(interaction_matrix: list[list[float]] | NDArray[np.float32], costs: list[float] | NDArray[np.float32], budget: float) -> QuadraticKnapsackData
staticmethod
Create QuadraticKnapsackData from an interaction matrix.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
interaction_matrix
|
list[list[float]] | NDArray
|
Symmetric n x n interaction matrix. |
required |
costs
|
list[float] | NDArray
|
Cost per item. |
required |
budget
|
float
|
Maximum total cost. |
required |
Returns:
| Type | Description |
|---|---|
QuadraticKnapsackData
|
The created data instance. |
generate_random(n_items: int = 5, max_interaction: int = 10, max_cost: int = 10, size: int | None = None, seed: int | None = None) -> QuadraticKnapsackData
staticmethod
Generate a random Quadratic Knapsack instance.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
n_items
|
int
|
Number of items, by default 5. |
5
|
max_interaction
|
int
|
Maximum interaction value, by default 10. |
10
|
max_cost
|
int
|
Maximum cost per item, by default 10. |
10
|
size
|
int | None
|
If provided, overrides n_items (for collection compatibility). |
None
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
QuadraticKnapsackData
|
A randomly generated instance. |
Formulation
Formulation for Quadratic Knapsack use case.
QuadraticKnapsackFormulation
Bases: UcFormulation[QuadraticKnapsackData, QuadraticKnapsackSolution]
Constraint-based formulation for the Quadratic Knapsack Problem.
Mathematical Formulation
Decision Variables: x_i in {0,1}: 1 if item i is selected, 0 otherwise
Objective: maximize sum_{i,j} interaction[i][j] * x_i * x_j
Constraints: sum_i costs[i] * x_i <= budget
to_string(data: QuadraticKnapsackData) -> str
staticmethod
Return a string describing the formulation.
formulate(data: QuadraticKnapsackData) -> Model
staticmethod
Formulate the Quadratic Knapsack as an optimization model.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
QuadraticKnapsackData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
Model
|
A model ready to be solved. |
interpret(solution: Solution, data: QuadraticKnapsackData) -> QuadraticKnapsackSolution
staticmethod
Extract solution from solver result.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
solution
|
Solution
|
The solver solution. |
required |
data
|
QuadraticKnapsackData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
QuadraticKnapsackSolution
|
Structured solution with metrics. |
Raises:
| Type | Description |
|---|---|
NoSolutionFoundError
|
If the solver did not find a solution. |
Solution
Solution model for Quadratic Knapsack use case.
QuadraticKnapsackSolution
Bases: UcSolution
Solution for the Quadratic Knapsack Problem (QKP) use case.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['quadratic_knapsack']
|
Identifier for this solution type. |
selected_items |
list[int]
|
Indices of the selected items. |
total_value |
float
|
Total interaction value of the selected items. |
total_cost |
float
|
Total cost of the selected items. |
is_valid |
bool
|
Whether the solution satisfies the budget constraint (total_cost <= budget). |
plot(data: QuadraticKnapsackData | None = None, *, ax: Axes | None = None) -> Axes
Plot the selected items.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
QuadraticKnapsackData | None
|
Problem data for additional context. |
None
|
ax
|
Axes | None
|
Matplotlib axes to draw on. Creates a new figure if |
None
|
Returns:
| Type | Description |
|---|---|
Axes
|
The axes with the plot. |
to_string() -> str
Return a string describing the solution.
Instance
Instance model for QuadraticKnapsack use case.
QuadraticKnapsackInstance
Bases: UcInstance[QuadraticKnapsackData, QuadraticKnapsackFormulation, QuadraticKnapsackSolution]
Instance combining data and formulation for QuadraticKnapsack.
Collection
Collection of Quadratic Knapsack instances.
QuadraticKnapsackCollection
Bases: UcInstanceCollection[QuadraticKnapsackInstance]
Collection of Quadratic Knapsack instances.
from_random(min_size: int, max_size: int, num_instances: int = 1, *, seed: int | None = None) -> QuadraticKnapsackCollection
classmethod
Generate random Quadratic Knapsack instances.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
min_size
|
int
|
Minimum number of items. |
required |
max_size
|
int
|
Maximum number of items. |
required |
num_instances
|
int
|
Number of instances per size, by default 1. |
1
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
QuadraticKnapsackCollection
|
Collection containing generated instances. |