discrete_optimization.coloring.solvers package

Submodules

discrete_optimization.coloring.solvers.coloring_asp_solver module

class discrete_optimization.coloring.solvers.coloring_asp_solver.ColoringASPSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: ASPClingoSolver, SolverColoringWithStartingSolution

Solver based on Answer Set Programming formulation and clingo solver.

build_string_data_input(nb_colors, nb_colors_subset: int | None = None)[source]
compute_clever_colors_map(colors_name: List[str])[source]
constrained_data_input()[source]
hyperparameters: List[Hyperparameter] = [CategoricalHyperparameter(name='greedy_start', default=True, choices=[True]), EnumHyperparameter(name='greedy_method', default=<NXGreedyColoringMethod.best: 'best'>, choices=[<NXGreedyColoringMethod.largest_first: 'largest_first'>, <NXGreedyColoringMethod.random_sequential: 'random_sequential'>, <NXGreedyColoringMethod.smallest_last: 'smallest_last'>, <NXGreedyColoringMethod.independent_set: 'independent_set'>, <NXGreedyColoringMethod.connected_sequential_dfs: 'connected_sequential_dfs'>, <NXGreedyColoringMethod.connected_sequential_bfs: 'connected_sequential_bfs'>, <NXGreedyColoringMethod.connected_sequential: 'connected_sequential'>, <NXGreedyColoringMethod.saturation_largest_first: 'saturation_largest_first'>, <NXGreedyColoringMethod.dsatur: 'DSATUR'>, <NXGreedyColoringMethod.best: 'best'>])]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

  • __init__()

  • init_model() (when available)

  • solve()

init_model(**kwargs: Any) → None[source]

Initialize intern model used to solve.

Can initialize a ortools, milp, gurobi, … model.

init_model_with_subset(**kwargs: Any) → None[source]
init_model_without_subset(**kwargs: Any) → None[source]
retrieve_solution(model: Model) → ColoringSolution[source]

Construct a do solution from a clingo model.

Parameters:

model – the current constructed clingo model

Returns:

the intermediate solution, at do format.

discrete_optimization.coloring.solvers.coloring_cp_lns module

Easy Large neighborhood search solver for coloring.

class discrete_optimization.coloring.solvers.coloring_cp_lns.LnsCpColoring(problem: ColoringProblem, cp_solver: MinizincCPSolver | None = None, initial_solution_provider: InitialSolution | None = None, constraint_handler: ConstraintHandler | None = None, post_process_solution: PostProcessSolution | None = None, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)[source]

Bases: LNS_CP, SolverColoring

Most easy way to use LNS-CP for coloring with some default parameters for constraint handler.

hyperparameters: List[Hyperparameter] = [SubBrickHyperparameter(name='cp_solver_cls', default=None, choices=[<class 'discrete_optimization.coloring.solvers.coloring_cp_solvers.ColoringCP'>]), SubBrickKwargsHyperparameter(name='cp_solver_kwargs', default=None), SubBrickHyperparameter(name='initial_solution_provider_cls', default=None, choices=[<class 'discrete_optimization.coloring.solvers.coloring_cp_lns_solvers.InitialColoring'>]), SubBrickKwargsHyperparameter(name='initial_solution_provider_kwargs', default=None), SubBrickHyperparameter(name='constraint_handler_cls', default=None, choices=[<class 'discrete_optimization.coloring.solvers.coloring_cp_lns_solvers.ConstraintHandlerFixColorsCP'>]), SubBrickKwargsHyperparameter(name='constraint_handler_kwargs', default=None), SubBrickHyperparameter(name='post_process_solution_cls', default=<class 'discrete_optimization.generic_tools.lns_mip.TrivialPostProcessSolution'>, choices=[<class 'discrete_optimization.generic_tools.lns_mip.TrivialPostProcessSolution'>, <class 'discrete_optimization.coloring.solvers.coloring_cp_lns_solvers.PostProcessSolutionColoring'>]), SubBrickKwargsHyperparameter(name='post_process_solution_kwargs', default=None), CategoricalHyperparameter(name='skip_first_iteration', default=False, choices=[True, False])]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

  • __init__()

  • init_model() (when available)

  • solve()

