alice
library
manual.

The `FS` structure

^Synopsis^{____________________________________________}

    signature FS
    structure FS : FS where type fd = FD.fd

The FS structure provides access to finite set variables and propagators.

Finite set variables are variables whose values are sets of integers.

^Import^{______________________________________________}

    import signature FS from "x-alice:/lib/gecode/FS-sig"
    import structure FS from "x-alice:/lib/gecode/FS"

^Interface^{___________________________________________}

signature FS =
sig
    type space
    type intvar
    type boolvar
    type setvar

    type domain = (int*int) vector
    exception InvalidDomain

    val setvar :  space  ->  setvar
    val setvarVec :  space * int ->  setvar vector

    val lowerBound : space * domain -> setvar
    val upperBound : space * domain -> setvar
    val bounds : space * domain * domain -> setvar

    datatype intrel = EQ | NQ | LQ | LE | GQ | GR

    datatype setrel = CMPL | DISJ | SEQ | SNQ | SUB | SUP
    datatype setop = DUNION | INTER | MINUS | UNION

    val dom : space * setvar * setrel * domain -> unit
    val domR : space * setvar * setrel * domain * boolvar -> unit
    val cardRange : space * int * int * setvar -> unit

    val rel : space * setvar * setrel * setvar -> unit
    val relR : space * setvar * setrel * setvar * boolvar -> unit
    val relOp : space * setvar * setop * setvar * setrel * setvar -> unit
    val relI : space * setvar * setrel * intvar -> unit
    val relIR : space * setvar * setrel * intvar * boolvar -> unit
    val relII : space * setvar * intrel * intvar -> unit
    val relN : space * setop * setvar vector * setvar -> unit
    val relNI : space * setop * intvar vector * setvar -> unit

    val relCSS : space * domain * setop * setvar * setrel * setvar -> unit
    val relSCS : space * setvar * setop * domain * setrel * setvar -> unit
    val relSSC : space * setvar * setop * setvar * setrel * domain -> unit
    val relCCS : space * domain * setop * domain * setrel * setvar -> unit
    val relCSC : space * domain * setop * setvar * setrel * domain -> unit
    val relSCC : space * setvar * setop * domain * setrel * domain -> unit

    val convex : space * setvar -> unit
    val convexHull : space * setvar * setvar -> unit
    val sequence : space * setvar vector -> unit
    val sequentialUnion : space * setvar vector * setvar -> unit

    structure Value :
	sig
	    val make : space * domain -> setvar
	    val empty : space -> setvar
	    val single : space * int -> setvar
	    val is : space * setvar -> bool
	end

    structure Selection : sig
	val setvar : space * setvar vector * intvar * setvar -> unit
	val union : space * setvar vector * setvar * setvar -> unit
	val inter : space * setvar vector * setvar * setvar -> unit
	val interIn : space * setvar vector * setvar * setvar * domain -> unit
        val disjoint : space * setvar vector * setvar -> unit
    end
	
    structure Reflect : sig
	val card : space * setvar -> (int * int)
	val lowerBound : space * setvar -> domain
	val upperBound : space * setvar -> domain
	val unknown : space * setvar -> domain
	val cardOfLowerBound : space * setvar -> int
	val cardOfUpperBound : space * setvar -> int
	val cardOfUnknown : space * setvar -> int
        val assigned : space * setvar -> bool
    end

    (* Branching strategies *)

    datatype fsb_var_sel =
	     FSB_MAX_CARD
	   | FSB_MIN_CARD
           | FSB_MIN_UNKNOWN_ELEM
	   | FSB_NONE
	     
    datatype fsb_val_sel =
	     FSB_MAX
	   | FSB_MIN

    val setvarbranch :  space *  setvar vector * fsb_var_sel *
			fsb_val_sel -> unit

end

^Description^{_________________________________________}

