Heuristics

NUCS provides heuristics for selecting a variable and for selecting a value (more generally, reducing its domain):

Heuristics for selecting a variable

NUCS provides the following functions for selecting a variable

nucs.heuristics.critical_resource_var_heuristic.critical_resource_var_heuristic(...) → int[source]

Chooses a task to branch on for disjunctive (unary resource) scheduling problems such as the job-shop.

Each decision variable is the start time of a task; params[v] carries (resource, duration) of that task. Rather than picking a globally smallest domain – which hops from one resource to another – this heuristic focuses branching on a single critical resource until its tasks are sequenced, mirroring the “keep the critical machine until its tasks are ordered” strategy: the search stays on one resource so the disjunctive propagator can sequence it, before moving on.

The critical resource is the one (with an unbound task) of smallest slack max(lct) - min(est) - load – the least free time, hence the most likely to fail – breaking ties on the tightest start window. Within it the tightest unbound task is selected (smallest window, then smallest earliest start), to be split low.

Parameters:

  • decision_variables (NDArray) – the decision variables, the start times of the tasks

  • domains_stk (NDArray) – the stack of domains

  • top (int) – the index of the top of the stacks

  • params (NDArray) – a two-dimensional array, params[v] is (resource, duration) of task v

Returns:

the variable, or -1 when every resource is sequenced (all start times bound)

Return type:

int

nucs.heuristics.first_not_instantiated_var_heuristic.first_not_instantiated_var_heuristic(...) → int[source]

Chooses the first non-instantiated variable.

Parameters:

  • decision_variables (NDArray) – the decision variables

  • domains_stk (NDArray) – the stack of domains

  • top (int) – the index of the top of the stacks

  • params (NDArray) – a two-dimensional parameter array, unused here

Returns:

the variable

Return type:

int

nucs.heuristics.greatest_domain_var_heuristic.greatest_domain_var_heuristic(...) → int[source]

Chooses the first variable which is not instantiated with the greatest domain.

Parameters:

  • decision_variables (NDArray) – the decision variables

  • domains_stk (NDArray) – the stack of domains

  • top (int) – the index of the top of the stacks

  • params (NDArray) – a two-dimensional parameter array, unused here

Returns:

the variable

Return type:

int

nucs.heuristics.largest_maximal_value_var_heuristic.largest_maximal_value_var_heuristic(...) → int[source]

Chooses the first variable which is not instantiated with the largest maximal value.

Parameters:

  • decision_variables (NDArray) – the decision variables

  • domains_stk (NDArray) – the stack of domains

  • top (int) – the index of the top of the stacks

  • params (NDArray) – a two-dimensional parameter array, unused here

Returns:

the variable

Return type:

int

nucs.heuristics.max_regret_var_heuristic.max_regret_var_heuristic(...) → int[source]

Chooses the variable with the maximal regret (difference between the best and second-best value).

Parameters:

  • decision_variables (NDArray) – the decision variables

  • domains_stk (NDArray) – the stack of domains

  • top (int) – the index of the top of the stacks

  • params (NDArray) – a two-dimensional (first dimension corresponds to variables, second to values) costs array

Returns:

the variable

Return type:

int

nucs.heuristics.min_earliest_start_var_heuristic.min_earliest_start_var_heuristic(...) → int[source]

Chooses the unbound task with the smallest earliest start time, the selection rule of the Set Times search.

Each decision variable is the start time of a task, so its domain minimum is the task’s earliest start and its maximum the latest start. This heuristic returns the unbound task that can start soonest, ties broken on the smallest latest start (the most urgent). Paired with the min_value domain heuristic – whose two branches “bind the start to its earliest value” and “forbid that value” are exactly Set Times’ schedule and postpone decisions – it realizes the Set Times scheme: repeatedly commit the soonest-startable task to its earliest time, or postpone it and let the disjunctive propagator push its earliest start to the next feasible point.

Parameters:

  • decision_variables (NDArray) – the decision variables, the start times of the tasks

  • domains_stk (NDArray) – the stack of domains

  • top (int) – the index of the top of the stacks

  • params (NDArray) – a two-dimensional parameter array, unused here

