Bin Packing Problem (BPP) API Reference
Data
Data model for Bpp use case.
BppData
Bases: UcData
Data for the Bin Packing Problem (BPP) use case.
This class encapsulates all necessary information to define and solve a BPP instance. The BPP is a classic optimization problem where the goal is to pack all items into the minimum number of bins while respecting capacity constraints.
The Bin Packing Problem is NP-hard and highly relevant for logistics, resource allocation, and various industrial applications such as container loading, memory allocation, and cutting stock problems.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['bin_packing_problem']
|
A constant identifier for this data type, always set to "bin_packing_problem". Used for registration and type identification in the use case registry. |
item_weights |
NumPyArray
|
A 1D NumPy array containing the weight of each item to be packed. The length of this array determines the number of items. Example: np.array([4.5, 2.3, 6.1, 3.8]) |
bin_capacity |
float
|
The maximum capacity of each bin. All bins have the same capacity. Example: 10.0 |
item_names |
(list[str | int] | None, optional)
|
Optional list of item identifiers (strings or integers) for better readability and tracking. If None, items will be identified by their index. Example: ["item_A", "item_B", "item_C"] or [0, 1, 2] |
Examples:
Create a simple 4-item BPP instance:
>>> bpp = BppData(
... name="bin_packing_problem",
... item_weights=np.array([4.5, 2.3, 6.1, 3.8]),
... bin_capacity=10.0,
... item_names=["A", "B", "C", "D"],
... )
plot(*, ax: Axes | None = None) -> Axes
Plot item weights as a horizontal bar chart.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
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 BPP data.
from_weights(item_weights: np.ndarray, bin_capacity: float, item_names: list[str | int] | None = None) -> BppData
staticmethod
Create BppData from item weights and bin capacity.
generate_random(n_items: int, bin_capacity: float, weight_max: float | None = None, *, seed: int | None = None) -> BppData
staticmethod
Generate a random BPP instance.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
n_items
|
int
|
Number of items. |
required |
bin_capacity
|
float
|
Capacity of each bin. |
required |
weight_max
|
float | None
|
Maximum item weight. Defaults to |
None
|
seed
|
int | None
|
Random seed. |
None
|
Returns:
| Type | Description |
|---|---|
BppData
|
Randomly generated instance. |
Formulation
Formulation for Bpp use case.
BppFormulation
Bases: UcFormulation[BppData, BppSolution]
Constraint-based formulation for the Bin Packing Problem (BPP).
This class provides the mathematical formulation to solve BPP using optimization. The formulation uses binary variables to represent item-to-bin assignments and minimizes the number of bins used.
Mathematical Formulation
Decision Variables:
x_ij ∈ {0,1}: 1 if item i is packed in bin j, 0 otherwise
y_j ∈ {0,1}: 1 if bin j is used, 0 otherwise
Objective:
minimize Σ_j y_j (minimize the number of bins used)
Constraints:
1. Each item in exactly one bin: Σ_j x_ij = 1 ∀i
2. Capacity constraint: Σ_i (weight_i * x_ij) ≤ capacity * y_j ∀j
3. Bin usage linking: y_j ≥ x_ij ∀i,j
to_string(data: BppData) -> str
staticmethod
Return a string describing the formulation.
formulate(data: BppData) -> Model
staticmethod
Formulate the Bin Packing Problem as a constraint-based model.
Creates a formulation for the Bin Packing Problem where we minimize the number of bins used while ensuring all items are packed and capacity constraints are satisfied.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
BppData
|
The BPP instance data containing item weights and bin capacity. |
required |
Returns:
| Type | Description |
|---|---|
Model
|
An optimization model ready to be solved. |
interpret(solution: Solution, data: BppData) -> BppSolution
staticmethod
Interpret the solution.
Extracts the bin assignments from the solution and computes solution metrics like number of bins used, bin loads, and validity.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
solution
|
Solution
|
The solution containing variable assignments. |
required |
data
|
BppData
|
The original BPP instance data. |
required |
Returns:
| Type | Description |
|---|---|
BppSolution
|
A structured solution object with bin assignments and metrics. |
Solution
Solution model for Bpp use case.
BppSolution
Bases: UcSolution
Solution for the Bin Packing Problem (BPP) use case.
This class represents a solution to a BPP instance, containing the assignment of items to bins and metrics about the solution quality.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['bin_packing_problem']
|
A constant identifier for this solution type, always set to "bin_packing_problem". |
bin_assignments |
list[list[str | int]]
|
A list of bins, where each bin is represented as a list of item identifiers (names or indices) that are packed into that bin. Example: [["item_A", "item_B"], ["item_C"], ["item_D", "item_E"]] represents 3 bins with different items. |
num_bins_used |
int
|
The total number of bins used in this solution. This is also the objective value that we want to minimize. |
bin_loads |
list[float]
|
The total weight in each bin. Useful for verifying that capacity constraints are satisfied. Example: [6.8, 6.1, 8.3] for the bin assignments above. |
is_valid |
bool
|
Whether the solution satisfies all constraints: - All items are assigned to exactly one bin - No bin exceeds its capacity - All bins have at least one item (no empty bins) |
Examples:
A valid solution for 5 items packed into 3 bins:
>>> solution = BppSolution(
... name="bin_packing_problem",
... bin_assignments=[["A", "B"], ["C"], ["D", "E"]],
... num_bins_used=3,
... bin_loads=[6.8, 6.1, 8.3],
... is_valid=True,
... )
plot(data: BppData | None = None, *, ax: Axes | None = None) -> Axes
Plot the bin packing solution as a stacked horizontal bar chart.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
BppData | None
|
Problem data. When provided, bar widths reflect item weights and a capacity line is drawn. |
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 Bpp use case.
BppInstance
Bases: UcInstance[BppData, BppFormulation, BppSolution]
Instance combining data and formulation for Bpp.
Collection
Collection of Bpp instances.
BppCollection
Bases: UcInstanceCollection[BppInstance]
Collection of Bpp instances.
from_random(min_num_items: int | None = None, max_num_items: int | None = None, bin_capacity: float = 10.0, num_instances: int = 1, *, sizes: Sequence[int] | None = None, seed: int | None = None) -> BppCollection
classmethod
Generate random bin packing instances.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
min_num_items
|
int | None
|
Minimum number of items. |
None
|
max_num_items
|
int | None
|
Maximum number of items. |
None
|
bin_capacity
|
float
|
Bin capacity for all instances. |
10.0
|
num_instances
|
int
|
Instances per size. |
1
|
seed
|
int | None
|
Random seed. |
None
|
sizes
|
Sequence[int] | None
|
Explicit sizes to generate, e.g. |
None
|
Returns:
| Type | Description |
|---|---|
BppCollection
|
Collection of generated instances. |
filter_infeasible(max_runtime: float = 3600, *, quiet: bool = True) -> list[bool]
Drop the instances of this collection that have no feasible solution.
Every instance is formulated and handed to SCIP, which stops as soon as
it finds the first feasible solution. An instance is removed from the
collection when SCIP proves the model infeasible, when no solution turns
up within max_runtime, or when formulating it fails altogether. This
keeps randomly generated instances from breaking a downstream pipeline.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
max_runtime
|
float
|
SCIP time limit per instance in seconds. Must be positive. Defaults to 3600 seconds. |
3600
|
quiet
|
bool
|
Suppress the SCIP solver output. |
True
|
Returns:
| Type | Description |
|---|---|
list[bool]
|
Feasibility mask over the instances as they were before filtering,
in that order: |
Raises:
| Type | Description |
|---|---|
ValueError
|
If |