discrete_optimization.generic_tasks_tools.solvers package

Subpackages

Submodules

discrete_optimization.generic_tasks_tools.solvers.cpm module

CPM to compute lower/uppe bound on start/end of tasks

class discrete_optimization.generic_tasks_tools.solvers.cpm.Cpm(problem: GenericSchedulingProblem[Task, UnaryResource, Skill, NonSkillCumulativeResource, NonRenewableResource], horizon: int | None = None)[source]

Bases: Generic[Task, UnaryResource, CumulativeResource, NonRenewableResource]

Propagator of bounds trough precedence graph according to minimum duration of each task.

For that we use: - multimode-scheduling: we know all possible durations - precedence: we use the precedence constraints

We first do a forward pass on all tasks in precedence graph for lower bounds and then a backward pass for upper bounds.

We start from lower bound 0 and upper bound horizon (problem horizon can be overriden).

This differs from classic CPM as we know that other non-precedence constraints can occur so that we cannot assume end lower_bounds = end upper bound for sink tasks. So sink tasks end upper bound will be set to horizon instead.

For each task, we take best of propagated bound and existing problem bound on start/end (via problem.get_task_start_or_end_tighter_lower_bound() and problem.get_task_start_or_end_tighter_upper_bound()).

horizon

if set, override problem.get_makespan_upper_bound().

compute_task_bounds() → None[source]

Compute task bounds by forxard/backward propagation through precedence graph

Returns:

get_a_critical_path() → list[Task][source]

Compute a critical path.

It takes into account no other constraints that precedence constraints. It starts from a task without predecessor to a task without successor.

Returns:

get_critical_subgraph() → DiGraph[source]

Compute critical subgraph.

It includes all critical nodes.

Returns:

a subgraph view of precedence graph self.graph_nx (so beware that attributes are shared with original graph)

get_task_bounds() → dict[Task, tuple[int, int, int, int]][source]

Return computed bounds on task start and end.

Returns:

start_lower_bound, end_lower_bound, start_upper_bound, end_upper_bound

class discrete_optimization.generic_tasks_tools.solvers.cpm.Taskbounds(start_lower_bound: 'Optional[int]' = None, end_lower_bound: 'Optional[int]' = None, start_upper_bound: 'Optional[int]' = None, end_upper_bound: 'Optional[int]' = None)[source]

Bases: object

end_lower_bound: int | None = None
end_upper_bound: int | None = None
start_lower_bound: int | None = None
start_upper_bound: int | None = None

discrete_optimization.generic_tasks_tools.solvers.utils module

discrete_optimization.generic_tasks_tools.solvers.utils.is_a_trivial_zero(var: Any) → bool[source]

Return whether the (cpsat, optalcp, …) 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