discrete_optimization.coloring.solvers package

Submodules

discrete_optimization.coloring.solvers.asp module

class discrete_optimization.coloring.solvers.asp.AspColoringSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: AspClingoSolver, WithStartingSolutionColoringSolver

Solver based on Answer Set Programming formulation and clingo solver.

build_string_data_input(nb_colors, nb_colors_subset: int | None = None)

compute_clever_colors_map(colors_name: list[str])

constrained_data_input()

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='greedy_start', default=True, depends_on=None, name_in_kwargs='greedy_start'), EnumHyperparameter(name='greedy_method', default=<NxGreedyColoringMethod.best: 'best'>, depends_on=('greedy_start', [True]), name_in_kwargs='greedy_method')]

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

Initialize internal model used to solve.

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

init_model_with_subset(**kwargs: Any) → None

init_model_without_subset(**kwargs: Any) → None

retrieve_solution(model: Model) → ColoringSolution

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_solver module

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

Bases: SolverDO

problem: ColoringProblem

discrete_optimization.coloring.solvers.cp_mzn 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.cp_mzn.CpColoringModel(value)

Bases: Enum

An enumeration.

CLIQUES = 0

DEFAULT = 1

DEFAULT_WITH_SUBSET = 3

LNS = 2

class discrete_optimization.coloring.solvers.cp_mzn.CpColoringSolver(problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None, cp_solver_name: CpSolverName = CpSolverName.CHUFFED, silent_solve_error: bool = False, **kwargs: Any)

Bases: MinizincCpSolver, ColoringSolver

add_coloring_constraint(coloring_constraint: ColoringConstraints)

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

[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

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_solver_name', default=<CpSolverName.CHUFFED: 0>, depends_on=None, name_in_kwargs='cp_solver_name'), EnumHyperparameter(name='cp_model', default=<CpColoringModel.DEFAULT: 1>, depends_on=None, name_in_kwargs='cp_model'), CategoricalHyperparameter(name='include_seq_chain_constraint', default=True, depends_on=None, name_in_kwargs='include_seq_chain_constraint')]

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

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 (CpColoringModel) – 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

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:

discrete_optimization.coloring.solvers.cpsat module

class discrete_optimization.coloring.solvers.cpsat.CpSatColoringSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OrtoolsCpSatSolver, WithStartingSolutionColoringSolver, WarmstartMixin

hyperparameters: list[Hyperparameter] = [EnumHyperparameter(name='modeling', default=<ModelingCpSat.INTEGER: 1>, depends_on=None, name_in_kwargs='modeling'), CategoricalHyperparameter(name='do_warmstart', default=True, depends_on=None, name_in_kwargs='do_warmstart'), CategoricalHyperparameter(name='value_sequence_chain', default=False, depends_on=('modeling', [<ModelingCpSat.INTEGER: 1>]), name_in_kwargs='value_sequence_chain'), CategoricalHyperparameter(name='used_variable', default=False, depends_on=('modeling', [<ModelingCpSat.INTEGER: 1>]), name_in_kwargs='used_variable'), CategoricalHyperparameter(name='symmetry_on_used', default=True, depends_on=('modeling', [<ModelingCpSat.INTEGER: 1>]), name_in_kwargs='symmetry_on_used'), CategoricalHyperparameter(name='greedy_start', default=True, depends_on=None, name_in_kwargs='greedy_start'), EnumHyperparameter(name='greedy_method', default=<NxGreedyColoringMethod.best: 'best'>, depends_on=('greedy_start', [True]), name_in_kwargs='greedy_method')]

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

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

init_model_binary(nb_colors: int, **kwargs)

init_model_integer(nb_colors: int, **kwargs)

retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → Solution

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(solution: ColoringSolution) → None

Make the solver warm start from the given solution.

set_warm_start_binary(solution: ColoringSolution)

set_warm_start_integer(solution: ColoringSolution)

class discrete_optimization.coloring.solvers.cpsat.ModelingCpSat(value)

Bases: Enum

An enumeration.

BINARY = 0

INTEGER = 1

discrete_optimization.coloring.solvers.dp module

class discrete_optimization.coloring.solvers.dp.DpColoringModeling(value)

Bases: Enum

An enumeration.

COLOR_NODE_TRANSITION = 1

COLOR_TRANSITION = 0

class discrete_optimization.coloring.solvers.dp.DpColoringSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: DpSolver, ColoringSolver, WarmstartMixin

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='solver', default=<class 'builtins.CABS'>, depends_on=None, name_in_kwargs='solver'), EnumHyperparameter(name='modeling', default=<DpColoringModeling.COLOR_TRANSITION: 0>, depends_on=None, name_in_kwargs='modeling'), CategoricalHyperparameter(name='dual_bound', default=True, depends_on=None, name_in_kwargs='dual_bound')]

Hyperparameters available for this solver.

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

• __init__()

• init_model() (when available)

• solve()

init_model(**kwargs)

Initialize internal model used to solve.

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

init_model_color(**kwargs: Any) → None

init_model_color_and_node(**kwargs: Any) → None

modeling: DpColoringModeling

nodes_reordering: list

retrieve_solution(sol: Solution) → Solution

retrieve_solution_color(sol: Solution) → Solution

retrieve_solution_color_and_node(sol: Solution) → Solution

set_warm_start(solution: ColoringSolution) → None

Make the solver warm start from the given solution.

transitions: dict

discrete_optimization.coloring.solvers.dp.bfs_iterator(g: Graph, source: Any) → Iterator[Any]

discrete_optimization.coloring.solvers.greedy module

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

class discrete_optimization.coloring.solvers.greedy.GreedyColoringSolver(problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: ColoringSolver

Binded solver of networkx heuristics for coloring problem.

hyperparameters: list[Hyperparameter] = [EnumHyperparameter(name='strategy', default=<NxGreedyColoringMethod.best: 'best'>, depends_on=None, name_in_kwargs='strategy')]

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

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.NxGreedyColoringMethod(value)

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'

discrete_optimization.coloring.solvers.lns_cp module

Easy Large neighborhood search solver for coloring.

class discrete_optimization.coloring.solvers.lns_cp.FixColorsCpSatConstraintHandler(problem: ColoringProblem, fraction_to_fix: float = 0.9)

Bases: OrtoolsCpSatConstraintHandler

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(solver: CpSatColoringSolver, result_storage: ResultStorage, **kwargs: Any) → Iterable[Constraint]

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

Parameters:

• solver – 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, depends_on=None, name_in_kwargs='fraction_to_fix', low=0.0, high=1.0, suggest_low=False, suggest_high=False, step=None, log=False)]

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.lns_cp.FixColorsMznConstraintHandler(problem: ColoringProblem, fraction_to_fix: float = 0.9)

Bases: MznConstraintHandler

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(solver: MinizincCpSolver, child_instance: Instance, result_storage: ResultStorage, last_result_store: ResultStorage | None = None, **kwargs: Any) → Iterable[Any]

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

Parameters:

• solver – 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, depends_on=None, name_in_kwargs='fraction_to_fix', low=0.0, high=1.0, suggest_low=False, suggest_high=False, step=None, log=False)]

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.lns_cp.InitialColoring(problem: ColoringProblem, initial_method: InitialColoringMethod, params_objective_function: ParamsObjectiveFunction | None = None)

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

Compute initial solution via greedy methods.

Returns: initial solution storage

hyperparameters: list[Hyperparameter] = [EnumHyperparameter(name='initial_method', default=<InitialColoringMethod.GREEDY: 1>, depends_on=None, name_in_kwargs='initial_method')]

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.lns_cp.InitialColoringMethod(value)

Bases: Enum

An enumeration.

DUMMY = 0

GREEDY = 1

class discrete_optimization.coloring.solvers.lns_cp.LnsCpColoringSolver(problem: ColoringProblem, subsolver: MinizincCpSolver | None = None, initial_solution_provider: InitialSolution | None = None, constraint_handler: MznConstraintHandler | None = None, post_process_solution: PostProcessSolution | None = None, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: LnsCpMzn, ColoringSolver

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

hyperparameters: list[Hyperparameter] = [SubBrickHyperparameter(name='subsolver', default=None, depends_on=None, name_in_kwargs='subsolver_subbrick'), SubBrickHyperparameter(name='initial_solution_provider', default=None, depends_on=('skip_initial_solution_provider', [False]), name_in_kwargs='initial_solution_provider_subbrick'), SubBrickHyperparameter(name='constraint_handler', default=None, depends_on=None, name_in_kwargs='constraint_handler_subbrick'), SubBrickHyperparameter(name='post_process_solution', default=None, depends_on=None, name_in_kwargs='post_process_solution_subbrick'), CategoricalHyperparameter(name='skip_initial_solution_provider', default=False, depends_on=None, name_in_kwargs='skip_initial_solution_provider')]

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.lns_cp.PostProcessSolutionColoring(problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None)

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

discrete_optimization.coloring.solvers.lns_cp.build_default_constraint_handler(coloring_problem: ColoringProblem, **kwargs)

discrete_optimization.coloring.solvers.lns_cp.build_default_cp_model(coloring_problem: ColoringProblem, **kwargs)

discrete_optimization.coloring.solvers.lns_cp.build_default_initial_solution(coloring_problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

discrete_optimization.coloring.solvers.lns_cp.build_default_postprocess(coloring_problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

discrete_optimization.coloring.solvers.lns_lp module

Large neighborhood search + Linear programming toolbox for coloring problem.

class discrete_optimization.coloring.solvers.lns_lp.FixColorsGurobiConstraintHandler(problem: ColoringProblem, fraction_to_fix: float = 0.9)

Bases: GurobiConstraintHandler, _BaseFixColorsConstraintHandler

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(solver: GurobiColoringSolver, result_storage: ResultStorage, **kwargs: Any) → Iterable[Any]

class discrete_optimization.coloring.solvers.lns_lp.FixColorsMathOptConstraintHandler(problem: ColoringProblem, fraction_to_fix: float = 0.9)

Bases: OrtoolsMathOptConstraintHandler, _BaseFixColorsConstraintHandler

Constraint builder used in LNS+LP (using mathopt 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(solver: MathOptColoringSolver, result_storage: ResultStorage, **kwargs: Any) → Iterable[Any]

class discrete_optimization.coloring.solvers.lns_lp.InitialColoring(problem: ColoringProblem, initial_method: InitialColoringMethod, params_objective_function: ParamsObjectiveFunction)

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

class discrete_optimization.coloring.solvers.lns_lp.InitialColoringMethod(value)

Bases: Enum

An enumeration.

DUMMY = 0

GREEDY = 1

discrete_optimization.coloring.solvers.lp module

Linear programming models and solve functions for Coloring problem.

class discrete_optimization.coloring.solvers.lp.ConstraintsDict

Bases: TypedDict

constraints_neighbors: dict[tuple[Hashable, Hashable, int], LinearConstraint]

one_color_constraints: dict[int, LinearConstraint]

class discrete_optimization.coloring.solvers.lp.GurobiColoringSolver(problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: GurobiMilpSolver, _BaseLpColoringSolver

Coloring LP solver based on gurobipy library.

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

convert_to_variable_values(solution: ColoringSolution) → dict[gurobipy.Var, float]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start().

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='greedy_start', default=True, depends_on=None, name_in_kwargs='greedy_start'), CategoricalHyperparameter(name='use_cliques', default=False, depends_on=None, name_in_kwargs='use_cliques')]

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

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.

class discrete_optimization.coloring.solvers.lp.MathOptColoringSolver(problem: ColoringProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OrtoolsMathOptMilpSolver, _BaseLpColoringSolver

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

convert_to_variable_values(solution: ColoringSolution) → dict[Variable, float]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start() to provide a suitable SolutionHint.variable_values. See https://or-tools.github.io/docs/pdoc/ortools/math_opt/python/model_parameters.html#SolutionHint for more information.

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='greedy_start', default=True, depends_on=None, name_in_kwargs='greedy_start'), CategoricalHyperparameter(name='use_cliques', default=False, depends_on=None, name_in_kwargs='use_cliques')]

Hyperparameters available for this solver.

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

• __init__()

• init_model() (when available)

• solve()

problem: ColoringProblem

discrete_optimization.coloring.solvers.quantum module

class discrete_optimization.coloring.solvers.quantum.FeasibleNbColorColoringQiskit(problem: ColoringProblem, nb_color=None)

Bases: object

interpret(result: object | ndarray)

to_quadratic_program() → object

class discrete_optimization.coloring.solvers.quantum.FeasibleNbColorQaoaColoringSolver(problem: ColoringProblem, nb_color=None, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: ColoringSolver, QiskitQaoaSolver

init_model(**kwargs)

Initialize internal model used to solve.

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

retrieve_current_solution(result) → Solution

Retrieve current solution from qiskit result.

Parameters:

result – list of value for each binary variable of the problem

Returns:

the converted solution at d-o format

class discrete_optimization.coloring.solvers.quantum.FeasibleNbColorVqeColoringSolver(problem: ColoringProblem, nb_color=None, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: ColoringSolver, QiskitVqeSolver

init_model(**kwargs)

Initialize internal model used to solve.

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

retrieve_current_solution(result) → Solution

Retrieve current solution from qiskit result.

Parameters:

result – list of value for each binary variable of the problem

Returns:

the converted solution at d-o format

class discrete_optimization.coloring.solvers.quantum.MinimizeNbColorColoringQiskit(problem: ColoringProblem, nb_max_color=None)

Bases: object

interpret(result: object | ndarray)

to_quadratic_program() → object

class discrete_optimization.coloring.solvers.quantum.MinimizeNbColorQaoaColoringSolver(problem: ColoringProblem, nb_max_color=None, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: ColoringSolver, QiskitQaoaSolver

init_model(**kwargs)

Initialize internal model used to solve.

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

retrieve_current_solution(result) → Solution

Retrieve current solution from qiskit result.

Parameters:

result – list of value for each binary variable of the problem

Returns:

the converted solution at d-o format

class discrete_optimization.coloring.solvers.quantum.MinimizeNbColorVqeColoringSolver(problem: ColoringProblem, nb_max_color=None, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: ColoringSolver, QiskitVqeSolver

init_model(**kwargs)

Initialize internal model used to solve.

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

retrieve_current_solution(result) → Solution

Retrieve current solution from qiskit result.

Parameters:

result – list of value for each binary variable of the problem

Returns:

the converted solution at d-o format

discrete_optimization.coloring.solvers.starting_solution module

class discrete_optimization.coloring.solvers.starting_solution.WithStartingSolutionColoringSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: ColoringSolver

get_starting_solution(**kwargs: Any) → ColoringSolution

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, depends_on=None, name_in_kwargs='greedy_start'), EnumHyperparameter(name='greedy_method', default=<NxGreedyColoringMethod.best: 'best'>, depends_on=('greedy_start', [True]), name_in_kwargs='greedy_method')]

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.toulbar module

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

Bases: WithStartingSolutionColoringSolver

default_costs_matrix(nb_colors_all: int, nb_colors_on_subset: int)

get_costs_matrix(index1: int, index2: int, costs: dict[str, list], range_map: dict[int, Any])

get_range_value(index_node: int, nb_colors_on_subset: int, nb_colors_all: int)

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='greedy_start', default=True, depends_on=None, name_in_kwargs='greedy_start'), EnumHyperparameter(name='greedy_method', default=<NxGreedyColoringMethod.best: 'best'>, depends_on=('greedy_start', [True]), name_in_kwargs='greedy_method'), CategoricalHyperparameter(name='value_sequence_chain', default=False, depends_on=None, name_in_kwargs='value_sequence_chain'), CategoricalHyperparameter(name='hard_value_sequence_chain', default=False, depends_on=('value_sequence_chain', [True]), name_in_kwargs='hard_value_sequence_chain'), IntegerHyperparameter(name='tolerance_delta_max', default=1, depends_on=('value_sequence_chain', [True]), name_in_kwargs='tolerance_delta_max', low=0, high=2, step=1, log=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

Initialize internal model used to solve.

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

model: pytoulbar2.CFN | None = None

solve(time_limit: int | None = 20, **kwargs: Any) → ResultStorage

Parameters:

• time_limit – the solve process stops after this time limit (in seconds). If None, no time limit is applied.

• **kwargs

Returns:

Module contents