discrete_optimization.coloring.solvers.coloring_cp_lns.build_default_constraint_handler(coloring_model: ColoringProblem, **kwargs)[source]
discrete_optimization.coloring.solvers.coloring_cp_lns.build_default_cp_model(coloring_model: ColoringProblem, **kwargs)[source]
discrete_optimization.coloring.solvers.coloring_cp_lns.build_default_initial_solution(coloring_model: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None)[source]
discrete_optimization.coloring.solvers.coloring_cp_lns.build_default_postprocess(coloring_model: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None)[source]

discrete_optimization.coloring.solvers.coloring_cp_lns_solvers module

Large neighborhood search + Constraint programming toolbox for coloring problem.

class discrete_optimization.coloring.solvers.coloring_cp_lns_solvers.ConstraintHandlerFixColorsCP(problem: ColoringProblem, fraction_to_fix: float = 0.9)[source]

Bases: ConstraintHandler

Constraint builder for LNS coloring problem.

This constraint handler is pretty basic, it fixes a fraction_to_fix proportion of nodes color.

problem

input coloring problem

Type:

ColoringProblem

fraction_to_fix

float between 0 and 1, representing the proportion of nodes to constrain.

Type:

float

adding_constraint_from_results_store(cp_solver: CPSolver, child_instance: Instance, result_storage: ResultStorage, last_result_store: ResultStorage | None = None) → Iterable[Any][source]

Include constraint that fix decision on a subset of nodes, according to current solutions found.

Parameters:

  • cp_solver (CPSolver) – a coloring CPSolver

  • child_instance – minizinc instance where to include the constraint

  • result_storage – current pool of solutions

  • last_result_store – pool of solutions found in previous LNS iteration (optional)

Returns: an empty list, unused.

hyperparameters: List[Hyperparameter] = [FloatHyperparameter(name='fraction_to_fix', default=0.9, low=0.0, high=1.0)]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

  • __init__()

  • init_model() (when available)

  • solve()

remove_constraints_from_previous_iteration(cp_solver: CPSolver, child_instance: Instance, previous_constraints: Iterable[Any]) → None[source]
class discrete_optimization.coloring.solvers.coloring_cp_lns_solvers.InitialColoring(problem: ColoringProblem, initial_method: InitialColoringMethod, params_objective_function: ParamsObjectiveFunction)[source]

Bases: InitialSolution

Initial solution provider for lns algorithm.

problem

input coloring problem

Type:

ColoringProblem

initial_method

the method to use to provide the initial solution.

Type:

InitialColoringMethod

get_starting_solution() → ResultStorage[source]

Compute initial solution via greedy methods.

Returns: initial solution storage

hyperparameters: List[Hyperparameter] = [EnumHyperparameter(name='initial_method', default=<InitialColoringMethod.GREEDY: 1>, choices=[<InitialColoringMethod.DUMMY: 0>, <InitialColoringMethod.GREEDY: 1>])]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

  • __init__()

  • init_model() (when available)

  • solve()

class discrete_optimization.coloring.solvers.coloring_cp_lns_solvers.InitialColoringMethod(value)[source]

Bases: Enum

An enumeration.

DUMMY = 0
GREEDY = 1
class discrete_optimization.coloring.solvers.coloring_cp_lns_solvers.PostProcessSolutionColoring(problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction)[source]

Bases: PostProcessSolution

Post process class for coloring problem.

It transforms the color vector to have colors between 0 and nb_colors-1

problem

coloring instance

Type:

ColoringProblem

params_objective_function

params of the objective function

Type:

ParamsObjectiveFunction

build_other_solution(result_storage: ResultStorage) → ResultStorage[source]

discrete_optimization.coloring.solvers.coloring_cp_solvers module

Module containing Constraint Programming based solver for Coloring Problem.

CP formulation rely on minizinc models stored in coloring/minizinc folder.

class discrete_optimization.coloring.solvers.coloring_cp_solvers.ColoringCP(problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None, cp_solver_name: CPSolverName = CPSolverName.CHUFFED, silent_solve_error: bool = False, **kwargs: Any)[source]

Bases: MinizincCPSolver, SolverColoring

add_coloring_constraint(coloring_constraint: ConstraintsColoring)[source]
export_dzn(file_name: str | None = None, keys: Iterable[Any] | None = None) → None[source]

