alice
library
manual.

Alice Project

The Linear structure


________ Synopsis ____________________________________________________

    signature LINEAR
    structure Linear : LINEAR

The Linear structure provides functionality to post linear equality constraints using a convenient infix operator syntax.

Notes:

The linear module maps linear constraints onto regular sum constraints of the FD module. This transformation is not always optimal, that is, one might be able to devise a better constraint manually.

Note also that since the linear module extensively performs folding of constant expressions, it eventually might exceed the implementation specific integer constant limit of finite domain constraints. In such a case, folding can be prevented by introducing a finite domain variable that is assigned a singleton value.


________ Import ______________________________________________________

    import signature LINEAR from "x-alice:/lib/constraints/LINEAR-sig"
    import structure Linear from "x-alice:/lib/constraints/Linear"

________ Interface ___________________________________________________

    signature LINEAR =
    sig
	infix 7 `*
	infix 6 `+ `-
	infix 5 `#
	infix 4 `= `<> `> `>= `< `<=
	infix 3 `<->

	datatype domain_element =
	    `` of int
	  | `# of int * int

	type domain = domain_element list

	datatype term =
	    FD of FD.fd
	  | `  of int
	  | `+ of term * term
	  | `- of term * term
	  | `* of term * term

	datatype rel =
	    `<   of term * term
	  | `<=  of term * term
	  | `=   of term * term
	  | `<>  of term * term
	  | `>=  of term * term
	  | `>   of term * term
	  | `<-> of rel * term

	val var : domain option -> term
	val bin : unit -> term
	val vec : int * domain -> term vector

	val distribute : FD.dist_mode * term vector -> unit
	val distinct : term vector -> unit
	val post : rel -> unit
    end

________ Description _________________________________________________

datatype domain_element = `` of int | `# of int *int
type domain = domain_element list

Used to describe domains of finite domain variables. `` i denotes the single integer value i and >`#(l,h) denotes all integer values between l and h. For example, [``3,`#(5,10)] denotes [3,5,6,7,8,9,10].

datatype term =
    FD of FD.fd
  | `  of int
  | `+ of term * term
  | `- of term * term
  | `* of term * term

This datatype is used to post arithmetic constraints.

datatype rel =
    `<   of term * term
  | `<=  of term * term
  | `=   of term * term
  | `<>  of term * term
  | `>=  of term * term
  | `>   of term * term
  | `<-> of rel * term

This datatype is used to post linear equations.

var dom

returns a freshly created finite domain variable term initialized with dom.

bin ()

returns a freshly created 0/1 variable term which can be used for reification.

vec (n,dom)

returns a vector of size n of freshly created finite domain variable terms. Each variable is initialized with dom.

distribute (s,v)

distributes the variables in v according to the given strategy s. For details, see here.

distinct v

posts the distinct constraint on all variables in v. For details, see here.

post r

post the constraint denoted by r.



last modified 1970/01/01 01:00