Returns:

the variable, or -1 when every task is bound

Return type:

int

nucs.heuristics.smallest_domain_var_heuristic.smallest_domain_var_heuristic(...) → int[source]

Chooses the first variable which is not instantiated with the smallest domain.

Parameters:

  • decision_variables (NDArray) – the decision variables

  • domains_stk (NDArray) – the stack of domains

  • top (int) – the index of the top of the stacks

  • params (NDArray) – a two-dimensional parameter array, unused here

Returns:

the variable

Return type:

int

nucs.heuristics.smallest_minimal_value_var_heuristic.smallest_minimal_value_var_heuristic(...) → int[source]

Chooses the first variable which is not instantiated with the smallest minimal value.

Parameters:

  • decision_variables (NDArray) – the decision variables

  • domains_stk (NDArray) – the stack of domains

  • top (int) – the index of the top of the stacks

  • params (NDArray) – a two-dimensional parameter array, unused here

Returns:

the variable

Return type:

int

Heuristics for reducing the chosen domain

NUCS provides the following functions for reducing a domain.

nucs.heuristics.max_value_dom_heuristic.max_value_dom_heuristic(...) → int[source]

Chooses the max value of the domain.

Parameters:

  • domains_stk (NDArray) – the stack of domains

  • domain_update_stk (NDArray) – the stack of domain updates

  • stks_top (NDArray) – the index of the top of the stacks as a Numpy array

  • variable (int) – the variable

  • params (NDArray) – a two-dimensional parameter array, unused here

Returns:

the events

Return type:

int

nucs.heuristics.mid_value_dom_heuristic.mid_value_dom_heuristic(...) → int[source]

Chooses the middle value of the domain.

Parameters:

  • domains_stk (NDArray) – the stack of domains

  • domain_update_stk (NDArray) – the stack of domain updates

  • stks_top (NDArray) – the index of the top of the stacks as a Numpy array

  • variable (int) – the variable

  • params (NDArray) – a two-dimensional parameter array, unused here

Returns:

the events

Return type:

int

nucs.heuristics.min_cost_dom_heuristic.min_cost_dom_heuristic(...) → int[source]

Chooses the value that minimizes the cost.

Parameters:

  • domains_stk (NDArray) – the stack of domains

  • domain_update_stk (NDArray) – the stack of domain updates

  • stks_top (NDArray) – the index of the top of the stacks as a Numpy array

  • variable (int) – the variable

  • params (NDArray) – a two-dimensional (first dimension corresponds to variables, second to values) cost array

Returns:

the events

Return type:

int

nucs.heuristics.min_value_dom_heuristic.min_value_dom_heuristic(...) → int[source]

Chooses the min value of the domain.

Parameters:

  • domains_stk (NDArray) – the stack of domains

  • domain_update_stk (NDArray) – the stack of domain updates

  • stks_top (NDArray) – the index of the top of the stacks as a Numpy array

  • variable (int) – the variable

  • params (NDArray) – a two-dimensional parameter array, unused here

Returns:

the events

Return type:

int

nucs.heuristics.split_low_dom_heuristic.split_low_dom_heuristic(...) → int[source]

Chooses the first half of the domain.

Parameters:

  • domains_stk (NDArray) – the stack of domains

  • domain_update_stk (NDArray) – the stack of domain updates

  • stks_top (NDArray) – the index of the top of the stacks as a Numpy array

  • variable (int) – the variable

  • params (NDArray) – a two-dimensional parameter array, unused here

Returns:

the events

Return type:

int

nucs.heuristics.split_high_dom_heuristic.split_high_dom_heuristic(...) → int[source]

Chooses the second half of the domain.

Parameters:

  • domains_stk (NDArray) – the stack of domains

  • domain_update_stk (NDArray) – the stack of domain updates

  • stks_top (NDArray) – the index of the top of the stacks as a Numpy array

  • variable (int) – the variable

  • params (NDArray) – a two-dimensional parameter array, unused here

Returns:

the events

Return type:

int