discrete_optimization.binpack.transformations package

Submodules

discrete_optimization.binpack.transformations.to_facility module

Transformation from BinPack to Facility Location.

class discrete_optimization.binpack.transformations.to_facility.BinpackToFacilityTransformation(setup_cost_per_bin: float = 1.0)

Bases: ProblemTransformation[BinPackProblem, BinPackSolution, FacilityProblem, FacilitySolution]

Transform BinPack problem to Facility Location problem.

Mapping: - Items (with weights) → Customers (with demands) - Bins (with capacity) → Facilities (with capacity) - Opening a bin → Setup cost for facility (cost = 1) - Minimize bins → Minimize setup costs - No spatial component (all locations at origin) - No assignment costs (distance-based cost = 0)

This transformation is ASYMMETRIC: - Forward (problem): LOSSY - incompatibility constraints lost - Backward (solution): EXACT - facility assignments map to bins

back_transform_solution(solution: FacilitySolution, source_problem: BinPackProblem) → BinPackSolution

Transform Facility solution back to BinPack solution.

Parameters:

• solution – Facility Location solution

• source_problem – Original BinPack problem

Returns:

Equivalent BinPack solution

forward_transform_solution(solution: BinPackSolution, target_problem: FacilityProblem) → FacilitySolution | None

Transform BinPack solution to Facility solution (for warmstart).

Parameters:

• solution – BinPack solution

• target_problem – Target Facility problem

Returns:

Equivalent Facility solution for warmstart

get_forward_metadata() → TransformationMetadata

Metadata for forward problem transformation (BinPack → Facility).

This direction is LOSSY: incompatibility constraints cannot be represented.

transform_problem(source_problem: BinPackProblem) → FacilityProblem

Transform BinPack to Facility Location.

Parameters:

source_problem – BinPack problem instance

Returns:

Equivalent Facility Location problem

discrete_optimization.binpack.transformations.to_rcpsp module

Transformation from BinPacking to RCPSP.

Clever mapping: - Each item → task with duration=1 - Bin capacity → cumulative resource - Item weight → resource requirement - Incompatible items → virtual unary resources (capacity 1)

This allows using powerful RCPSP solvers for bin packing!

class discrete_optimization.binpack.transformations.to_rcpsp.BinpackToRcpspTransformation

Bases: ProblemTransformation[BinPackProblem, BinPackSolution, RcpspProblem, RcpspSolution]

Transform BinPacking to RCPSP.

Mapping strategy: - Each item → task with duration=1 - Bin capacity → cumulative resource “BinCapacity” - Item weight → resource requirement for that task - Time slot t → bin t (items at same time = same bin) - Incompatible items → virtual resources of capacity 1

Key insight: Tasks scheduled at the same time (time slot t) go in bin t. Cumulative resource constraint ensures bin capacity is respected. Virtual resources ensure incompatible items can’t be in same bin (same time).

This transformation is EXACT in both directions: - Forward (problem): All constraints can be represented (incompatibility via virtual resources) - Backward (solution): Time slots map directly to bin assignments

Example

# >>> # Bin packing: 3 items, capacity 10 # >>> # Item 0: weight 5, Item 1: weight 3, Item 2: weight 6 # >>> # Items 0 and 2 are incompatible # >>> problem = BinPackProblem( # … list_items=[ItemBinPack(0, 5), ItemBinPack(1, 3), ItemBinPack(2, 6)], # … capacity_bin=10, # … incompatible_items={(0, 2)} # … ) # >>> # >>> # RCPSP transformation: # >>> # - 3 tasks with duration=1 # >>> # - Resource “BinCapacity” with capacity=10 # >>> # - Task 0 needs 5, Task 1 needs 3, Task 2 needs 6 # >>> # - Resource “Incompatible_0_2” with capacity=1 (both tasks consume it) # >>> # - Tasks at time 0 → bin 0, tasks at time 1 → bin 1, etc.

back_transform_solution(solution: RcpspSolution, source_problem: BinPackProblem) → BinPackSolution

Transform RCPSP solution back to BinPacking solution.

Parameters:

• solution – RCPSP solution

• source_problem – Original BinPacking problem

Returns:

Equivalent BinPacking solution

forward_transform_solution(solution: BinPackSolution, target_problem: RcpspProblem) → RcpspSolution | None

Transform BinPacking solution to RCPSP solution (for warmstart).