[DEBUG utility] Export the instantiated data into a dzn for potential debugs without python.

Parameters:

  • file_name (str) – file path where to dump the data file

  • keys (List[str]) – list of input data names to dump.

Returns: None

get_solution(**kwargs: Any) → ColoringSolution[source]

Used by the init_model method to provide a greedy first solution

Keyword Arguments:

  • greedy_start (bool) – use heuristics (based on networkx) to compute starting solution, otherwise the dummy method is used.

  • verbose (bool) – verbose option.

Returns (ColoringSolution): a starting coloring solution that can be used by lns.

hyperparameters: List[Hyperparameter] = [EnumHyperparameter(name='cp_model', default=<ColoringCPModel.DEFAULT: 1>, choices=[<ColoringCPModel.CLIQUES: 0>, <ColoringCPModel.DEFAULT: 1>, <ColoringCPModel.LNS: 2>, <ColoringCPModel.DEFAULT_WITH_SUBSET: 3>]), CategoricalHyperparameter(name='include_seq_chain_constraint', default=True, choices=[True, False])]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

  • __init__()

  • init_model() (when available)

  • solve()

init_model(**kwargs: Any) → None[source]

Instantiate a minizinc model with the coloring problem data.

Keyword Arguments:

  • nb_colors (int) – upper bound of number of colors to be considered by the model.

  • object_output (bool) – specify if the solution are returned in a ColoringCPSolution object or native minizinc output.

  • include_seq_chain_constraint (bool) – include the value_precede_chain in the minizinc model. See documentation of minizinc for the specification of this global constraint.

  • cp_model (ColoringCPModel) – CP model version.

  • max_cliques (int) – if cp_model == ColoringCPModel.CLIQUES, specify the max number of cliques to include in the model.

Returns: None

retrieve_solution(_output_item: str | None = None, **kwargs: Any) → ColoringSolution[source]

Return a d-o solution from the variables computed by minizinc.

Parameters:

  • _output_item – string representing the minizinc solver output passed by minizinc to the solution constructor

  • **kwargs – keyword arguments passed by minzinc to the solution contructor containing the objective value (key “objective”), and the computed variables as defined in minizinc model.

Returns:

class discrete_optimization.coloring.solvers.coloring_cp_solvers.ColoringCPModel(value)[source]

Bases: Enum

An enumeration.

CLIQUES = 0
DEFAULT = 1
DEFAULT_WITH_SUBSET = 3
LNS = 2

discrete_optimization.coloring.solvers.coloring_cpsat_solver module

class discrete_optimization.coloring.solvers.coloring_cpsat_solver.ColoringCPSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: OrtoolsCPSatSolver, SolverColoringWithStartingSolution

hyperparameters: List[Hyperparameter] = [EnumHyperparameter(name='modeling', default=<ModelingCPSat.INTEGER: 1>, choices=[<ModelingCPSat.BINARY: 0>, <ModelingCPSat.INTEGER: 1>]), CategoricalHyperparameter(name='warmstart', default=True, choices=[True, False]), CategoricalHyperparameter(name='value_sequence_chain', default=False, choices=[True, False]), CategoricalHyperparameter(name='used_variable', default=False, choices=[True, False]), CategoricalHyperparameter(name='symmetry_on_used', default=True, choices=[True, False]), CategoricalHyperparameter(name='greedy_start', default=True, choices=[True]), EnumHyperparameter(name='greedy_method', default=<NXGreedyColoringMethod.best: 'best'>, choices=[<NXGreedyColoringMethod.largest_first: 'largest_first'>, <NXGreedyColoringMethod.random_sequential: 'random_sequential'>, <NXGreedyColoringMethod.smallest_last: 'smallest_last'>, <NXGreedyColoringMethod.independent_set: 'independent_set'>, <NXGreedyColoringMethod.connected_sequential_dfs: 'connected_sequential_dfs'>, <NXGreedyColoringMethod.connected_sequential_bfs: 'connected_sequential_bfs'>, <NXGreedyColoringMethod.connected_sequential: 'connected_sequential'>, <NXGreedyColoringMethod.saturation_largest_first: 'saturation_largest_first'>, <NXGreedyColoringMethod.dsatur: 'DSATUR'>, <NXGreedyColoringMethod.best: 'best'>])]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

  • __init__()

  • init_model() (when available)

  • solve()

