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_constraint_on_nb_allocation_changes(ref: AllocationSolution[Task, UnaryResource], nb_changes: int) → 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

allocation_modelling: AllocationModelling
abstract 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.

abstract 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_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) → 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_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

abstract 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.

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_constraint_on_nb_allocation_changes(ref: AllocationSolution[Task, UnaryResource], nb_changes: int) → 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

create_is_present_variables() → None[source]
abstract 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.

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

Bases: Enum

An enumeration.

BINARY = 'binary'
INTEGER = 'integer'
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

abstract 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.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_makespan_var() → IntVar[source]

Get the makespan variable used to track global makespan.

get_subtasks_makespan_var() → IntVar[source]

Get the makespan variable used to track subtasks makespan.

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

abstract 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]
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, …

Module contents