discrete_optimization.generic_tasks_tools.solvers package

Subpackages

Submodules

discrete_optimization.generic_tasks_tools.solvers.cpsat module

class discrete_optimization.generic_tasks_tools.solvers.cpsat.AllocationBinaryOrIntegerModellingCpSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: AllocationIntegerModellingCpSatSolver[Task, UnaryResource]

Base class for allocation cp-sat solvers using a binary or integer modelling.

add_allocation_changes_constraints(ref: AllocationSolution[Task, UnaryResource]) → list[Any][source]

Add and return constraints so that change variables reflect diff to ref.

add_constraint_on_task_unary_resource_allocation(task: Task, unary_resource: UnaryResource, used: bool) → list[Any][source]

Add constraint on allocation of given unary resource for the given task

Parameters:

  • task

  • unary_resource

  • used – if True, we enforce the allocation of unary_resource to task, else we prevent it

Returns:

resulting constraints

allocation_modelling: AllocationModelling
abstractmethod get_binary_allocation_variable(task: Task, unary_resource: UnaryResource) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64[source]

“Return a 0-1 variable/expression telling if the unary_resource is used for the task.

Only to be called when allocation_modelling == AllocationModelling.BINARY.

NB: sometimes the given resource is never to be used by a task and the variable has not been created. The convention is to return 0 in that case.

abstractmethod get_integer_allocation_variable(task: Task) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64[source]

Return an integer variable/expression storing the index of the allocated unary_resource.

Assumes that exactly one unary resource is allocated to a task. Only to be called when allocation_modelling == AllocationModelling.INTEGER.

Parameters:

task

Returns:

get_task_allocation_variable(task: Task) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64[source]

Return an integer variable/expression storing the index of the allocated unary_resource.

Assumes that exactly one unary resource is allocated to a task.

get_task_unary_resource_is_present_variable(task: Task, unary_resource: UnaryResource) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64[source]

Return a 0-1 variable/expression telling if the unary_resource is used for the task.

NB: sometimes the given resource is never to be used by a task and the variable has not been created. The convention is to return 0 in that case.

class discrete_optimization.generic_tasks_tools.solvers.cpsat.AllocationCpSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: OrtoolsCpSatSolver, AllocationCpSolver[Task, UnaryResource]

Base class for allocation cp-sat solvers using a binary modelling.

I.e. using 0-1 variables to model allocation status of each couple (task, unary_resource) This is a more general modelisation thant the integer one as it allows allocation of multiple resources.

add_allocation_changes_constraints(ref: AllocationSolution[Task, UnaryResource]) → list[Any][source]

Add and return constraints so that change variables reflect diff to ref.

add_constraint_nb_unary_resource_usages(sign: SignEnum, target: int, tasks: Iterable[Task] | None = None, unary_resources: Iterable[UnaryResource] | None = None) → list[Any][source]
add_constraint_on_nb_allocation_changes(ref: AllocationSolution[Task, UnaryResource], nb_changes: int, sign: SignEnum = SignEnum.LEQ) → list[Any][source]

Add contraint on maximal number of allocation changes from the given reference.

Parameters:

  • ref

  • nb_changes – maximal number of changes

Returns:

resulting constraints

add_constraint_on_task_unary_resource_allocation(task: Task, unary_resource: UnaryResource, used: bool) → list[Any][source]

Add constraint on allocation of given unary resource for the given task

Parameters:

  • task

  • unary_resource

  • used – if True, we enforce the allocation of unary_resource to task, else we prevent it

Returns:

resulting constraints

add_constraint_on_total_nb_usages(sign: SignEnum, target: int) → list[Any][source]
add_constraint_on_unary_resource_nb_usages(unary_resource: UnaryResource, sign: SignEnum, target: int) → list[Any][source]
allocation_changes_variables: dict[tuple[Task, UnaryResource], IntVar]

Variables tracking allocation changes from a given reference.

allocation_changes_variables_created = False

Flag telling whether ‘allocation changes variables’ have been created

at_most_one_unary_resource_per_task = False

Flag telling if the problem accept at most one unary_resource per task.