Parameters:

• solution – BinPacking solution

• target_problem – Target RCPSP problem

Returns:

Equivalent RCPSP solution for warmstart

get_forward_metadata() → TransformationMetadata

Metadata for forward problem transformation (BinPack → RCPSP).

This direction is EXACT: all constraints can be represented in RCPSP.

transform_problem(source_problem: BinPackProblem) → RcpspProblem

Transform BinPacking to RCPSP.

Parameters:

source_problem – BinPacking problem instance

Returns:

Equivalent RCPSP problem

discrete_optimization.binpack.transformations.to_salbp module

Transformation from BinPack to SALBP (Assembly Line Balancing).

class discrete_optimization.binpack.transformations.to_salbp.BinpackToSalbpTransformation

Bases: ProblemTransformation[BinPackProblem, BinPackSolution, SalbpProblem, SalbpSolution]

Transform BinPack problem to SALBP (Assembly Line Balancing) problem.

Mapping: - Items (with weights) → Tasks (with processing times) - Bin capacity → Station cycle time - Minimize bins → Minimize stations - No precedence constraints (empty list)

This transformation is INCOMPLETE IN BOTH DIRECTIONS: - Forward (problem): LOSSY - incompatibility constraints cannot be represented in SALBP - Backward (solution): LOSSY - precedence constraints from SALBP cannot be verified in BinPack

Only use when:

• BinPack has NO incompatibility constraints AND

• SALBP has NO precedence constraints

• In this case, both problems are equivalent (pure capacity allocation)

back_transform_solution(solution: SalbpSolution, source_problem: BinPackProblem) → BinPackSolution

Transform SALBP solution back to BinPack solution.

Parameters:

• solution – SALBP solution (allocation_to_station)

• source_problem – Original BinPack problem

Returns:

Equivalent BinPack solution

forward_transform_solution(solution: BinPackSolution, target_problem: SalbpProblem) → SalbpSolution | None

Transform BinPack solution to SALBP solution (for warmstart).

Parameters:

• solution – BinPack solution

• target_problem – Target SALBP problem

Returns:

Equivalent SALBP solution for warmstart

get_forward_metadata() → TransformationMetadata

Metadata for forward problem transformation (BinPack → SALBP).

This direction is LOSSY: incompatibility constraints cannot be represented.

transform_problem(source_problem: BinPackProblem) → SalbpProblem

Transform BinPack to SALBP.

Parameters:

source_problem – BinPack problem instance

Returns:

Equivalent SALBP problem

Module contents

Problem transformations for BinPacking.

class discrete_optimization.binpack.transformations.BinpackToFacilityTransformation(setup_cost_per_bin: float = 1.0)

Bases: ProblemTransformation[BinPackProblem, BinPackSolution, FacilityProblem, FacilitySolution]

Transform BinPack problem to Facility Location problem.

Mapping: - Items (with weights) → Customers (with demands) - Bins (with capacity) → Facilities (with capacity) - Opening a bin → Setup cost for facility (cost = 1) - Minimize bins → Minimize setup costs - No spatial component (all locations at origin) - No assignment costs (distance-based cost = 0)

This transformation is ASYMMETRIC: - Forward (problem): LOSSY - incompatibility constraints lost - Backward (solution): EXACT - facility assignments map to bins

back_transform_solution(solution: FacilitySolution, source_problem: BinPackProblem) → BinPackSolution

Transform Facility solution back to BinPack solution.

Parameters:

• solution – Facility Location solution

• source_problem – Original BinPack problem

Returns:

Equivalent BinPack solution

forward_transform_solution(solution: BinPackSolution, target_problem: FacilityProblem) → FacilitySolution | None

Transform BinPack solution to Facility solution (for warmstart).

Parameters:

• solution – BinPack solution

• target_problem – Target Facility problem

Returns:

Equivalent Facility solution for warmstart

get_forward_metadata() → TransformationMetadata

Metadata for forward problem transformation (BinPack → Facility).

This direction is LOSSY: incompatibility constraints cannot be represented.

transform_problem(source_problem: BinPackProblem) → FacilityProblem

Transform BinPack to Facility Location.

Parameters:

source_problem – BinPack problem instance

Returns:

Equivalent Facility Location problem

class discrete_optimization.binpack.transformations.BinpackToRcpspTransformation

Bases: ProblemTransformation[BinPackProblem, BinPackSolution, RcpspProblem, RcpspSolution]

