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.

Advertisements

About jacobfeldman

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

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