Default to False, ie several resources allowed per task.

create_allocation_changes_variables()[source]

Create variables necessary for constraint on nb of changes.

create_done_variables()[source]
create_used_variables()[source]
done_variables: dict[Task, IntVar]

Variables tracking whether a task has at least one unary resource allocated.

done_variables_created = False

Flag telling whether ‘done variables’ have been created

get_default_tasks_n_unary_resources(tasks: Iterable[Task] | None = None, unary_resources: Iterable[UnaryResource] | None = None) → tuple[Iterable[Task], Iterable[UnaryResource]][source]
get_nb_tasks_done_variable() → Any[source]

Construct and get the variable tracking number of tasks with at least a resource allocated.

Returns:

objective variable to minimize

get_nb_unary_resources_used_variable() → Any[source]

Construct and get the variable tracking number of tasks with at least a resource allocated.

Returns:

objective variable to minimize

abstractmethod get_task_unary_resource_is_present_variable(task: Task, unary_resource: UnaryResource) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64[source]

Return a 0-1 variable/expression telling if the unary_resource is used for the task.

NB: sometimes the given resource is never to be used by a task and the variable has not been created. The convention is to return 0 in that case.

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

Init cp model and reset stored variables if any.

property subset_tasks_of_interest: Iterable[Task]

Subset of tasks of interest used for the objective.

By default, all tasks.

property subset_unaryresources_allowed: Iterable[UnaryResource]

Unary resources allowed to solve the problem.

By default, all unary resources.

used_variables: dict[UnaryResource, IntVar]

Variables tracking whether a unary resource has been used at least once.

used_variables_created = False

Flag telling whether ‘used variables’ have been created

class discrete_optimization.generic_tasks_tools.solvers.cpsat.AllocationIntegerModellingCpSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: AllocationCpSatSolver[Task, UnaryResource]

Base class for allocation cp-sat solvers using an integer modelling.

I.e. using integer variables to model allocation of a task. This assumes that at most one unary_resource can be allocated to a task.

add_allocation_changes_constraints(ref: AllocationSolution[Task, UnaryResource]) → list[Any][source]

Add and return constraints so that change variables reflect diff to ref.

add_constraint_on_task_unary_resource_allocation(task: Task, unary_resource: UnaryResource, used: bool) → list[Any][source]

Add constraint on allocation of given unary resource for the given task

Parameters:

  • task

  • unary_resource

  • used – if True, we enforce the allocation of unary_resource to task, else we prevent it

Returns:

resulting constraints

create_is_present_variables() → None[source]
abstractmethod get_task_allocation_variable(task: Task) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64[source]

Return an integer variable/expression storing the index of the allocated unary_resource.

Assumes that exactly one unary resource is allocated to a task.

get_task_unary_resource_is_present_variable(task: Task, unary_resource: UnaryResource) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64[source]

Return a 0-1 variable/expression telling if the unary_resource is used for the task.

NB: sometimes the given resource is never to be used by a task and the variable has not been created. The convention is to return 0 in that case.

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

Init cp model and reset stored variables if any.

is_present_variables: dict[tuple[Task, UnaryResource], IntVar]
is_present_variables_created = False
class discrete_optimization.generic_tasks_tools.solvers.cpsat.AllocationModelling(*values)[source]

Bases: Enum

BINARY = 'binary'
INTEGER = 'integer'
class discrete_optimization.generic_tasks_tools.solvers.cpsat.AllocationSchedulingCpSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: CumulativeResourceSchedulingCpSatSolver[Task, CumulativeResource | UnaryResource], AllocationCpSatSolver[Task, UnaryResource], Generic[Task, UnaryResource, CumulativeResource]

get_resource_consumption_intervals(resource: CumulativeResource | UnaryResource) → list[tuple[IntervalVar, int]][source]

Get all intervals where a given resource is consumed by a task, and related consumption value.

Parameters:

resource

Returns: list of tuples (interval_var, consumption_value)

abstractmethod get_task_unary_resource_interval(task: Task, unary_resource: UnaryResource) → IntervalVar[source]