Transform BinPacking to RCPSP.

Mapping strategy: - Each item → task with duration=1 - Bin capacity → cumulative resource “BinCapacity” - Item weight → resource requirement for that task - Time slot t → bin t (items at same time = same bin) - Incompatible items → virtual resources of capacity 1

Key insight: Tasks scheduled at the same time (time slot t) go in bin t. Cumulative resource constraint ensures bin capacity is respected. Virtual resources ensure incompatible items can’t be in same bin (same time).

This transformation is EXACT in both directions: - Forward (problem): All constraints can be represented (incompatibility via virtual resources) - Backward (solution): Time slots map directly to bin assignments

Example

# >>> # Bin packing: 3 items, capacity 10 # >>> # Item 0: weight 5, Item 1: weight 3, Item 2: weight 6 # >>> # Items 0 and 2 are incompatible # >>> problem = BinPackProblem( # … list_items=[ItemBinPack(0, 5), ItemBinPack(1, 3), ItemBinPack(2, 6)], # … capacity_bin=10, # … incompatible_items={(0, 2)} # … ) # >>> # >>> # RCPSP transformation: # >>> # - 3 tasks with duration=1 # >>> # - Resource “BinCapacity” with capacity=10 # >>> # - Task 0 needs 5, Task 1 needs 3, Task 2 needs 6 # >>> # - Resource “Incompatible_0_2” with capacity=1 (both tasks consume it) # >>> # - Tasks at time 0 → bin 0, tasks at time 1 → bin 1, etc.

back_transform_solution(solution: RcpspSolution, source_problem: BinPackProblem) → BinPackSolution

Transform RCPSP solution back to BinPacking solution.

Parameters:

• solution – RCPSP solution

• source_problem – Original BinPacking problem

Returns:

Equivalent BinPacking solution

forward_transform_solution(solution: BinPackSolution, target_problem: RcpspProblem) → RcpspSolution | None

Transform BinPacking solution to RCPSP solution (for warmstart).

Parameters:

• solution – BinPacking solution

• target_problem – Target RCPSP problem

Returns:

Equivalent RCPSP solution for warmstart

get_forward_metadata() → TransformationMetadata

Metadata for forward problem transformation (BinPack → RCPSP).

This direction is EXACT: all constraints can be represented in RCPSP.

transform_problem(source_problem: BinPackProblem) → RcpspProblem

Transform BinPacking to RCPSP.

Parameters:

source_problem – BinPacking problem instance

Returns:

Equivalent RCPSP problem

class discrete_optimization.binpack.transformations.BinpackToSalbpTransformation

Bases: ProblemTransformation[BinPackProblem, BinPackSolution, SalbpProblem, SalbpSolution]

Transform BinPack problem to SALBP (Assembly Line Balancing) problem.

Mapping: - Items (with weights) → Tasks (with processing times) - Bin capacity → Station cycle time - Minimize bins → Minimize stations - No precedence constraints (empty list)

This transformation is INCOMPLETE IN BOTH DIRECTIONS: - Forward (problem): LOSSY - incompatibility constraints cannot be represented in SALBP - Backward (solution): LOSSY - precedence constraints from SALBP cannot be verified in BinPack

Only use when:

• BinPack has NO incompatibility constraints AND

• SALBP has NO precedence constraints

• In this case, both problems are equivalent (pure capacity allocation)

back_transform_solution(solution: SalbpSolution, source_problem: BinPackProblem) → BinPackSolution

Transform SALBP solution back to BinPack solution.

Parameters:

• solution – SALBP solution (allocation_to_station)

• source_problem – Original BinPack problem

Returns:

Equivalent BinPack solution

forward_transform_solution(solution: BinPackSolution, target_problem: SalbpProblem) → SalbpSolution | None

Transform BinPack solution to SALBP solution (for warmstart).

Parameters:

• solution – BinPack solution

• target_problem – Target SALBP problem

Returns:

Equivalent SALBP solution for warmstart

get_forward_metadata() → TransformationMetadata

Metadata for forward problem transformation (BinPack → SALBP).

This direction is LOSSY: incompatibility constraints cannot be represented.

transform_problem(source_problem: BinPackProblem) → SalbpProblem

Transform BinPack to SALBP.

Parameters:

source_problem – BinPack problem instance

Returns:

Equivalent SALBP problem