init_model(**args: Any) → None[source]

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

init_model_binary(nb_colors: int, **kwargs)[source]
init_model_integer(nb_colors: int, **kwargs)[source]
retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → Solution[source]

Construct a do solution from the cpsat solver internal solution.

It will be called each time the cpsat solver find a new solution. At that point, value of internal variables are accessible via cpsolvercb.Value(VARIABLE_NAME).

Parameters:

cpsolvercb – the ortools callback called when the cpsat solver finds a new solution.

Returns:

the intermediate solution, at do format.

set_warm_start_binary(solution: ColoringSolution)[source]
set_warm_start_integer(solution: ColoringSolution)[source]
set_warmstart(solution: ColoringSolution)[source]
class discrete_optimization.coloring.solvers.coloring_cpsat_solver.ModelingCPSat(value)[source]

Bases: Enum

An enumeration.

BINARY = 0
INTEGER = 1

discrete_optimization.coloring.solvers.coloring_lp_lns_solvers module

Large neighborhood search + Linear programming toolbox for coloring problem.

class discrete_optimization.coloring.solvers.coloring_lp_lns_solvers.ConstraintHandlerFixColorsGrb(problem: ColoringProblem, fraction_to_fix: float = 0.9)[source]

Bases: ConstraintHandler

Constraint builder used in LNS+LP (using gurobi solver) for coloring problem.

This constraint handler is pretty basic, it fixes a fraction_to_fix proportion of nodes color.

problem

input coloring problem

Type:

ColoringProblem

fraction_to_fix

float between 0 and 1, representing the proportion of nodes to constrain.

Type:

float

adding_constraint_from_results_store(milp_solver: MilpSolver, result_storage: ResultStorage) → Mapping[Hashable, Any][source]
remove_constraints_from_previous_iteration(milp_solver: MilpSolver, previous_constraints: Mapping[Hashable, Any]) → None[source]
class discrete_optimization.coloring.solvers.coloring_lp_lns_solvers.ConstraintHandlerFixColorsPyMip(problem: ColoringProblem, fraction_to_fix: float = 0.9)[source]

Bases: ConstraintHandler

Constraint builder used in LNS+ LP (using pymip library) for coloring problem.

This constraint handler is pretty basic, it fixes a fraction_to_fix proportion of nodes color.

problem

input coloring problem

Type:

ColoringProblem

fraction_to_fix

float between 0 and 1, representing the proportion of nodes to constrain.

Type:

float

adding_constraint_from_results_store(milp_solver: MilpSolver, result_storage: ResultStorage) → Mapping[Hashable, Any][source]
remove_constraints_from_previous_iteration(milp_solver: MilpSolver, previous_constraints: Mapping[Hashable, Any]) → None[source]
class discrete_optimization.coloring.solvers.coloring_lp_lns_solvers.InitialColoring(problem: ColoringProblem, initial_method: InitialColoringMethod, params_objective_function: ParamsObjectiveFunction)[source]

Bases: InitialSolution

Initial solution provider for lns algorithm.

problem

input coloring problem

Type:

ColoringProblem

initial_method

the method to use to provide the initial solution.

Type:

InitialColoringMethod

get_starting_solution() → ResultStorage[source]
class discrete_optimization.coloring.solvers.coloring_lp_lns_solvers.InitialColoringMethod(value)[source]

Bases: Enum

An enumeration.

DUMMY = 0
GREEDY = 1

discrete_optimization.coloring.solvers.coloring_lp_solvers module

Linear programming models and solve functions for Coloring problem.

