discrete_optimization.coloring.transformations package

Submodules

discrete_optimization.coloring.transformations.from_list_coloring module

Transformation from ListColoringProblem to ColoringProblem using dummy nodes.

class discrete_optimization.coloring.transformations.from_list_coloring.ListColoringToColoringTransformation[source]

Bases: ProblemTransformation[ListColoringProblem, ColoringSolution, ColoringProblem, ColoringSolution]

Transform ListColoringProblem to ColoringProblem using dummy nodes.

Mapping: - Create K dummy nodes (one per color) - Dummy nodes form a complete clique (all connected) - Dummy node k is fixed to color k - Original node can use color k only if NOT connected to dummy node k - Use subset_nodes to focus optimization on original nodes only

This encoding allows standard coloring solvers to solve list coloring problems.

This transformation is EXACT in both directions.

back_transform_solution(solution: ColoringSolution, source_problem: ListColoringProblem) → ColoringSolution[source]

Transform Coloring solution back to ListColoring solution.

Parameters:

  • solution – Coloring solution (with dummy nodes)

  • source_problem – Original ListColoringProblem

Returns:

Equivalent ListColoring solution (without dummy nodes)

forward_transform_solution(solution: ColoringSolution, target_problem: ColoringProblem) → ColoringSolution | None[source]

Transform ListColoring solution to Coloring solution (for warmstart).

Parameters:

  • solution – ListColoring solution

  • target_problem – Target ColoringProblem (with dummy nodes)

Returns:

Equivalent Coloring solution (with dummy node colors added)

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (ListColoring → Coloring).

This direction is EXACT: list coloring can be perfectly encoded as standard coloring.

transform_problem(source_problem: ListColoringProblem) → ColoringProblem[source]

Transform ListColoringProblem to ColoringProblem with dummy nodes.

Parameters:

source_problem – ListColoringProblem instance

Returns:

Equivalent ColoringProblem with dummy color nodes

discrete_optimization.coloring.transformations.to_list_coloring module

Transformation from ColoringProblem to ListColoringProblem.

class discrete_optimization.coloring.transformations.to_list_coloring.ColoringToListColoringTransformation[source]

Bases: ProblemTransformation[ColoringProblem, ColoringSolution, ListColoringProblem, ColoringSolution]

Transform ColoringProblem to ListColoringProblem.

Mapping: - Standard coloring → List coloring with all colors allowed for all nodes - Graph structure preserved - Solution space identical (all colors available everywhere)

This transformation is EXACT in both directions.

back_transform_solution(solution: ColoringSolution, source_problem: ColoringProblem) → ColoringSolution[source]

Transform ListColoring solution back to Coloring solution.

Parameters:

  • solution – ListColoring solution

  • source_problem – Original ColoringProblem

Returns:

Equivalent Coloring solution (same representation)

forward_transform_solution(solution: ColoringSolution, target_problem: ListColoringProblem) → ColoringSolution | None[source]

Transform Coloring solution to ListColoring solution (for warmstart).

Parameters:

  • solution – Coloring solution

  • target_problem – Target ListColoringProblem

Returns:

Equivalent ListColoring solution

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (Coloring → ListColoring).

This direction is EXACT: standard coloring is list coloring with unrestricted lists.

transform_problem(source_problem: ColoringProblem) → ListColoringProblem[source]

Transform ColoringProblem to ListColoringProblem.

Parameters:

source_problem – ColoringProblem instance

Returns:

Equivalent ListColoringProblem with all colors allowed

Module contents

Transformations between ColoringProblem and ListColoringProblem.

class discrete_optimization.coloring.transformations.ColoringToListColoringTransformation[source]

Bases: ProblemTransformation[ColoringProblem, ColoringSolution, ListColoringProblem, ColoringSolution]

Transform ColoringProblem to ListColoringProblem.

Mapping: - Standard coloring → List coloring with all colors allowed for all nodes - Graph structure preserved - Solution space identical (all colors available everywhere)

This transformation is EXACT in both directions.

back_transform_solution(solution: ColoringSolution, source_problem: ColoringProblem) → ColoringSolution[source]

Transform ListColoring solution back to Coloring solution.

Parameters:

  • solution – ListColoring solution

  • source_problem – Original ColoringProblem

Returns:

Equivalent Coloring solution (same representation)

forward_transform_solution(solution: ColoringSolution, target_problem: ListColoringProblem) → ColoringSolution | None[source]

Transform Coloring solution to ListColoring solution (for warmstart).

Parameters:

  • solution – Coloring solution

  • target_problem – Target ListColoringProblem

Returns:

Equivalent ListColoring solution

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (Coloring → ListColoring).

This direction is EXACT: standard coloring is list coloring with unrestricted lists.

transform_problem(source_problem: ColoringProblem) → ListColoringProblem[source]

Transform ColoringProblem to ListColoringProblem.

Parameters:

source_problem – ColoringProblem instance

Returns:

Equivalent ListColoringProblem with all colors allowed

class discrete_optimization.coloring.transformations.ListColoringToColoringTransformation[source]

Bases: ProblemTransformation[ListColoringProblem, ColoringSolution, ColoringProblem, ColoringSolution]

Transform ListColoringProblem to ColoringProblem using dummy nodes.

Mapping: - Create K dummy nodes (one per color) - Dummy nodes form a complete clique (all connected) - Dummy node k is fixed to color k - Original node can use color k only if NOT connected to dummy node k - Use subset_nodes to focus optimization on original nodes only

This encoding allows standard coloring solvers to solve list coloring problems.

This transformation is EXACT in both directions.

back_transform_solution(solution: ColoringSolution, source_problem: ListColoringProblem) → ColoringSolution[source]

Transform Coloring solution back to ListColoring solution.

Parameters:

  • solution – Coloring solution (with dummy nodes)

  • source_problem – Original ListColoringProblem

Returns:

Equivalent ListColoring solution (without dummy nodes)

forward_transform_solution(solution: ColoringSolution, target_problem: ColoringProblem) → ColoringSolution | None[source]

Transform ListColoring solution to Coloring solution (for warmstart).

Parameters:

  • solution – ListColoring solution

  • target_problem – Target ColoringProblem (with dummy nodes)

Returns:

Equivalent Coloring solution (with dummy node colors added)

get_forward_metadata() → TransformationMetadata[source]

Metadata for forward problem transformation (ListColoring → Coloring).

This direction is EXACT: list coloring can be perfectly encoded as standard coloring.

transform_problem(source_problem: ListColoringProblem) → ColoringProblem[source]

Transform ListColoringProblem to ColoringProblem with dummy nodes.

Parameters:

source_problem – ListColoringProblem instance

Returns:

Equivalent ColoringProblem with dummy color nodes