Skip to content

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 (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:

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • 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:

  • n_car_types (int) –

    Number of car types.

  • sequence (list[int]) –

    The car sequence.

Returns:

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:

  • n_car_types (int, default: 5 ) –

    Number of car types, by default 5.

  • size (int | None, default: None ) –

    If provided, overrides n_car_types (for collection compatibility).

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns:

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:

Returns:

  • Model –

    A model ready to be solved.

interpret(solution: Solution, data: BinaryPaintShopData) -> BinaryPaintShopSolution staticmethod

Extract solution from solver result.

Parameters:

  • solution (Solution) –

    The solver solution.

  • data (BinaryPaintShopData) –

    The problem data.

Returns:

Raises:

Solution

Solution model for Binary Paint Shop use case.

BinaryPaintShopSolution

Bases: UcSolution

Solution for the Binary Paint Shop Problem (BPS) use case.

Attributes:

  • 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:

  • data (BinaryPaintShopData | None, default: None ) –

    Problem data (required for car-type icons).

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • 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:

  • min_size (int) –

    Minimum number of car types.

  • max_size (int) –

    Maximum number of car types.

  • num_instances (int, default: 1 ) –

    Number of instances per size, by default 1.

  • seed (int | None, default: None ) –

    Random seed for reproducibility, by default None.

Returns: