discrete_optimization.generic_tasks_tools.solvers.lns_cp package

Submodules

discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor module

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor.BaseConstraintExtractor

Bases: ABC, Generic[Task]

Base class for constraint extractor.

The constraints are extracted from a current solution + tasks subset.

abstract add_constraints(current_solution: TasksSolution[Task], solver: TasksCpSolver[Task], tasks_primary: set[Task], tasks_secondary: set[Task], **kwargs: Any) → list[Any]

Extract constraints and add them to the cp model.

Parameters:

• current_solution

• solver

• tasks_primary

• tasks_secondary

• **kwargs

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor.ChainingConstraintExtractor(frac_fixed_chaining: float = 0.25)

Bases: BaseConstraintExtractor[Task]

add_constraints(current_solution: TasksSolution[Task], solver: TasksCpSolver[Task], tasks_primary: set[Task], tasks_secondary: set[Task], **kwargs: Any) → list[Any]

Extract constraints and add them to the cp model.

Parameters:

• current_solution

• solver

• tasks_primary

• tasks_secondary

• **kwargs

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor.ConstraintExtractorList(extractors: list[BaseConstraintExtractor[Task]])

Bases: BaseConstraintExtractor[Task]

Extractor adding constraints from multiple sub-extractors.

add_constraints(current_solution: TasksSolution[Task], solver: TasksCpSolver[Task], tasks_primary: set[Task], tasks_secondary: set[Task], **kwargs: Any) → list[Any]

Extract constraints and add them to the cp model.

Parameters:

• current_solution

• solver

• tasks_primary

• tasks_secondary

• **kwargs

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor.MultimodeConstraintExtractor(fix_primary_tasks_modes: bool = False, fix_secondary_tasks_modes: bool = True)

Bases: BaseConstraintExtractor[Task]

Extractor adding constraints on modes.

add_constraints(current_solution: TasksSolution[Task], solver: TasksCpSolver[Task], tasks_primary: set[Task], tasks_secondary: set[Task], **kwargs: Any) → list[Any]

Extract constraints and add them to the cp model.

Parameters:

• current_solution

• solver

• tasks_primary

• tasks_secondary

• **kwargs

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor.NbChangesAllocationConstraintExtractor(nb_changes_max: int = 10)

Bases: BaseConstraintExtractor[Task]

add_constraints(current_solution: TasksSolution[Task], solver: TasksCpSolver[Task], tasks_primary: set[Task], tasks_secondary: set[Task], **kwargs: Any) → list[Any]

Extract constraints and add them to the cp model.

Parameters:

• current_solution

• solver

• tasks_primary

• tasks_secondary

• **kwargs

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor.NbUsagesAllocationConstraintExtractor(plus_delta_nb_usages_total: int = 5, plus_delta_nb_usages_per_unary_resource: int = 3, minus_delta_nb_usages_per_unary_resource: int = 3)

Bases: BaseConstraintExtractor[Task]

add_constraints(current_solution: TasksSolution[Task], solver: TasksCpSolver[Task], tasks_primary: set[Task], tasks_secondary: set[Task], **kwargs: Any) → list[Any]

Extract constraints and add them to the cp model.

Parameters:

• current_solution

• solver

• tasks_primary

• tasks_secondary

• **kwargs

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor.ParamsConstraintExtractor(minus_delta_primary: int = 5, plus_delta_primary: int = 5, minus_delta_secondary: int = 0, plus_delta_secondary: int = 0, constraint_to_current_solution_makespan: bool = True, margin_rel_to_current_solution_makespan: float = 0.05, minus_delta_primary_duration: int = 5, plus_delta_primary_duration: int = 5, minus_delta_secondary_duration: int = 5, plus_delta_secondary_duration: int = 5, fix_primary_tasks_modes: bool = False, fix_secondary_tasks_modes: bool = True, chaining: bool = False, frac_fixed_chaining: float = 0.25, allocation_subtasks: bool = True, fix_secondary_tasks_allocation: bool = False, frac_random_fixed_tasks: float = 0.6, allocation_subresources: bool = False, frac_random_fixed_unary_resources: float = 0.5, nb_changes: bool = False, nb_changes_max: int = 10, nb_usages: bool = False, plus_delta_nb_usages_total: int = 5, plus_delta_nb_usages_per_unary_resource: int = 3, minus_delta_nb_usages_per_unary_resource: int = 3)

