Binary Paint Shop Problem (BPS) API Reference
Data
Data model for Binary Paint Shop use case.
BinaryPaintShopData
Bases: UcData
Data for the Binary Paint Shop Problem (BPS) use case.
In the Binary Paint Shop Problem, a sequence of cars passes through a paint shop. Each car type appears exactly twice in the sequence. Each car must be painted one of two colors (0 or 1), with the constraint that each car type must have one car of each color. The goal is to minimize the number of color changes between consecutive cars.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['binary_paint_shop']
|
A constant identifier for this data type. |
n_car_types |
int
|
Number of distinct car types. |
sequence |
NDArray[int]
|
The car sequence where each car type appears exactly twice. Length is 2 * n_car_types. |
plot(*, ax: Axes | None = None) -> Axes
Plot the car sequence with distinct icons per car type.
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 data.
from_sequence(n_car_types: int, sequence: list[int]) -> BinaryPaintShopData
staticmethod
Create BinaryPaintShopData from a sequence.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
n_car_types
|
int
|
Number of car types. |
required |
sequence
|
list[int]
|
The car sequence. |
required |
Returns:
| Type | Description |
|---|---|
BinaryPaintShopData
|
The created data instance. |
generate_random(n_car_types: int = 5, size: int | None = None, seed: int | None = None) -> BinaryPaintShopData
staticmethod
Generate a random Binary Paint Shop instance.
Creates a random permutation of 2 * n_car_types items where each car type appears exactly twice.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
n_car_types
|
int
|
Number of car types, by default 5. |
5
|
size
|
int | None
|
If provided, overrides n_car_types (for collection compatibility). |
None
|
seed
|
int | None
|
Random seed for reproducibility, by default None. |
None
|
Returns:
| Type | Description |
|---|---|
BinaryPaintShopData
|
A randomly generated instance. |
Formulation
Formulation for Binary Paint Shop use case.
BinaryPaintShopFormulation
Bases: UcFormulation[BinaryPaintShopData, BinaryPaintShopSolution]
Constraint-based formulation for the Binary Paint Shop Problem.
Mathematical Formulation
Decision Variables: c_t in {0,1}: color of the first appearance of car type t (second appearance gets the opposite color 1 - c_t) d_p in {0,1}: color change indicator between positions p and p+1
Objective: minimize sum_p d_p
Constraints: For each consecutive pair (p, p+1): d_p >= color_at_p - color_at_{p+1} d_p >= color_at_{p+1} - color_at_p where color_at_p = c_{type_p} if first appearance, color_at_p = 1 - c_{type_p} if second appearance
to_string(data: BinaryPaintShopData) -> str
staticmethod
Return a string describing the formulation.
formulate(data: BinaryPaintShopData) -> Model
staticmethod
Formulate the Binary Paint Shop as an optimization model.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
BinaryPaintShopData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
Model
|
A model ready to be solved. |
interpret(solution: Solution, data: BinaryPaintShopData) -> BinaryPaintShopSolution
staticmethod
Extract solution from solver result.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
solution
|
Solution
|
The solver solution. |
required |
data
|
BinaryPaintShopData
|
The problem data. |
required |
Returns:
| Type | Description |
|---|---|
BinaryPaintShopSolution
|
Structured solution with metrics. |
Raises:
| Type | Description |
|---|---|
NoSolutionFoundError
|
If the solver did not find a solution. |
Solution
Solution model for Binary Paint Shop use case.
BinaryPaintShopSolution
Bases: UcSolution
Solution for the Binary Paint Shop Problem (BPS) use case.
Attributes:
| Name | Type | Description |
|---|---|---|
name |
Literal['binary_paint_shop']
|
Identifier for this solution type. |
color_assignment |
NDArray[int]
|
Color (0 or 1) assigned to each position in the sequence. |
n_color_changes |
int
|
Number of color changes between consecutive positions. |
is_valid |
bool
|
Whether each car type has one car of each color. |
plot(data: BinaryPaintShopData | None = None, *, ax: Axes | None = None) -> Axes
Plot the color assignment with car icons.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
data
|
BinaryPaintShopData | None
|
Problem data (required for car-type icons). |
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 BinaryPaintShop use case.
BinaryPaintShopInstance
Bases: UcInstance[BinaryPaintShopData, BinaryPaintShopFormulation, BinaryPaintShopSolution]
Instance combining data and formulation for BinaryPaintShop.
Collection
Collection of Binary Paint Shop instances.
BinaryPaintShopCollection
Bases: UcInstanceCollection[BinaryPaintShopInstance]
Collection of Binary Paint Shop instances.
from_random(min_size: int, max_size: int, num_instances: int = 1, *, seed: int | None = None) -> BinaryPaintShopCollection
classmethod
Generate random Binary Paint Shop instances.
Parameters:
| Name | Type | Description | Default |
|---|---|---|---|
min_size
|
int
|
Minimum number of car types. |
required |
max_size
|
int
|
Maximum number of car types. |
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 |
|---|---|
BinaryPaintShopCollection
|
Collection containing generated instances. |