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.
