JSR-331 release 1.0.0 is available for free downloads

Everybody who is interested in using constraint programming tools in Java may now download JSR-331 v. 1.0.0 from http://openrules.com/jsr331.  The latest release has been delivered to the JCP for the final approval. You may download JSR-331 from here, try multiple examples of constraint satisfaction and optimization problems, and start writing CP-based engines for your own problems.

To install JSR-331, simply download, unzip, and import the Eclipse project “org.jcp.jsr331.tck” “to your Eclipse workspace. JSR-331 v.1.0.0 comes with 3 working implementations based on open source CP solvers: Choco, Constrainer, and JaCoP. One more implementation is on the way. All included software comes with sources and available under the terms of open source licenses. You may look at the latest JSR-331 User Manual. There is a Google support group for all your technical questions. Your comments and suggestions are very welcome.

Using Constraint Solvers as Inferential Rule Engines

In the post Representing and solving rule-based decision models with constraint solvers I described the use of constraint solvers as rule engines. The proposed approach allows a business analyst (not a programmer) to represent his/her business problem in business terms using only business tools such as Excel and without worrying about an underlying rules execution mechanism (either it is a RETE-based rule engine or a constraint solver).  In a way this approach may be considered as a standardized way to represent constraint satisfaction and optimization problems.

A paper that describes this approach in details has been published at RuleML 2011 – America, LNCS 7018, pp. 208-221, 2011, Springer-Verlag Berlin Heidelberg 2011.

CP Standardization Update

The latest noticeable progress has been done in two directions:

1)      Developing JSR-331, a Java CP API.  JSR-331 has successfully passed the Public Review Vote – see http://jcp.org/en/jsr/results?id=5118.  Now it has 3 working implementations based on open source CP solvers (Choco, Constrainer, and JaCoP) and many examples that explain how to use the standard to represent and solve different CSPs. These JSR-331 implementations currently support integer, boolean, and set constrained variables, and many popular binary and global constraints. The implementation of real constrained variables is under way.  The latest User Manual can be found at http://4c110.ucc.ie/cpstandards/files/JSR331.UserManual.v072.pdf. To download and try JSR-331 with all examples and sources please send a request to jacobfeldman@openrules.com. The next step is to produce the JSR-331 Final Draft that will include an enhanced TCK (Technology Compatibility Kit) and more practical examples. We expect to publish the Final Draft in August.

2)      Developing a common CP XML format. A small group of ACP members (Julien Fischer, Peter Stuckey, Radoslaw Szymanek, Guido Tack) have modified FlatZinc XML, the XML version of FlatZinc to create a draft standard for CP solver interchange. When this standard is finalized, an ability to save/load constraint satisfaction problems in the CP XML format will be added to the common level of the JSR-331 implementation. Read more about CP XML in Peter Stuckey’s post at the CP Standardization Discussion Forum and provide your comments and suggestions.

JSR-331 now supports constrained set variables

I have added support of the constrained set variables to a common implementation of the JSR-331. This basic implementation of the interface VarSet can work with any underlying CP solver (even if it does not support its own set variables).  While the standard JSR-331 interface already defines VarSet for a while, only now JSR-331 users can utilize set variables in their problem definitions.  There are two examples that demonstrate how to use set variables:

- FlightCrews - configuring flight crews under different constraints such as cardinality, knowledge of foreign languages, and more.

- Manners - this is a set of examples that deal with a notorious benchmark “Miss Manners” frequently used to compare performance of different rule engines.  The problem is to find an acceptable seating arrangement for all guests at a dinner party.  An acceptable arrangement should match people with the same hobbies, and to seat everyone next to a member of the opposite sex.

First we demonstrate how to represent and solve this problem with well-defined data for parties of 16, 64, and 128 guests.  Then we demonstrate how to find an “acceptable” solution even when not all constraints can be satisfied – a situation when rule engines or a simple Java implementation usually stop short.  Our CP-based solution explains how to minimize the total constraint violation. Read more about this problem and comparison of different approaches at my presentation at RulesFest-2009 “Rule Violations and Over-Constrained Problems“.

The implementation of Miss Manners with set variables required an Element constraint to be defined on an array of sets with a constrained set variable served as an index. To implement this constraint on a common level (in a solver independent way), I needed an ability to add new custom constraints. These capabilities currently are not included in the standard JSR-331 interface, but it is a part of the JSR-331 implementation package called “javax.constraints.extra”. This package allows a user to define custom propagators and associate them to certain events occurred on constrained variables.  To implement “ConstraintElementAtOnSets” I used this package and Constrainer as an underlying CP solver.

You may download the latest JSR-331 and try to use constrained set variables for your own problems – simply send me a request to jacobfeldman@openrules.com and I will provide you with an access to all jars and sources.

A new Java interface for Google CP Solver

Recently Google released a Java interface for its new “or-tools” product. This is very good news and congratulations go to Laurent Perron and his colleagues. With a new open source CP Solver coming not from a small company but from Google, we may expect additional recognition of CP among real-world application developers.  Hakan Kjellerstrand made his first review of Google Java CP interface and published a set of working examples. Here is his code for the SEND+MORE=MONEY problem:

 

