discrete_optimization.generic_tasks_tools package

Subpackages

• discrete_optimization.generic_tasks_tools.solvers package
  • Subpackages
    • discrete_optimization.generic_tasks_tools.solvers.lns_cp package
      • Submodules
      • discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_extractor module
      • discrete_optimization.generic_tasks_tools.solvers.lns_cp.constraint_handler module
      • discrete_optimization.generic_tasks_tools.solvers.lns_cp.neighbor_tools module
      • Module contents
  • Submodules
  • discrete_optimization.generic_tasks_tools.solvers.cpsat module
    • AllocationBinaryOrIntegerModellingCpSatSolver
      • AllocationBinaryOrIntegerModellingCpSatSolver.add_constraint_on_nb_allocation_changes()
      • AllocationBinaryOrIntegerModellingCpSatSolver.add_constraint_on_task_unary_resource_allocation()
      • AllocationBinaryOrIntegerModellingCpSatSolver.allocation_modelling
      • AllocationBinaryOrIntegerModellingCpSatSolver.get_binary_allocation_variable()
      • AllocationBinaryOrIntegerModellingCpSatSolver.get_integer_allocation_variable()
      • AllocationBinaryOrIntegerModellingCpSatSolver.get_task_allocation_variable()
      • AllocationBinaryOrIntegerModellingCpSatSolver.get_task_unary_resource_is_present_variable()
    • AllocationCpSatSolver
      • AllocationCpSatSolver.add_constraint_nb_unary_resource_usages()
      • AllocationCpSatSolver.add_constraint_on_nb_allocation_changes()
      • AllocationCpSatSolver.add_constraint_on_task_unary_resource_allocation()
      • AllocationCpSatSolver.add_constraint_on_total_nb_usages()
      • AllocationCpSatSolver.add_constraint_on_unary_resource_nb_usages()
      • AllocationCpSatSolver.allocation_changes_variables
      • AllocationCpSatSolver.allocation_changes_variables_created
      • AllocationCpSatSolver.at_most_one_unary_resource_per_task
      • AllocationCpSatSolver.create_allocation_changes_variables()
      • AllocationCpSatSolver.create_done_variables()
      • AllocationCpSatSolver.create_used_variables()
      • AllocationCpSatSolver.done_variables
      • AllocationCpSatSolver.done_variables_created
      • AllocationCpSatSolver.get_nb_tasks_done_variable()
      • AllocationCpSatSolver.get_nb_unary_resources_used_variable()
      • AllocationCpSatSolver.get_task_unary_resource_is_present_variable()
      • AllocationCpSatSolver.init_model()
      • AllocationCpSatSolver.used_variables
      • AllocationCpSatSolver.used_variables_created
    • AllocationIntegerModellingCpSatSolver
      • AllocationIntegerModellingCpSatSolver.add_constraint_on_nb_allocation_changes()
      • AllocationIntegerModellingCpSatSolver.add_constraint_on_task_unary_resource_allocation()
      • AllocationIntegerModellingCpSatSolver.create_is_present_variables()
      • AllocationIntegerModellingCpSatSolver.get_task_allocation_variable()
      • AllocationIntegerModellingCpSatSolver.get_task_unary_resource_is_present_variable()
      • AllocationIntegerModellingCpSatSolver.is_present_variables
      • AllocationIntegerModellingCpSatSolver.is_present_variables_created
    • AllocationModelling
      • AllocationModelling.BINARY
      • AllocationModelling.INTEGER
    • MultimodeCpSatSolver
      • MultimodeCpSatSolver.add_constraint_on_task_mode()
      • MultimodeCpSatSolver.get_task_mode_is_present_variable()
    • SchedulingCpSatSolver
      • SchedulingCpSatSolver.add_constraint_chaining_tasks()
      • SchedulingCpSatSolver.add_constraint_on_task()
      • SchedulingCpSatSolver.constraints_on_makespan
      • SchedulingCpSatSolver.get_global_makespan_variable()
      • SchedulingCpSatSolver.get_makespan_var()
      • SchedulingCpSatSolver.get_subtasks_makespan_var()
      • SchedulingCpSatSolver.get_subtasks_makespan_variable()
      • SchedulingCpSatSolver.get_subtasks_sum_end_time_variable()
      • SchedulingCpSatSolver.get_subtasks_sum_start_time_variable()
      • SchedulingCpSatSolver.get_task_start_or_end_variable()
      • SchedulingCpSatSolver.init_model()
      • SchedulingCpSatSolver.remove_constraints_on_objective()
    • is_a_trivial_zero()
  • Module contents