Get the interval variable corresponding to given task conditioned to allocation of the given unary resource.

The method may return an error (no variable existing) if self.problem.is_compatible_task_unary_resource(task=task, unary_resource=unary_resource) is false.

problem: AllocationSchedulingProblem[Task, UnaryResource, CumulativeResource]
class discrete_optimization.generic_tasks_tools.solvers.cpsat.CumulativeResourceSchedulingCpSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: RenewableResourceCpSatSolver[Task, Resource], MultimodeSchedulingCpSatSolver[Task], Generic[Task, Resource]

Base class for cpast solvers dealing with scheduling problems handling cumulative resources.

This class manages the creation of interval variables for each (task, mode) tuple, with If actually single mode (only 1 mode per task), it

get_resource_consumption_intervals(resource: Resource) → list[tuple[IntervalVar, int]][source]

Get all intervals where a given resource is consumed by a task, and related consumption value.

Parameters:

resource

Returns: list of tuples (interval_var, consumption_value)

problem: CumulativeResourceProblem[Task, Resource]
class discrete_optimization.generic_tasks_tools.solvers.cpsat.MultimodeCpSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: OrtoolsCpSatSolver, MultimodeCpSolver[Task]

add_constraint_on_task_mode(task: Task, mode: int) → list[Any][source]

Add constraint on task mode

The mode of task is fixed to mode.

Parameters:

  • task

  • mode

Returns:

resulting constraints

abstractmethod get_task_mode_is_present_variable(task: Task, mode: int) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64[source]

Retrieve the 0-1 variable/expression telling if the mode is used for the task.

Parameters:

  • task

  • mode

Returns:

class discrete_optimization.generic_tasks_tools.solvers.cpsat.MultimodeSchedulingCpSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SchedulingCpSatSolver[Task], MultimodeCpSatSolver[Task], Generic[Task]

Base class for cpsat solvers dealing with scheduling problems whose tasks durations depend only on mode.

Automatically managed creation of some variables - start - end - task-mode choice + only one to chosen constraint - duration - task intervals (constraint duration = end - start) - task-mode opt intervals

abstractmethod get_task_mode_interval(task: Task, mode: int) → IntervalVar[source]

Get the interval variable corresponding to given task and mode.

problem: MultimodeSchedulingProblem[Task]
class discrete_optimization.generic_tasks_tools.solvers.cpsat.RenewableResourceCpSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: SchedulingCpSatSolver[Task], Generic[Task, Resource]

create_renewable_resources_constraint(resource: Resource)[source]

Add the constraint for renewable resources to the cpsat model.

Constraint ensuring that the total demand on the given resource stay below its capacity.

abstractmethod get_resource_consumption_intervals(resource: Resource) → list[tuple[IntervalVar, int]][source]

Get all intervals where a given resource is consumed by a task, and related consumption value.

Parameters:

resource

Returns: list of tuples (interval_var, consumption_value)

problem: RenewableResourceProblem[Task, Resource]
class discrete_optimization.generic_tasks_tools.solvers.cpsat.SchedulingCpSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: OrtoolsCpSatSolver, SchedulingCpSolver[Task]

Base class for most ortools/cpsat solvers handling scheduling problems.

Allows to have common code.

add_constraint_chaining_tasks(task1: Task, task2: Task) → list[Any][source]

Add constraint chaining task1 with task2

task2 start == task1 end

Parameters:

  • task1

  • task2

Returns:

resulting constraints

add_constraint_on_task(task: Task, start_or_end: StartOrEnd, sign: SignEnum, time: int) → list[Any][source]

Add constraint on given task start or end

task start or end must compare to time according to sign

Parameters:

  • task

  • start_or_end

  • sign

  • time

Returns:

resulting constraints

constraints_on_makespan: list[Any] | None = None

Constraints on partial makespan so that it can be considered as the objective.

get_global_makespan_variable() → Any[source]

Construct and get the variable tracking the global makespan.

Default implementation uses get_subtasks_makespan_variable on last tasks. Beware: a further call to get_subtasks_makespan_variable with another subset of tasks can change the constraints on this variable and thus make it obsolete.

