Clone wiki

OscaR / constraint

A new constraint can be implemented either in Java or in Scala but for this explanation we will consider a Scala implementation. A CP constraint has two responsibilities during the solving proces:

  1. Check that it is consistent according to it's definition
  2. Remove inconsistent values from the domain of it's scope

To implement a constraint you have to extend the Constraint abstract class. The minimum requirement is to override those two methods:

  • def setup (l: CPPropagStrength): CPOutcome This method is in charge of checking if the constraint is consistent according to it's semantic and the current domains and it can also do first propagation to remove inconsistent values. It is also in this method that you register the constraint to potential modification of the domain of the variables in its scope.
  • def propagate (): CPOutcome This method will be called when a domain of a variable has been modified and so the constraint can potentially remove new inconsistent values there or detect it is inconsistent.

Both method return a CPOutcome value which can be:

  • CPOutcome.Failure: you return this to tell to the solver that the constraint is inconsistent and that a backtrack should occur.
  • CPOutcome.Success: you return this to tell to the solver that the constraint will always be satisfied if the domain reduces even more whatever the reduction.
  • CPOutcome.Suspend: you return this to tell to the solver that the constraint has done its work but if something changes, it wants to be called back again.

The Less Or Equal Constraint

This constraint asks that a variable X should be less or equal <= than another variable Y. Let us call our constraint MyLessOrEqual, here is its skeleton:

class MyLessOrEqual(val X: CPVarInt, val Y: CPVarInt ) extends Constraint(X.store, "MyLessOrEqual") {
 
  override def setup(l: CPPropagStrength): CPOutcome =  {   
    CPOutcome.Suspend
  }
  
  override def propagate(): CPOutcome = {
    CPOutcome.Suspend
  } 
}

We can now implement the content of the propagate and after that we'll see what to put in the setup method:

class MyLessOrEqual(val X: CPVarInt, val Y: CPVarInt ) extends Constraint(X.getStore(), "MyLessOrEqual") {
 
  override def setup(l: CPPropagStrength): CPOutcome =  {   
    CPOutcome.Suspend
  }
  
  override def propagate(): CPOutcome = {
    	if (Y.min() >= X.max) CPOutcome.Success
    	else if (Y.updateMin(X.min) == CPOutcome.Failure) CPOutcome.Failure
    	else if (X.updateMax(Y.max) == CPOutcome.Failure)CPOutcome.Failure
    	else CPOutcome.Suspend
  }
}

Let's explain each line of the propagate method:

  • Clearly if the minimum value in the domain of Y is already larger or equal than the max of the domain of X, whatever values are removed from both domain in the future will not affect the fact that the constraint will always be satisfied. This is why we return CPOutcome.Success in this case.
  • Every values of the domain of Y smaller than the minimum of X are inconsistent. This is why we set the minimum of the domain of Y to the minimum of the domain of X using the method updateMin. This method directly impact the domain of Y and could potentially make it empty. In case it becomes empty, updateMin returns CPOutcome.Failure and we must also report this failure as the result of our propagate method.
  • The next case is symmetrical wrt to X
  • Finally if none of the previous cases are true, it means that we are still interested to be called later if something changes on the domain of X or Y.

Now the method propagate is ready we can implement the setup method that will also call it:

class MyLessOrEqual(val X: CPVarInt, val Y: CPVarInt ) extends Constraint(X.getStore(), "MyLessOrEqual") {
    
  override def setup(l: CPPropagStrength): CPOutcome =  {   
        val oc = propagate()
	if (oc == CPOutcome.Suspend) {
		if (!X.isBound()) X.callPropagateWhenMinChanges(this)
		if (!Y.isBound()) Y.callPropagateWhenMaxChanges(this)
	}
	oc	
  }
  
  override def propagate(): CPOutcome = {
    	if (Y.min >= X.max) CPOutcome.Success
    	else if (Y.updateMin(X.min) == CPOutcome.Failure) CPOutcome.Failure
    	else if (X.updateMax(Y.max) == CPOutcome.Failure)CPOutcome.Failure
    	else CPOutcome.Suspend
  }
}

Our setup method first starts by checking if the constraint is consistent and does a first propagation step calling first propagate that we just implemented. The only outcome of interest is Suspend, otherwise (Failure or Success) the constraint does not need to attach itself to future domain modifications. Looking at the reasoning made in the propagate method, there is no need to call it on every types of modification in the domains of X and Y. In particular propagate method should be called only when

  • The minimum of X changes or,
  • The maximum of Y changes.

This is exactly what is done by calling the methods X.callPropagateWhenMinChanges(this) Y.callPropagateWhenMaxChanges(this).

Note that for other constraints you might need to register the constraint to other types of domain modifications. You may consider:

  • def callPropagateWhenBind (c: Constraint)
  • def callPropagateWhenBoundsChange (c: Constraint)
  • def callPropagateWhenDomainChanges (c: Constraint)
  • def callPropagateWhenMaxChanges (c: Constraint)
  • def callPropagateWhenMinChanges (c: Constraint)

all available in CPVarInt API.

We can now write a small test class to use our constraint and see that it does what it is supposed to do:

object MyLessOrEqual {
  def main(args: Array[String]) {
	  val cp = CPSolver()
	  var x = CPVarInt(cp,4 to 9)
	  var y = CPVarInt(cp,2 to 8)
	  
	  cp.add(new MyLessOrEqual(x,y)) // add the constraint to the model
	  println("x:"+x+" y:"+y) // x: 4..8 y: 4..8
	  cp.add(y <= 6)
      println("x:"+x+" y:"+y) // x: 4..6 y: 4..6
  }
}

Updated