[ Reference Manual | Alphabetic Index ]

library(tentative)

A framework for Local Search based on tentative values   [more]

Predicates

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, -Vars)
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, -Vars)
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, -Var)
Retrieve a random variable from a varset
vs_random_index(+VS, -Var)
Retrieve a random variable index from a varset
vs_random_violated(+VS, -Var)
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, -Var)
Retrieve a worst violated variable from a varset
vs_random_worst_index(+VS, -Var)
Retrieve a worst violated variable index from a varset
vs_size(+VS, -N)
Get the size of a varset
vs_violated(+VS, -Vars)
Succeeds for each violated variable from a varset
vs_violated_index(+VS, -Vars)
Succeeds for each violated variable index from a varset
vs_worst(+VS, -Vars)
Succeeds for each worst violated variable from a varset
vs_worst_index(+VS, -Vars)
Succeeds for each worst violated variable index from a varset

Structures

struct monitored_constraint(alias, violations, suspensions)
No description available

Other Exports

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)

Description

Overview

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:

Actual constraint implementations can be found in the library lib(tentative_constraints).

Tentative Values

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:

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
All these operations are undone on backtracking.

Variable Sets

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, -Vs)
get a list of all the variables in the set
vs_element(+VS, +I, -V)
get a particular variable from the set
vs_member(+VS, -V)
enumerate all variables from the set
vs_random(+VS, -Vs), vs_random_index(+VS, -Is)
pick a random variable from the set
vs_random_violated(+VS, -Vs), vs_random_violated_index(+VS, -Is)
pick a random violated variable from the set
vs_all_violated(+VS, -Vs), vs_all_violated_index(+VS, -Is)
get a list of all violated variables from the set
vs_violated(+VS, -V), vs_violated_index(+VS, -I)
enumerate all violated variables from the set
vs_random_worst(+VarSet, -WorstVar), vs_random_worst_index(+VarSet, -I)
pick a random variable with maximum violations from the set
vs_all_worst(+VS, -Vs), vs_all_worst_index(+VS, -Is)
get a list of all the maximally violated variables from the set
vs_worst(+VS, -V), vs_worst_index(+VS, -I)
enumerate all maximally violated variables from the set

Constraint Sets

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:

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
The total violation count of all the constraints in the set can be accessed 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)
Constraints from the constraint set can be selected according to different criteria through the following predicates:
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

Invariants

There is currently one primitive to maintain arithmetic invariants:

-Res tent_is +Expr
the tentative value of Res is the tentative result of Expr

Search and Randomised Primitives

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

Tracing

A simple tracing facility is provided via

tent_trace_array(+Stream, +Name, +ArrayList)
Print a message whenever a tentative value changes
Also, the Visualisation Tools can be used with this library, by creating viewables with type changeable(tentative,Type).

Constraint implementation interface

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:
register_for_notification(?TV, +Tag, ?Receiver)
register to receive messages about changes to TV's tentative value
This messaging facility is based upon the primitive in lib(notify_ports).

Constraints

Actual constraint implementations can be found in the library lib(tentative_constraints).

Example

See lib(tentative_constraints).

About

See Also

library(tentative_constraints)
Generated from tentative.eci on 2017-10-25 11:22