Creating and Posting Constraints

Let’s consider how the proposed JSR-331 standard suggests creating and posting constraints. For example, the most popular linear constraints can be created and posted by the Problem’s method “post” like in this example:

Var x = p.variable(“X”,0,10);
Var y = p.variable(“Y”,0,10);
p.post(x,“<“, y);

As you may guess here we defined a constraint that states: a variable x should be always strictly less than variable y.  Here p is an instance of the standard class Problem and the last statement is a shortcut for

p.postLinear(x, “<“, y);

This interface assumes that the proper constraint was not only created (actually this method returns an instance of the class Constraint) but it is also “posted” (“memorized”, “activated”). Constraint posting means that this constraint will remove all inconsistent values from domains of the variables x and y. For example, you may reasonably expect that value 10 does not belong anymore to the domain of x and 0 does not belong to the domain of y (while it is up to an  implementation to decide when to actually remove these values – right after constraint posting or during a search). You may also expect that this constraint will keep removing inconsistent values every time when domains of x and/or y is changed. For example, if you additionally post this constraint:

p.post(x, “>=”, 4);

you may expect that the previous constraint will remove all values that are less than 5 from the domain of y.

Sometimes you need to create constraints without posting them, like in this example:

Constraint c1 = new Linear(x,”=“,7);
Constraint c2 = new Linear(y,”=“,9);
p.postIfThen(c1,c2);

Here, if constraint c1 is satisfied then c2 also should be satisfied. Only IfThen-constraint is posted.

There are many flavors of linear constraints:

p.post(x.plus(y),”=“,z);     // x+y = z
Var[] vars = { x, y, z, t };
p.post(vars, “=“, 25);       // sum(vars) = 25
int[] coef = { 3, 4, -7, 5 };
p.post(coef,vars, “>“, 10);  // 3x+4y-7z+5t > 10

Of course, a Java user may write something “ugly” like this

Var exp =  x.multiply(3).plus(y.multiply(4)).minus(z.multiple(7).
plus( z.multiply(5));
p.post(exp, “>“, 10);

The reason is obvious – Java does not support overloaded operators. However, a Groovy user without any additional coding may take advantage of operator overloading in Groovy and express the same constraint as:

p.post(x*3+y*4-z*7, “>”, 10);

All factory methods for creating and posting constraints start with the word “post”. Here is the current list of the method names used to create and post constraints:

  • postLinear or simply  post
  • postAllDiff
  • postElement
  • postCardinality
  • postGlobalCardinality
  • postIfThen
  • postMax
  • postMin

Here are examples for creating and posting constraints for the problem p:

p.post(x,”<“,y);  // the same as p.postLinear(x,”<“,y);
p.post(x.plus(y),”=“,z);

p.postAllDifferent(vars);
p.postElement(vars,indexVar, “=“, 5);
p.postCardinality(vars,3, “>“, 0);

Read more at the JSR-331 Specification Early Review.

Advertisements

About jacobfeldman

CTO at www.openrules.com http://www.linkedin.com/in/jacobfeldmanopenrules
This entry was posted in Uncategorized. Bookmark the permalink.

2 Responses to Creating and Posting Constraints

  1. Carole-Ann says:

    Jacob,

    Thank you for sharing your deep expertise with us. I am very admirative of your endless patience as it relates to the fascinating topic of Constraint Programming.

    One thing keeps bothering me though with those Standards.

    Why do you want to stick with a very low level language???

    I was hoping that the Standard could elevate the syntax to something readable by a human. Don’t tell me that the code is readable — you HAD TO post comments to translate some of it into 3x+4y-7z+5t > 10.

    Why don’t you introduce a constraint syntax (or leverage an existing one)?

    Thanks,

    Carole-Ann

    • jacobfeldman says:

      Carole-Ann,
      There are quite a few specialized constraint languages, e.g. OPL from IBM/ILOG, MiniZinc from G12, Comet from Dynadec. Read more here. They are very good, expressive, and user friendly. However, they force a user to learn peculiarities of a new language, come with proprietary IDEs and specialized interfaces for main-stream development environments. These facts certainly limit their real-world acceptance.

      We consider standard APIs for Java and C# as major but only initial steps on the Road to Standardization. The next natural step is a creation of CP DSL. For example, as I wrote in the above post, you may replace “ugly” Java-level constraint representations with nice “human”-oriented expressions written directly in Groovy, Scala, Boo, and other agile dynamic languages. CP DSL strips out unnecessary boilerplate programming details and allows a user to express constraints in a human way. Such DSL will naturally come up as a result of lower level standardization efforts. You probably would agree that a user can at least read and understand the following Groovy script that presents and solves a notorious puzzle SEND+MORE=MONEY:

      This script will be further simplified but it already works and immediately produces a solution:
      Solution: [9567] + [1085] = [10652]

      Another direction to bring CP to “humans” (business analysts, non-developers) is incorporating standardized CP models in already human-oriented systems such as BRMS (business rules management systems). For example, you may like an elegant presentation of Sudoku constraints in this rules table in Excel/OpenRules:

      Just two lines of a CP snippet and simple copy/pastes allow a user to express Sudoku constraints in a quite natural way. A user concentrates on “What” not on “How”.

      I hope this way we will gradually make the power of CP more accessible for developers of the real-world decision management systems.
      Thank you.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s