class discrete_optimization.coloring.solvers.coloring_lp_solvers.ColoringLP(problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: GurobiMilpSolver, _BaseColoringLP

Coloring LP solver based on gurobipy library.

coloring_model

coloring problem instance to solve

Type:

ColoringProblem

params_objective_function

objective function parameters (however this is just used for the ResultStorage creation, not in the optimisation)

Type:

ParamsObjectiveFunction

hyperparameters: List[Hyperparameter] = [CategoricalHyperparameter(name='greedy_start', default=True, choices=[True, False]), CategoricalHyperparameter(name='use_cliques', default=False, choices=[True, False])]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

  • __init__()

  • init_model() (when available)

  • solve()

init_model(**kwargs: Any) → None[source]

Initialize the gurobi model.

Keyword Arguments:

  • greedy_start (bool) – if True, a greedy solution is computed (using GreedyColoring solver) and used as warm start for the LP.

  • use_cliques (bool) – if True, compute cliques of the coloring problem and add constraints to the model.

  • verbose (bool) – verbose option.

class discrete_optimization.coloring.solvers.coloring_lp_solvers.ColoringLP_MIP(problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None, milp_solver_name: MilpSolverName = MilpSolverName.CBC, **kwargs: Any)[source]

Bases: PymipMilpSolver, _BaseColoringLP

Coloring LP solver based on pymip library.

Note

Gurobi and CBC are available as backend solvers.

problem

coloring problem instance to solve

Type:

ColoringProblem

params_objective_function

objective function parameters (however this is just used for the ResultStorage creation, not in the optimisation)

Type:

ParamsObjectiveFunction

milp_solver_name

backend solver to use (either CBC ou GRB)

Type:

MilpSolverName

hyperparameters: List[Hyperparameter] = [CategoricalHyperparameter(name='greedy_start', default=True, choices=[True, False]), CategoricalHyperparameter(name='use_cliques', default=False, choices=[True, False])]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

  • __init__()

  • init_model() (when available)

  • solve()

init_model(**kwargs: Any) → None[source]

Initialize intern model used to solve.

Can initialize a ortools, milp, gurobi, … model.

class discrete_optimization.coloring.solvers.coloring_lp_solvers.ConstraintsDict[source]

Bases: TypedDict

constraints_neighbors: Dict[Tuple[Hashable, Hashable, int], Constr | QConstr | MConstr | GenConstr]
one_color_constraints: Dict[int, Constr | QConstr | MConstr | GenConstr]

discrete_optimization.coloring.solvers.coloring_solver module

class discrete_optimization.coloring.solvers.coloring_solver.SolverColoring(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SolverDO

problem: ColoringProblem

discrete_optimization.coloring.solvers.coloring_solver_with_starting_solution module

class discrete_optimization.coloring.solvers.coloring_solver_with_starting_solution.SolverColoringWithStartingSolution(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SolverColoring

get_starting_solution(**kwargs: Any) → ColoringSolution[source]

Used by the init_model method to provide a greedy first solution

Keyword Arguments:

  • greedy_start (bool) – use heuristics (based on networkx) to compute starting solution, otherwise the dummy method is used.

  • verbose (bool) – verbose option.

Returns (ColoringSolution): a starting coloring solution that can be used by lns.

hyperparameters: List[Hyperparameter] = [CategoricalHyperparameter(name='greedy_start', default=True, choices=[True]), EnumHyperparameter(name='greedy_method', default=<NXGreedyColoringMethod.best: 'best'>, choices=[<NXGreedyColoringMethod.largest_first: 'largest_first'>, <NXGreedyColoringMethod.random_sequential: 'random_sequential'>, <NXGreedyColoringMethod.smallest_last: 'smallest_last'>, <NXGreedyColoringMethod.independent_set: 'independent_set'>, <NXGreedyColoringMethod.connected_sequential_dfs: 'connected_sequential_dfs'>, <NXGreedyColoringMethod.connected_sequential_bfs: 'connected_sequential_bfs'>, <NXGreedyColoringMethod.connected_sequential: 'connected_sequential'>, <NXGreedyColoringMethod.saturation_largest_first: 'saturation_largest_first'>, <NXGreedyColoringMethod.dsatur: 'DSATUR'>, <NXGreedyColoringMethod.best: 'best'>])]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

  • __init__()

  • init_model() (when available)

  • solve()

discrete_optimization.coloring.solvers.coloring_toulbar_solver module

class discrete_optimization.coloring.solvers.coloring_toulbar_solver.ToulbarColoringSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SolverColoringWithStartingSolution

default_costs_matrix(nb_colors_all: int, nb_colors_on_subset: int)[source]
get_costs_matrix(index1: int, index2: int, costs: Dict[str, List], range_map: Dict[int, Any])[source]
get_range_value(index_node: int, nb_colors_on_subset: int, nb_colors_all: int)[source]
hyperparameters: List[Hyperparameter] = [CategoricalHyperparameter(name='greedy_start', default=True, choices=[True]), EnumHyperparameter(name='greedy_method', default=<NXGreedyColoringMethod.best: 'best'>, choices=[<NXGreedyColoringMethod.largest_first: 'largest_first'>, <NXGreedyColoringMethod.random_sequential: 'random_sequential'>, <NXGreedyColoringMethod.smallest_last: 'smallest_last'>, <NXGreedyColoringMethod.independent_set: 'independent_set'>, <NXGreedyColoringMethod.connected_sequential_dfs: 'connected_sequential_dfs'>, <NXGreedyColoringMethod.connected_sequential_bfs: 'connected_sequential_bfs'>, <NXGreedyColoringMethod.connected_sequential: 'connected_sequential'>, <NXGreedyColoringMethod.saturation_largest_first: 'saturation_largest_first'>, <NXGreedyColoringMethod.dsatur: 'DSATUR'>, <NXGreedyColoringMethod.best: 'best'>]), CategoricalHyperparameter(name='value_sequence_chain', default=False, choices=[True, False]), CategoricalHyperparameter(name='hard_value_sequence_chain', default=False, choices=[True, False]), IntegerHyperparameter(name='tolerance_delta_max', default=1, low=0, high=2)]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

  • __init__()

  • init_model() (when available)

  • solve()

init_model(**kwargs: Any) → None[source]

Initialize intern model used to solve.

Can initialize a ortools, milp, gurobi, … model.

model: pytoulbar2.CFN | None = None
solve(**kwargs: Any) → ResultStorage[source]

Generic solving function.

Parameters:

  • callbacks – list of callbacks used to hook into the various stage of the solve

  • **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

discrete_optimization.coloring.solvers.greedy_coloring module

Greedy solvers for coloring problem : binding from networkx library methods.

class discrete_optimization.coloring.solvers.greedy_coloring.GreedyColoring(problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SolverColoring

Binded solver of networkx heuristics for coloring problem.

hyperparameters: List[Hyperparameter] = [EnumHyperparameter(name='strategy', default=<NXGreedyColoringMethod.best: 'best'>, choices=[<NXGreedyColoringMethod.largest_first: 'largest_first'>, <NXGreedyColoringMethod.random_sequential: 'random_sequential'>, <NXGreedyColoringMethod.smallest_last: 'smallest_last'>, <NXGreedyColoringMethod.independent_set: 'independent_set'>, <NXGreedyColoringMethod.connected_sequential_dfs: 'connected_sequential_dfs'>, <NXGreedyColoringMethod.connected_sequential_bfs: 'connected_sequential_bfs'>, <NXGreedyColoringMethod.connected_sequential: 'connected_sequential'>, <NXGreedyColoringMethod.saturation_largest_first: 'saturation_largest_first'>, <NXGreedyColoringMethod.dsatur: 'DSATUR'>, <NXGreedyColoringMethod.best: 'best'>])]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

  • __init__()

  • init_model() (when available)

  • solve()

solve(**kwargs: Any) → ResultStorage[source]

Run the greedy solver for the given problem.

Keyword Arguments:

  • strategy (NXGreedyColoringMethod) – one of the method used by networkx to compute coloring solution, or use NXGreedyColoringMethod.best to run each of them and return the best result.

  • verbose (bool)

Returns:

storage of solution found by the greedy solver.

Return type:

results (ResultStorage)

class discrete_optimization.coloring.solvers.greedy_coloring.NXGreedyColoringMethod(value)[source]

Bases: Enum

An enumeration.

best = 'best'
connected_sequential = 'connected_sequential'
connected_sequential_bfs = 'connected_sequential_bfs'
connected_sequential_dfs = 'connected_sequential_dfs'
dsatur = 'DSATUR'
independent_set = 'independent_set'
largest_first = 'largest_first'
random_sequential = 'random_sequential'
saturation_largest_first = 'saturation_largest_first'
smallest_last = 'smallest_last'

Module contents