Returns:

objective variable to minimize

get_subtasks_makespan_variable(subtasks: Iterable[Task]) → Any[source]

Construct and get the variable tracking the makespan on a subset of tasks.

Beware: a further call to get_subtasks_makespan_variable with another subset of tasks can change the constraints on this variable and thus make it obsolete.

Parameters:

subtasks

Returns:

objective variable to minimize

get_subtasks_sum_end_time_variable(subtasks: Iterable[Task]) → Any[source]

Construct and get the variable tracking the sum of end times on a subset of tasks.

Parameters:

subtasks

Returns:

objective variable to minimize

get_subtasks_sum_start_time_variable(subtasks: Iterable[Task]) → Any[source]

Construct and get the variable tracking the sum of start times on a subset of tasks.

Parameters:

subtasks

Returns:

objective variable to minimize

abstractmethod get_task_start_or_end_variable(task: Task, start_or_end: StartOrEnd) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64[source]

Retrieve the variable storing the start or end time of given task.

Parameters:

  • task

  • start_or_end

Returns:

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

Init cp model and reset stored variables if any.

remove_constraints_on_objective() → None[source]
class discrete_optimization.generic_tasks_tools.solvers.cpsat.SinglemodeCpSatSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: MultimodeCpSatSolver[Task]

Cpsat solver mixin for single mode problems.

get_task_mode_is_present_variable(task: Task, mode: int) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64[source]

Retrieve the 0-1 variable/expression telling if the mode is used for the task.

Parameters:

  • task

  • mode

Returns:

problem: SinglemodeProblem[Task]
discrete_optimization.generic_tasks_tools.solvers.cpsat.is_a_trivial_zero(var: LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64) → bool[source]

Return whether the variable is actually a plain 0 integer.

For instance, tells if is_present variables are real variables or not to avoid including them in sum, max, …

discrete_optimization.generic_tasks_tools.solvers.optalcp_tasks_solver module

class discrete_optimization.generic_tasks_tools.solvers.optalcp_tasks_solver.AllocationOptalSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: OptalCpSolver, AllocationCpSolver[Task, UnaryResource]

Base class for allocation cp-sat solvers using a binary modelling. I.e. using 0-1 variables to model allocation status of each couple (task, unary_resource) This is a more general modelisation thant the integer one as it allows allocation of multiple resources.

add_allocation_changes_constraints(ref: AllocationSolution[Task, UnaryResource]) → list[Any][source]

Add and return constraints so that change variables reflect diff to ref.

add_constraint_nb_unary_resource_usages(sign: SignEnum, target: int, tasks: Iterable[Task] | None = None, unary_resources: Iterable[UnaryResource] | None = None) → list[Any][source]
add_constraint_on_nb_allocation_changes(ref: AllocationSolution[Task, UnaryResource], nb_changes: int, sign: SignEnum = SignEnum.LEQ) → list[Any][source]

Add contraint on maximal number of allocation changes from the given reference.

Parameters:

  • ref

  • nb_changes – maximal number of changes

Returns:

resulting constraints

add_constraint_on_task_unary_resource_allocation(task: Task, unary_resource: UnaryResource, used: bool) → list[Any][source]

Add constraint on allocation of given unary resource for the given task

Parameters:

  • task

  • unary_resource

  • used – if True, we enforce the allocation of unary_resource to task, else we prevent it

Returns:

resulting constraints

add_constraint_on_total_nb_usages(sign: SignEnum, target: int) → list[Any][source]
add_constraint_on_unary_resource_nb_usages(unary_resource: UnaryResource, sign: SignEnum, target: int) → list[Any][source]
allocation_changes_variables: dict[tuple[Task, UnaryResource], 'cp.IntExpr']

Variables tracking allocation changes from a given reference.

allocation_changes_variables_created = False

Flag telling whether ‘allocation changes variables’ have been created

at_most_one_unary_resource_per_task = False

Flag telling if the problem accept at most one unary_resource per task.

Default to False, ie several resources allowed per task.

create_allocation_changes_variables()[source]

Create variables necessary for constraint on nb of changes.