Submodules

discrete_optimization.generic_tasks_tools.allocation module

class discrete_optimization.generic_tasks_tools.allocation.AllocationCpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: TasksCpSolver[Task], Generic[Task, UnaryResource]

Base class for solver managing constraints on allocation.

abstract add_constraint_on_nb_allocation_changes(ref: AllocationSolution[Task, UnaryResource], nb_changes: int) → list[Any]

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

Parameters:

• ref

• nb_changes – maximal number of changes

Returns:

resulting constraints

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

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

abstract add_constraint_on_total_nb_usages(sign: SignEnum, target: int) → list[Any]

abstract add_constraint_on_unary_resource_nb_usages(unary_resource: UnaryResource, sign: SignEnum, target: int) → list[Any]

add_constraint_same_allocation_as_ref(ref: AllocationSolution[Task, UnaryResource], tasks: Iterable[Task] | None = None, unary_resources: Iterable[UnaryResource] | None = None) → list[Any]

Add constraint to keep same allocation as the reference for the given tasks and unary resources subsets.

Parameters:

• ref

• tasks

• unary_resources

Returns:

resulting constraints

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

abstract get_nb_tasks_done_variable() → Any

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

Returns:

objective variable to minimize

abstract get_nb_unary_resources_used_variable() → Any

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

Returns:

objective variable to minimize

problem: AllocationProblem[Task, UnaryResource]

class discrete_optimization.generic_tasks_tools.allocation.AllocationProblem

Bases: TasksProblem[Task], Generic[Task, UnaryResource]

Base class for allocation problems.

An allocation problems consist in allocating resources to tasks.

get_index_from_unary_resource(unary_resource: UnaryResource) → int

get_unary_resource_from_index(i: int) → UnaryResource

is_compatible_task_unary_resource(task: Task, unary_resource: UnaryResource) → bool

Should return False if the unary_resource can never be allocated to task.

This is only a hint used to reduce the number of variables or constraints generated.

Default to True, to be overriden in subclasses.

unary_resources_list: list[UnaryResource]

Available unary resources.

It can correspond to employees (rcpsp-multiskill), teams (workforce-scheduling), or a mix of several types.

class discrete_optimization.generic_tasks_tools.allocation.AllocationSolution

Bases: TasksSolution[Task], Generic[Task, UnaryResource]

Class inherited by a solution for allocation problems.

check_same_allocation_as_ref(ref: AllocationSolution[Task, UnaryResource], tasks: Iterable[Task] | None = None, unary_resources: Iterable[UnaryResource] | None = None) → bool

compute_nb_allocation_changes(ref: AllocationSolution[Task, UnaryResource]) → int

compute_nb_tasks_done() → int

Compute number of tasks with at least a resource allocated.

compute_nb_unary_resource_usages(tasks: Iterable[Task] | None = None, unary_resources: Iterable[UnaryResource] | None = None)

compute_nb_unary_resources_used() → int

Compute number of unary resources allocated to at least one task.

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

abstract is_allocated(task: Task, unary_resource: UnaryResource) → bool

Return the usage of the unary resource for the given task.

Parameters:

• task

• unary_resource

Returns:

problem: AllocationProblem[Task, UnaryResource]

discrete_optimization.generic_tasks_tools.allocation.get_default_tasks_n_unary_resources(problem: AllocationProblem, tasks: Iterable[Task] | None = None, unary_resources: Iterable[UnaryResource] | None = None) → tuple[Iterable[Task], Iterable[UnaryResource]]

discrete_optimization.generic_tasks_tools.base module

