- CS :~ ConstrSpec
- Add a constraint to a constraint set
- cs_all(+CS, -Cstr)
- Get all constraints in the constraint set
- cs_all_violated(+CS, -Cstr)
- Get all violated constraints in the constraint set
- cs_all_worst(+CS, -Cstr)
- Get all worst violated constraints in the constraint set
- cs_clear_all(+CS)
- Clean up the constraint set completely
- cs_clear_satisfied(+CS)
- Remove the satisfied constraints from the constraint set
- cs_create(-CS, ++Options)
- Create an empty constraint set
- cs_current_violations(+CS, -Vio)
- Get the current violatedness of the constraint set
- cs_random_violated(+CS, -Cstr)
- Get random violated constraints in the constraint set
- cs_random_worst(+CS, -Cstr)
- Get random worst violated constraint from the constraint set
- cs_violations(+CS, -Vio)
- Get a tentative variable reflecting the violatedness of the constraint set
- get_changeable_value(?, ?)
- No description available
- has_tent_value(?X)
- X has a tentative value (succeeds also for X nonvar)
- print_tentative(?, ?)
- No description available
- random_element(+Values, -X)
- Pick random element from range or collection
- random_sample(+Values, +SampleSize, -X)
- Nondeterministically pick SampleSize random elements
- register_for_notification(?X, +Tag, ?Receiver)
- Constraint implementation: register for notification
- suspend_on_change(?, ?)
- No description available
- tent_fix(?X)
- Instantiate X to its tentative value
- tent_get(?X, -TV)
- Get X's tentative value
- ++ImplSpec tent_implements ++ConsSpec
- Associate a constraint with a tentative value implementation
- ?Result tent_is +Expr
- Maintain tentative result of arithmetic expression
- tent_minimize_random(+MoveGenerator, ?Violations, -MoveId)
- Find a move that minimizes violations
- tent_set(?X, +TV)
- Set X's tentative value to TV
- tent_set_all(?Vars, +TV)
- Set the tentative values of all variables within Vars to the same value TV
- tent_set_attr(?, ?)
- No description available
- tent_set_random(?Vars, ++Values)
- Set the tentative value of each variable within Vars to a random value from the given Range
- tent_trace_array(+Stream, +Name, +ArrayList)
- Simple tracing facility for several variables
- var_get_violations(?X, -Violations)
- Get X's violation count
- var_inc_violations(?X, +Delta)
- Increment X's violation count by Delta
- vs_all(+VS, -Vars)
- Retrieve all variables from a varset
- vs_all_violated(+VS, -Vars)
- Retrieve all violated variables from a varset
- vs_all_violated_index(+VS, -Is)
- Retrieve all violated variable indices from a varset
- vs_all_worst(+VS, -Vars)
- Retrieve all worst violated variables from a varset
- vs_all_worst_index(+VS, -Is)
- Retrieve all worst violated variable indices from a varset
- vs_create(?Vars, -VS)
- Construct a varset from the variables in Vars
- vs_element(+VS, +I, -X)
- Get an element of a varset by index
- vs_member(+VS, -X)
- Succeed for each element of a varset
- vs_random(+VS, -X)
- Retrieve a random variable from a varset
- vs_random_index(+VS, -I)
- Retrieve a random variable index from a varset
- vs_random_violated(+VS, -X)
- Retrieve a random violated variable from a varset
- vs_random_violated_index(+VS, -I)
- Retrieve a random violated variable index from a varset
- vs_random_worst(+VS, -X)
- Retrieve a worst violated variable from a varset
- vs_random_worst_index(+VS, -I)
- Retrieve a worst violated variable index from a varset
- vs_size(+VS, -N)
- Get the size of a varset
- vs_violated(+VS, -X)
- Succeeds for each violated variable from a varset
- vs_violated_index(+VS, -I)
- Succeeds for each violated variable index from a varset
- vs_worst(+VS, -X)
- Succeeds for each worst violated variable from a varset
- vs_worst_index(+VS, -I)
- Succeeds for each worst violated variable index from a varset
- struct monitored_constraint(alias, violations, suspensions)
- No description available
- export op(700, xfx, tent_get)
- export op(700, xfx, tent_set)
- export op(700, xfx, tent_implements)
- export op(800, xfx, alias)
- export op(900, xfx, :~)
- export op(700, xfx, tent_is)
This is a library for implementing Local Search algorithms. It is intended as a successor for library(repair).
This library provides the following concepts and primitives:
A tentative value (TV) can be an atomic term or a (possibly nonground) compound term. It is a conscious design choice not to allow variable tentative values. A tentative value can be attached to a variable, and freely changed. It is not possible to remove a variable's tentative value once it has had one, it can only be replaced by a different one. The change of tentative value can be used as a trigger condition for waking delayed goals.
Instantiating a tentative variable to a value V is equivalent to first setting/changing its tentative value to V, and then instantiating to V.
When two tentative variables get unified, one of them acquires the tentative value of the other (which one is undefined). Such unifications do not fit well with the concepts of this library and are best avoided.
Variables with tentative value are printed in the following format:
X{99 -> 7}where the first number (99) is the tentative value, and the second number (7) is the variable's violation count.
The primitives related to tentative values are:
All these operations are undone on backtracking.
- has_tent_value(?X)
- X has a tentative (or definitive) value
- tent_get(?X, -Val)
- get tentative value
- tent_set(?X, -Val)
- set tentative value
- tent_set_all(?Xs, +Val)
- set multiple identical tentative values
- tent_set_random(?Xs, +Range)
- set multiple random tentative values
- tent_fix(?X)
- instantiate to tentative value
- var_get_violations(?X, -Violations)
- get the number of violations the variable is currently involved in
- var_inc_violations(?Var, +Delta)
- add Delta to Var's violation counter
Tentative variables can be grouped into indexed sets, from which elements (or their index) can then be selected according to different criteria. The corresponding predicates are:
- vs_create(+Vars, -VarSet)
- construct a variable set from the variables in Vars
- vs_all(+VS, -Xs)
- get a list of all the variables in the set
- vs_element(+VS, +I, -X)
- get a particular variable from the set
- vs_member(+VS, -X)
- enumerate all variables from the set
- vs_random(+VS, -X), vs_random_index(+VS, -I)
- pick a random variable from the set
- vs_random_violated(+VS, -X), vs_random_violated_index(+VS, -I)
- pick a random violated variable from the set
- vs_all_violated(+VS, -Xs), vs_all_violated_index(+VS, -Is)
- get a list of all violated variables from the set
- vs_violated(+VS, -X), vs_violated_index(+VS, -I)
- enumerate all violated variables from the set
- vs_random_worst(+VarSet, -X), vs_random_worst_index(+VarSet, -I)
- pick a random variable with maximum violations from the set
- vs_all_worst(+VS, -Xs), vs_all_worst_index(+VS, -Is)
- get a list of all the maximally violated variables from the set
- vs_worst(+VS, -X), vs_worst_index(+VS, -I)
- enumerate all maximally violated variables from the set
To monitor a constraint's tentative violatedness, it must be added to a constraint set. The predicates to create, add and remove constraints from a constraint set are:
The total violation count of all the constraints in the set can be accessed through the following predicates:
- CS :~ C
- add a constraint to the constraint set
- cs_create(-CS, +Options)
- create an empty constraint set
- cs_clear_all(+CS)
- remove all constraints from the constraint set
- cs_clear_satisfied(+CS)
- remove all satisfied constraints from the constraint set
Constraints from the constraint set can be selected according to different criteria through the following predicates:
- cs_violations(+CS, -VioVar)
- get a tentative variable reflecting violatedness of the constraint set
- cs_current_violations(+CS, -Vio)
- get the current violatedness of the constraint set (integer)
- cs_random_worst(+CS, -C)
- get a random worst violated constraint from the constraint set
- cs_all_worst(+CS, -Cs)
- get all worst violated constraints from the constraint set
- cs_all_violated(+CS, -Cs)
- get all violated constraints from the constraint set
- cs_random_violated(+CS, -Cs)
- get a random violated constraint from the constraint set
- cs_all(+CS, -Cs)
- get all constraints from the constraint set
There is currently one primitive to maintain arithmetic invariants:
- -Res tent_is +Expr
- the tentative value of Res is the tentative result of Expr
The following primitives support the implementation of the actual Local Search routines:
- tent_minimize_random(MoveGenerator, Violations, MoveId)
- Find a best neighbour using MoveGenerator
- random_element(+Range, -Value)
- Pick a random element from Range
- random_sample(+Range, +N, -Value)
- Succeed N times with random values from Range
A simple tracing facility is provided via
Also, the Visualisation Tools can be used with this library, by creating viewables with type changeable(tentative,Type).
- tent_trace_array(+Stream, +Name, +ArrayList)
- Print a message whenever a tentative value changes
Constraints are implemented by an implementation predicate. A constraint is linked to its implementation predicate by a tent_implements/2 declaration, e.g.
:- alldifferent_t/2 tent_implements alldifferent/1.The implementation predicate must have one more argument than the constraint itself. The extra (last) argument is a structure
struct(monitored_constraint( alias, % the constraint goal (or equivalent term) violations, % a tentative variable suspensions % suspensions of the monitoring goals )The implementation predicate is supposed to update the constraint's violation TV plus the violation counters of the variables that occur in the constraint. It should do this by suspending on the variable's tent_chg list, and by registering for exact change notification via:
This messaging facility is based upon the primitive in lib(notify_ports).
- register_for_notification(?TV, +Tag, ?Receiver)
- register to receive messages about changes to TV's tentative value
Actual constraint implementations can be found in the library lib(tentative_constraints).
See lib(tentative_constraints).