Bases: Hyperparametrizable

hyperparameters: list[Hyperparameter] = [IntegerHyperparameter(name='minus_delta_primary', default=5, depends_on=None, name_in_kwargs='minus_delta_primary', low=0, high=20, step=1, log=False), IntegerHyperparameter(name='plus_delta_primary', default=5, depends_on=None, name_in_kwargs='plus_delta_primary', low=0, high=20, step=1, log=False), IntegerHyperparameter(name='minus_delta_secondary', default=0, depends_on=None, name_in_kwargs='minus_delta_secondary', low=0, high=10, step=1, log=False), IntegerHyperparameter(name='plus_delta_secondary', default=0, depends_on=None, name_in_kwargs='plus_delta_secondary', low=0, high=10, step=1, log=False), IntegerHyperparameter(name='minus_delta_primary_duration', default=5, depends_on=None, name_in_kwargs='minus_delta_primary_duration', low=0, high=10, step=1, log=False), IntegerHyperparameter(name='plus_delta_primary_duration', default=5, depends_on=None, name_in_kwargs='plus_delta_primary_duration', low=0, high=10, step=1, log=False), IntegerHyperparameter(name='minus_delta_secondary_duration', default=5, depends_on=None, name_in_kwargs='minus_delta_secondary_duration', low=0, high=10, step=1, log=False), IntegerHyperparameter(name='plus_delta_secondary_duration', default=5, depends_on=None, name_in_kwargs='plus_delta_secondary_duration', low=0, high=10, step=1, log=False), CategoricalHyperparameter(name='chaining', default=False, depends_on=None, name_in_kwargs='chaining'), FloatHyperparameter(name='frac_fixed_chaining', default=0.25, depends_on=('chaining', [True]), name_in_kwargs='frac_fixed_chaining', low=0.0, high=1.0, suggest_low=False, suggest_high=False, step=None, log=False), CategoricalHyperparameter(name='fix_primary_tasks_modes', default=False, depends_on=None, name_in_kwargs='fix_primary_tasks_modes'), CategoricalHyperparameter(name='fix_secondary_tasks_modes', default=True, depends_on=None, name_in_kwargs='fix_secondary_tasks_modes'), CategoricalHyperparameter(name='allocation_subtasks', default=True, depends_on=None, name_in_kwargs='allocation_subtasks'), CategoricalHyperparameter(name='fix_secondary_tasks_allocation', default=False, depends_on=('allocation_subtasks', [True]), name_in_kwargs='fix_secondary_tasks_allocation'), FloatHyperparameter(name='frac_random_fixed_tasks', default=0.6, depends_on=('allocation_subtasks', [True]), name_in_kwargs='frac_random_fixed_tasks', low=0.0, high=1.0, suggest_low=False, suggest_high=False, step=None, log=False), CategoricalHyperparameter(name='allocation_subresources', default=False, depends_on=None, name_in_kwargs='allocation_subresources'), FloatHyperparameter(name='frac_random_fixed_unary_resources', default=0.5, depends_on=('allocation_subresources', [True]), name_in_kwargs='frac_random_fixed_unary_resources', low=0.0, high=1.0, suggest_low=False, suggest_high=False, step=None, log=False), CategoricalHyperparameter(name='nb_changes', default=False, depends_on=None, name_in_kwargs='nb_changes'), IntegerHyperparameter(name='nb_changes_max', default=10, depends_on=('nb_changes', [True]), name_in_kwargs='nb_changes_max', low=0, high=20, step=1, log=False), CategoricalHyperparameter(name='nb_usages', default=False, depends_on=None, name_in_kwargs='nb_usages'), IntegerHyperparameter(name='plus_delta_nb_usages_total', default=5, depends_on=('nb_usages', [True]), name_in_kwargs='plus_delta_nb_usages_total', low=0, high=10, step=1, log=False), IntegerHyperparameter(name='plus_delta_nb_usages_per_unary_resource', default=3, depends_on=('nb_usages', [True]), name_in_kwargs='plus_delta_nb_usages_per_unary_resource', low=0, high=5, step=1, log=False), IntegerHyperparameter(name='minus_delta_nb_usages_per_unary_resource', default=3, depends_on=('nb_usages', [True]), name_in_kwargs='minus_delta_nb_usages_per_unary_resource', low=0, high=5, 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()

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor.SchedulingConstraintExtractor(minus_delta_primary: int = 5, plus_delta_primary: int = 5, minus_delta_secondary: int = 0, plus_delta_secondary: int = 0)

Bases: BaseConstraintExtractor[Task]

add_constraints(current_solution: TasksSolution[Task], solver: TasksCpSolver[Task], tasks_primary: set[Task], tasks_secondary: set[Task], **kwargs) → list[Any]

Extract constraints and add them to the cp model.

Parameters:

• current_solution

• solver

• tasks_primary

• tasks_secondary

• **kwargs

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor.SubresourcesAllocationConstraintExtractor(frac_random_fixed_unary_resources: float = 0.5)

Bases: BaseConstraintExtractor[Task]

add_constraints(current_solution: TasksSolution[Task], solver: TasksCpSolver[Task], tasks_primary: set[Task], tasks_secondary: set[Task], **kwargs: Any) → list[Any]

Extract constraints and add them to the cp model.

Parameters:

• current_solution

• solver

• tasks_primary

• tasks_secondary

• **kwargs

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor.SubtasksAllocationConstraintExtractor(fix_secondary_tasks_allocation: bool = False, frac_random_fixed_tasks: float = 0.6)

Bases: BaseConstraintExtractor[Task]

add_constraints(current_solution: TasksSolution[Task], solver: TasksCpSolver[Task], tasks_primary: set[Task], tasks_secondary: set[Task], **kwargs: Any) → list[Any]

Extract constraints and add them to the cp model.

Parameters:

• current_solution

• solver

• tasks_primary

• tasks_secondary

• **kwargs

Returns:

discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor.build_default_constraint_extractor(problem: TasksProblem, params_constraint_extractor: ParamsConstraintExtractor) → BaseConstraintExtractor

discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_handler module

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_handler.ObjectiveSubproblem(value)

Bases: Enum

An enumeration.

GLOBAL_MAKESPAN = 4

INITIAL_OBJECTIVE = 0

MAKESPAN_SUBTASKS = 1

NB_TASKS_DONE = 5

NB_UNARY_RESOURCES_USED = 6

SUM_END_SUBTASKS = 3

SUM_START_SUBTASKS = 2

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_handler.TasksConstraintHandler(problem: TasksProblem, neighbor_builder: NeighborBuilder[Task] | None = None, constraints_extractor: BaseConstraintExtractor | None = None, params_constraint_extractor: ParamsConstraintExtractor | None = None, objective_subproblem: ObjectiveSubproblem = ObjectiveSubproblem.INITIAL_OBJECTIVE)

Bases: ConstraintHandler, Generic[Task]

Generic constraint handler for tasks related problems.

Include constraints for scheduling, multimode, and allocation features if present.

adding_constraint_from_results_store(solver: TasksCpSolver, result_storage: ResultStorage, result_storage_last_iteration: ResultStorage, **kwargs: Any) → Iterable[Any]

Add constraints to the internal model of a solver based on previous solutions

Parameters:

• solver – solver whose internal model is updated

• result_storage – all results so far

• result_storage_last_iteration – results from last LNS iteration only

• **kwargs

Returns:

list of added constraints

discrete_optimization.generic_tasks_tools.solvers.lns_cp.neighbor_tools module

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.neighbor_tools.NeighborBuilder

Bases: Generic[Task]

abstract find_subtasks(current_solution: TasksSolution[Task], subtasks: set[Task] | None = None) → tuple[set[Task], set[Task]]

Split the scheduling task set in 2 part, it can then be used by constraint handler to introduce different constraints in those two subsets. Usually the first returned set will be considered like the subproblem in LNS :param current_solution: current solution to consider :param subtasks: possibly existing subset of tasks that are in the neighborhood

Returns:

problem: TasksProblem[Task]

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.neighbor_tools.NeighborBuilderMix(list_neighbor: list[NeighborBuilder[Task]], weight_neighbor: list[float] | array, verbose: bool = False)

Bases: NeighborBuilder[Task]

find_subtasks(current_solution: TasksSolution[Task], subtasks: set[Task] | None = None) → tuple[set[Task], set[Task]]

Split the scheduling task set in 2 part, it can then be used by constraint handler to introduce different constraints in those two subsets. Usually the first returned set will be considered like the subproblem in LNS :param current_solution: current solution to consider :param subtasks: possibly existing subset of tasks that are in the neighborhood

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.neighbor_tools.NeighborBuilderSubPart(problem: TasksProblem[Task], nb_cut_part: int = 10)

Bases: NeighborBuilder[Task]

Cut the schedule in different subpart in the increasing order of the schedule.

find_subtasks(current_solution: TasksSolution[Task], subtasks: set[Task] | None = None) → tuple[set[Task], set[Task]]

Split the scheduling task set in 2 part, it can then be used by constraint handler to introduce different constraints in those two subsets. Usually the first returned set will be considered like the subproblem in LNS :param current_solution: current solution to consider :param subtasks: possibly existing subset of tasks that are in the neighborhood

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.neighbor_tools.NeighborBuilderTimeWindow(problem: TasksProblem[Task], time_window_length: int = 10)

Bases: NeighborBuilder[Task]

find_subtasks(current_solution: TasksSolution[Task], subtasks: set[Task] | None = None) → tuple[set[Task], set[Task]]

Split the scheduling task set in 2 part, it can then be used by constraint handler to introduce different constraints in those two subsets. Usually the first returned set will be considered like the subproblem in LNS :param current_solution: current solution to consider :param subtasks: possibly existing subset of tasks that are in the neighborhood

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.neighbor_tools.NeighborRandom(problem: TasksProblem[Task], fraction_subproblem: float = 0.9, delta_abs_time_from_makespan_to_not_fix: int = 5, delta_rel_time_from_makespan_to_not_fix: float = 0.0)

Bases: NeighborBuilder[Task]

find_subtasks(current_solution: TasksSolution[Task], subtasks: set[Task] | None = None) → tuple[set[Task], set[Task]]

Split the scheduling task set in 2 part, it can then be used by constraint handler to introduce different constraints in those two subsets. Usually the first returned set will be considered like the subproblem in LNS :param current_solution: current solution to consider :param subtasks: possibly existing subset of tasks that are in the neighborhood

Returns:

class discrete_optimization.generic_tasks_tools.solvers.lns_cp.neighbor_tools.NeighborRandomAndNeighborGraph(problem: TasksProblem[HashableTask], graph: Graph | None = None, fraction_subproblem: float = 0.05)

Bases: NeighborBuilder[HashableTask]

find_subtasks(current_solution: TasksSolution[HashableTask], subtasks: set[HashableTask] | None = None) → tuple[set[HashableTask], set[HashableTask]]

Split the scheduling task set in 2 part, it can then be used by constraint handler to introduce different constraints in those two subsets. Usually the first returned set will be considered like the subproblem in LNS :param current_solution: current solution to consider :param subtasks: possibly existing subset of tasks that are in the neighborhood

Returns:

discrete_optimization.generic_tasks_tools.solvers.lns_cp.neighbor_tools.build_default_neighbor_builder(problem: TasksProblem[Task]) → NeighborBuilder[Task]

discrete_optimization.generic_tasks_tools.solvers.lns_cp.neighbor_tools.intersect(i1: tuple[int, int], i2: tuple[int, int])

Module contents