class discrete_optimization.generic_tasks_tools.base.TasksCpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: CpSolver, Generic[Task]

Base class for cp solver handling tasks problems.

problem: TasksProblem[Task]

class discrete_optimization.generic_tasks_tools.base.TasksProblem

Bases: Problem, Generic[Task]

Base class for scheduling/allocation problems.

tasks_list: list[Task]

List of all tasks to schedule or allocate to.

class discrete_optimization.generic_tasks_tools.base.TasksSolution

Bases: ABC, Solution, Generic[Task]

Base class for sheduling/allocation solutions.

problem: TasksProblem[Task]

discrete_optimization.generic_tasks_tools.enums module

class discrete_optimization.generic_tasks_tools.enums.StartOrEnd(value)

Bases: Enum

An enumeration.

END = 'end'

START = 'start'

discrete_optimization.generic_tasks_tools.multimode module

class discrete_optimization.generic_tasks_tools.multimode.MultimodeCpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: TasksCpSolver[Task]

Class inherited by a solver managing constraints on tasks modes.

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

Add constraint on task mode

The mode of task is fixed to mode.

Parameters:

• task

• mode

Returns:

resulting constraints

problem: MultimodeProblem[Task]

class discrete_optimization.generic_tasks_tools.multimode.MultimodeProblem

Bases: TasksProblem[Task]

Class inherited by a solution exposing tasks modes.

abstract get_task_modes(task: Task) → set[int]

Retrieve mode found for given task.

Parameters:

task

Returns:

property is_multimode

property max_number_of_mode

class discrete_optimization.generic_tasks_tools.multimode.MultimodeSolution

Bases: TasksSolution[Task]

Class inherited by a solution exposing tasks modes.

abstract get_mode(task: Task) → int

Retrieve mode found for given task.

Parameters:

task

Returns:

problem: MultimodeProblem[Task]

discrete_optimization.generic_tasks_tools.precedence module

class discrete_optimization.generic_tasks_tools.precedence.PrecedenceProblem

Bases: TasksProblem[HashableTask]

Problem with precedence constraints on tasks.

abstract get_precedence_constraints() → dict[HashableTask, Iterable[HashableTask]]

Map each task to the tasks that need to be performed after it.

get_precedence_graph() → Graph

discrete_optimization.generic_tasks_tools.scheduling module

class discrete_optimization.generic_tasks_tools.scheduling.SchedulingCpSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: TasksCpSolver[Task]

Base class for cp solvers handling scheduling problems.

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

Add constraint chaining task1 with task2

task2 start == task1 end

Parameters:

• task1

• task2

Returns:

resulting constraints

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

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_global_makespan_variable() → Any

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_lower_bound() → int

Get a lower bound on global makespan.

Can be overriden in solvers wanting to specify it in init_model() for instance.

get_makespan_upper_bound() → int

Get a upper bound on global makespan.

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

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

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

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

Parameters:

subtasks

Returns:

objective variable to minimize

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

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

Parameters:

subtasks

Returns:

objective variable to minimize

problem: SchedulingProblem[Task]

class discrete_optimization.generic_tasks_tools.scheduling.SchedulingProblem

Bases: TasksProblem[Task]

Base class for scheduling problems.

A scheduling problems is about finding start and end times to tasks.

get_last_tasks() → list[Task]

Get a sublist of tasks that are candidate to be the last one scheduled.

Default to all tasks.

get_makespan_lower_bound() → int

Get a lower bound on global makespan.

Default to 0. But can be overriden for problems with more information.

abstract get_makespan_upper_bound() → int

Get a upper bound on global makespan.

class discrete_optimization.generic_tasks_tools.scheduling.SchedulingSolution

Bases: TasksSolution[Task]

Base class for solution to scheduling problems.

constraint_chaining_tasks_satisfied(task1: Task, task2: Task) → bool

constraint_on_task_satisfied(task: Task, start_or_end: StartOrEnd, sign: SignEnum, time: int) → bool

abstract get_end_time(task: Task) → int

get_max_end_time() → int

abstract get_start_time(task: Task) → int

problem: SchedulingProblem[Task]

Module contents