As you may notice, this interface has its own, unique naming convention like the most of CP solvers do. However, conceptually there should be no problem to build a JSR-331 implementation using a new Google CP solver.  At the same time, the fact that the actual solver’s implementation is done in C++, may cause some configuration issues.  Everything is open-sourced, and if somebody wants to do it now, please contact me at jacobfeldman@openrules.com and I would provide you with an access to the JSR-331 SVN repository. You also may count on my personal support as well. If this development goes well, I hope soon we will have one more (fourth!) JSR-331 implementation.

JSR 331 passed Public Review

JSR-331 has successfully passed the Public Review Vote – see http://jcp.org/en/jsr/results?id=5118. The next step is to produce the Proposed Final Draft. With 3 implementations ready to go we will also concentrate on the TCK (Technology Compatibility Kit) and more practical examples. Thanks to everybody who already contributed – new comments and suggestions are very welcome. See the latest User Manual at http://4c110.ucc.ie/cpstandards/files/JSR331.UserManual.v072.pdf.

OpenRules integrates JSR-331 with BRMS

OpenRules has announced that its redesigned Rule Solver™ is now JSR-331 compliant.  Rule Solver^™ is a long-time available optimization component of OpenRules^® BRMS that allows users to define and solve constraint satisfaction and optimization problems within a business rules environment.

Rule Solver^™ includes JSR-331 based templates that allow business analysts to define their CSPs directly in Excel. For example, here is a rules table that defines a Sudoku problem:

An Excel user with simple copy-pastes defines rows, columns, and blocks. The rules table “postSudokuConstraints”with one AlDiff constraint does the entire work.

While JSR-331 does not include (yet!) a scheduling component, OpenRules added a simple package “javax.constraints.scheduler” that extends JSR-331 to handle scheduling and resource allocation problems.  It allows a user to express a scheduling problem in terms of activities and resources.  Activities may have unknown start, duration and end. Activities may require or produce different resources. Resources may have different types (e.g. recoverable like humans or consumable like money) and their limited capacities may vary over time. The package includes major temporal and capacity constraints specified in accordance with the JSR-331 requirements.

Rule Solver^™ includes OpenRules-based templates for scheduling problems. For example, let’s consider 5 different orders (activities) that fire batches of bricks in the oven (a resource with limited capacities). Each order requires certain oven’s capacity as described in the following picture:

With Rules Solver^™ a user can define the problem in the following Excel rules tables:

To solve the problem a user specifies the following main method (also in Excel):

Here are the results:

Solution:
A[0 -- 1 --> 1)    requires Oven[2]
B[3 -- 4 --> 7)    requires Oven[1]
C[5 -- 4 --> 9)    requires Oven[1]
D[5 -- 2 --> 7)    requires Oven[1]
E[11 -- 4 --> 15) requires Oven[2]

You may read the proper user manual with a lot of examples at http://openrules.com/pdf/RulesSolver.UserManual.pdf and download and try the software from http://openrules.com/insideTrack.htm#RuleSolver.

Hopefully, other BRMS vendors will follow OpenRules lead and will integrate JSR-331 in their Business Rules products.

JSR-331 wins JCP Award “The Most Innovative JSR of 2010″

Surprise, surprise! Our JSR-331 actually won the JCP Award for The Most Innovative JSR of 2010. It was announced at Java One on September 22 in San Francisco. It is certainly nice, and what the JCP notification page says about JSR-331 is flattering: “JSR 331, Constraint Programming. This JSR represents the real innovation in SE/EE since the 300 number of JSRs started; where almost every other JSR especially in SE/EE is just an upgrade to existing technologies.”

However, from a pure Java perspective I think there were more deserving nominees, see for example JSR-299, Contexts and Dependency Injection for the Java EE platform.  Here what JCP says about it: “Critics have foreshadowed the death of the Java language, claiming that there is little more than can be done to evolve it and therefore needs to be replaced. JSR 299 silenced these viewpoints.”

It is interesting that we did nothing to nominate or somehow promote our JSR – I simply had no idea about this competition. Of course, I understand this award is more related to the recognition of the CP technology itself. But it also shows that CP is still not within main stream of real-world application development where it certainly deserves to be. Hopefully this award and the standard API will make CP more visible and accessible to Java developers.  So, now it becomes even more important to expedite creation of a JSR-331 User Manual and making initial implementations available for free downloads to all application developers.

See http://jcp.org/en/press/news/awards/2010award_nominees

CP-2010

CP-2010: 16th International Conference on Principles and Practice of Constraint Programming, the major CP event of the year,  will be held on September 6-10, 2010 in St. Andrews, Scotland. The agenda includes an important Standardization Discussion on Sep. 10 from 9:00 to 10:20.

JSR-331 nominated for a Java Community Process Award

I’ve learned that the JSR-331 “Constraint Programming API” has been nominated for the most innovative JSR of the year for JCP Program Awards. Hopefully, it will bring more recognition of the CP power among Java developers. Related links: 

JCP Awards:  http://blogs.sun.com/jcp/
JSR-331 Specification (Early Draft): http://4c110.ucc.ie/cpstandards/files/JSR331Specification.v061.pdf
http://www.cpstandards.org
http://cp2010.cs.st-andrews.ac.uk/events.php