1. Pierre Schaus
  2. OscaR

Wiki

Clone wiki

OscaR / cplogical

Model Logical Constraints and Reified Constraints

One main asset of CP is it's ability to model logical constraints easily. By logical constraints we mean constraints between CPVarBool which are nothing else than 0-1 CPVarInt variables with 0 representing false, and 1 representing true.

OscaR support the logical or "||", the logical and "&&" and the implication "==>".

When you add a logical constraint between boolean variable, the result is it self a boolean variable that you can add to the solver which is constrained to be true.

For instance

val cp = CPSolver()	
val A = CPVarBool(cp)
val B = CPVarBool(cp)
val C = CPVarBool(cp)	
cp.add(A && B) // is equivalent to cp.add((A && B) == 1) which is equivalent to cp.add((A && B).constraintTrue())

You can build any logical complex boolean expressions using the logical operators (&&,||,==>)

For instance the following program:

val cp = CPSolver()	
	
val A = CPVarBool(cp)
val B = CPVarBool(cp)
val C = CPVarBool(cp)
val D = CPVarBool(cp)
	
cp.solve subjectTo {
  cp.add(((A ==> B) || C) && D)
} exploration {
  cp.binary(Array(A,B,C,D))
  println(A+" "+B+" "+C+" "+D)
} run()

outputs the following solutions:

false false false true
false false true true
false true false true
false true true true
true false true true
true true false true
true true true true

A very useful tool to model logical constraints are the reified constraints. Reified constraints are nothing else than constraints that can be negated (Note that logical constraints are reified constraints them-self since they return a CPVarBool that you can constraint to be false). Very common reified constraints also present in OscaR are the (<==) reified less or equal, (<<=) reified strictly less than, (===) reified equality.

For instance you could count the number of variables taking a value between 2 and 3 (inclusive) in the following way:

val cp = CPSolver()	
	
val X = Array.fill(5)CPVarInt(cp,0 to 5)
val count = sum(X)(x => (x >==2) && (x <<= 4))

count will be a CPVarInt representing the number of variables in X taking it's value in the interval [2,3]. The result of x >==2 is a CPVarBool (0-1) variable equal to true (1) if and only if x is larger or equal to 2. The result of x <<=4 is a CPVarBool (0-1) variable equal to true (1) if and only if x is strictly smaller than 4. The && between the two CPVarBool's is true (1) only if both are equal to true. Then a variable is returned by the sum function representing the summation of the 5 CPVarBool's.

Updated