type space: The type of first class comutational spaces. Usually equal to Space.space.
type intvar: The type of finite domain variables. Usually equal to FD.intvar.
type boolvar: The type of boolean constraint variables. Usually equal to FD.intvar.
type fs: The type of finite set variables.
type domain = (int*int) vector: The type of domain descriptions. Used to define set bounds at variable creation, in value declaration, and reflection. It is an ordered, non-overlapping, non-contingous vector of ordered integer pairs. For example the set of all primes between 1 and 10 is #[(2,3),(5,5),(7,7)]
Observe that #[(1,2),(3,4)] is an invalid domain: contigous ranges, use #[(1,4)] instead
#[(1,3),(3,4)] is even more so.
#[(3,2)] is also invalid, the range is ill-defined.
#[(4,5),(1,2)] is nonconformant in pair ordering, #[(1,2),(4,5)] is fine.
exception InvalidDomain: Exception thrown by all variable creation and domain tell operations on receipt of a domain description not conforming to the above rules.
setvar s: Returns a freshly created, unconstrained finite set variable in s. The returned variable is only to be used in s and its decendants.
setvarVec (s,n): Returns a vector of n freshly cretaed, unconstrained finite set variables in s.
lowerBound (s,dom): Returns a freshly created finite set variable in s, already constrained to be a superset of dom.
upperBound (s,dom): Returns a freshly created finite set variable in s, already constrained to be a subset of dom.
bounds (s, dom1, dom2): Returns a freshly created finite set variable in s, already constrained to be a superset of dom1 and a subset of dom2.
datatype intrel: Type to identify an arithmetic relation in constraints. This is the same as FD.relation.
EQ: Equal.
NQ: Not equal.
LQ: Less or equal.
LE: Less.
GQ: Greater or equal.
GR: Greater.
datatype setrel: Type to identify a set relation in constraints.
CMPL: Complement.
DISJ: Disjointness.
SEQ: Set equality.
SNQ: Set disequality.
SUB: Subset.
SUP: Superset.
datatype setop: Type to identify a set operation in constraints.
DUNION: Disjoint union.
INTER: Intersection.
MINUS: Difference.
UNION: Union.
dom (s,x,r,d): Constrains x in s to be in relation r with the set constant denoted by d.
dom (s,x,r,d,b): Constrains b to be true if and only if x is in relation r with the set constant denoted by d.
cardRange (s,min,max,x): Constrains x in s to have a cardinality (number of set elements) between min and max.
rel (s, x, r, y): Creates a new propagator in s to constrain x to be in relation r with y.
relR (s, x, r, y, b): Constrains b to be true if and only if x is in relation r with y.
relOp (s, x, oper, y, r, z): Creates a new propagator in s to constrain z to be in relation r with x oper y.
relI (s, x, r, y): Creates a new propagator in s to constrain x to be in relation r with {y}.
relIR (s, x, r, y, b): Constrains b to be true if and only if x is in relation r with {y}.
relII (s, x, r, y, b): Creates a new propagator in s to constrain all elements in x to be in relation r with y.
relN (s, oper, xs, y): Creates a new propagator in s to constrain y to be the result of the n-ary operation oper on the elements of xs.
relNI (s, oper, xs, y): Creates a new propagator in s to constrain y to be the result of the n-ary operation oper on the elements of xs, which are FD variables treated as singleton sets.
relCSS (s, x, oper, y, r, z) relSCS (s, x, oper, y, r, z) etc.: Creates a new propagator in s to constrain z to be in relation r with x oper y. Depending on which of the CSS, SCS etc. is chose, one or two of the x,y,z can be constant sets specified as domains.
minElement (s, x, y): Creates a new propagator in s ensuring y is the smallest element of x.
maxElement (s, x, y): Creates a new propagator in s ensuring y is the largest element of x.
cardinality (s, x, y): Creates a new propagator in s ensuring y is the number of elements (cardinality) of x.
match (s, x, ys): Creates a new propagator in s ensuring ys is the ordered vector of all elements of x.
convex (s, x): Creates a new propagator in s to constrain x to be a convex set, containing all integers between its smallest and largest element.
convexHull (s, x, y): Creates a new propagator in s to constrain y to be the convex hull of x. Simply put, y has the same smallest and largest element as x, but also contains all integers in between.
sequence (s, xs): Creates a new propagator in s to constrain the largest element of xs[i] to be smaller than the smallest element of xs[i+1].
sequentialUnion (s, xs, y): Creates a new propagator in s to constrain y to be the union of all xs, while xs is a seqence as defined above for the seq constraint. This is a special case of the partitionN constraint.
Value.make (s, dom): Creates a determined set in s containing exactly the elements in dom.
Value.empty (s): Creates a determined, empty set in s.
Value.single (s, n): Creates a determined, single element set in s containing the integer n.
Selection.setvar (s, v, y, x): Creates a new propagator in s ensuring the yth element of v is equal to x. y is constrained be in the range of valid indexes for v.
Selection.union (s, v, y, x): Creates a new propagator in s ensuring the union of the sets in v indexed by all elements of y is x. y is constrained to contain nothing outside the range of valid indexes for v.
Selection.inter (s, v, y, x): Creates a new propagator in s ensuring the intersection of the sets in v indexed by all elements of y is x. y is constrained to contain nothing outside the range of valid indexes for v. If y is the empty set, x is constrained to be the universe.
Selection.interIn (s, v, y, x, d): Creates a new propagator in s ensuring the intersection of the sets in v indexed by all elements of y is x. y is constrained to contain nothing outside the range of valid indexes for v. If y is the empty set, x is constrained to be the universe, given as d.
Selection.disjoint (s, v, x): Creates a new propagator in s ensuring the intersection of the sets in v indexed by all elements of x is empty. x is constrained to contain nothing outside the range of valid indexes for v.
Reflection.card (s, x): Returns the current cardinality bounds of x in s.
Reflection.lowerBound (s, x): Returns the currently known greatest lower bound set of x in s. Simply put, all elements known to be in the set.
Reflection.upperBound (s, x): Returns the currently known least upper bound set of x in s. Simply put, all elements not yet known to be excluded from the set.
Reflection.unknown (s, x): Returns the elements whose membership in x is currently unknown in s. Simply put, all elements that may still be both included or excluded.
Reflection.cardOfLowerBound (s, x): Returns the number of known elements of x in s.
Reflection.cardOfUpperBound (s, x): Returns the number of possible elements of x in s.
Reflection.cardOfUnknown (s, x): Returns the number of elements whose membership in x is yet to be determined in s. Same as Reflection.cardOfUpperBound(s,x)-Reflection.cardOfLowerBound(s,x)
Reflection.assigned (s, x): Returns true if x is determined in s. Simply put, same as Reflection.cardOfUnknown(x,s)=0
datatype fsb_var_sel: Identifies the variable selection strategy in branching.
FSB_MAX_CARD : Pick the variable with the largest possible cardinality.
FSB_MIN_CARD : Pick the variable with the lowest possible cardinality.
FSB_MIN_UNKNOWN_ELEM : Pick the variable with the smallest unknown element.
FSB_NONE : Pick the leftmost undetermined variable.
datatype fsb_val_sel: Identifies the value selection strategy in branching.
FSB_MAX : Pick the largest unknown value of the variable.
FSB_MIN : Pick the smallest unknown value of the variable.
setvarbranch (s, v, varStrategy, valStrategy): Creates a new branching (aka distributor or labeling) in s over the setvars in v following the given strategy.

alice library manual.

The FS structure

________ Synopsis ____________________________________________________

________ Import ______________________________________________________

________ Interface ___________________________________________________

________ Description _________________________________________________

alice
library
manual.

The `FS` structure

^Synopsis^{____________________________________________}

^Import^{______________________________________________}

^Interface^{___________________________________________}

^Description^{_________________________________________}