library(tentative)

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:

• A variable can be given a tentative value. This is a value which is attached to the variable, but does not constrain the variable.
• Tentative values are observed by monitored constraints. A monitored constraint checks whether a constraint is satisfied given the current tentative values of its variables, or computes a measure of violatedness for a tentatively violated constraint.
• Violatedness can be attached to constraints and to variables. Typically, when a constraint is tentatively violated, this increases the violatedness count of the constraint itself, and the violatedness count of those variables that can be made responsible for the violation.

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}

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

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, -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

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

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

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

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.

	struct(monitored_constraint(
		alias,		% the constraint goal (or equivalent term)
		violations,	% a tentative variable
		suspensions	% suspensions of the monitoring goals
	)

register_for_notification(?TV, +Tag, ?Receiver)

register to receive messages about changes to TV's tentative value

Constraints

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

Example

See lib(tentative_constraints).

About

• Author: Joachim Schimpf
• Copyright © Cisco Systems
• Date: $Date: 2016/08/08 14:36:55 $

See Also