create_done_variables()[source]
create_used_variables()[source]
done_variables: dict[Task, cp.BoolExpr]

Variables tracking whether a task has at least one unary resource allocated.

done_variables_created = False

Flag telling whether ‘done variables’ have been created

get_default_tasks_n_unary_resources(tasks: Iterable[Task] | None = None, unary_resources: Iterable[UnaryResource] | None = None) → tuple[Iterable[Task], Iterable[UnaryResource]][source]
get_nb_tasks_done_variable() → Any[source]

Construct and get the variable tracking number of tasks with at least a resource allocated.

Returns:

objective variable to minimize

get_nb_unary_resources_used_variable() → Any[source]

Construct and get the variable tracking number of tasks with at least a resource allocated.

Returns:

objective variable to minimize

abstractmethod get_task_unary_resource_is_present_variable(task: Task, unary_resource: UnaryResource) → cp.BoolExpr[source]

Return a 0-1 variable/expression telling if the unary_resource is used for the task.

NB: sometimes the given resource is never to be used by a task and the variable has not been created. The convention is to return 0 in that case.

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

Init cp model and reset stored variables if any.

property subset_tasks_of_interest: Iterable[Task]

Subset of tasks of interest used for the objective.

By default, all tasks.

property subset_unaryresources_allowed: Iterable[UnaryResource]

Unary resources allowed to solve the problem.

By default, all unary resources.

used_variables: dict[UnaryResource, cp.BoolVar]

Variables tracking whether a unary resource has been used at least once.

used_variables_created = False

Flag telling whether ‘used variables’ have been created

class discrete_optimization.generic_tasks_tools.solvers.optalcp_tasks_solver.MultimodeOptalSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: OptalCpSolver, MultimodeCpSolver[Task]

add_constraint_on_task_mode(task: Task, mode: int) → list[Any][source]

Add constraint on task mode

The mode of task is fixed to mode.

Parameters:

  • task

  • mode

Returns:

resulting constraints

abstractmethod get_task_mode_is_present_variable(task: Task, mode: int) → cp.BoolExpr[source]

Retrieve the 0-1 variable/expression telling if the mode is used for the task.

Parameters:

  • task

  • mode

Returns:

class discrete_optimization.generic_tasks_tools.solvers.optalcp_tasks_solver.SchedulingOptalSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)[source]

Bases: OptalCpSolver, SchedulingCpSolver[Task]

add_constraint_chaining_tasks(task1: Task, task2: Task) → list[Any][source]

Add constraint chaining task1 with task2

task2 start == task1 end

Parameters:

  • task1

  • task2

Returns:

resulting constraints

add_constraint_on_task(task: Task, start_or_end: StartOrEnd, sign: SignEnum, time: int) → list['cp.BoolExpr'][source]

Add constraint on given task start or end

task start or end must compare to time according to sign

Parameters:

  • task

  • start_or_end

  • sign

  • time

Returns:

resulting constraints

get_subtasks_makespan_variable(subtasks: Iterable[Task]) → Any[source]

Construct and get the variable tracking the makespan on a subset of tasks.

Beware: a further call to get_subtasks_makespan_variable with another subset of tasks can change the constraints on this variable and thus make it obsolete.

Parameters:

subtasks

Returns:

objective variable to minimize

get_subtasks_sum_end_time_variable(subtasks: Iterable[Task]) → Any[source]

Construct and get the variable tracking the sum of end times on a subset of tasks.

Parameters:

subtasks

Returns:

objective variable to minimize

get_subtasks_sum_start_time_variable(subtasks: Iterable[Task]) → Any[source]

Construct and get the variable tracking the sum of start times on a subset of tasks.

Parameters:

subtasks

Returns:

objective variable to minimize

abstractmethod get_task_interval_variable(task: Task) → cp.IntervalVar[source]

Retrieve the interval variable of given task.

get_task_start_or_end_variable(task: Task, start_or_end: StartOrEnd) → cp.IntExpr[source]

Retrieve the variable storing the start or end time of given task.

Parameters:

  • task

  • start_or_end

Returns:

Module contents