Feasible Tuple (Table) Constraints

[Vivian Steller]

With JSR-331, can one somehow realize constraints on tuples as implemented by Choco (see http://www.emn.fr/z-info/choco-solver/c ... Variable...)?

Thanks for any hints!

[JacobFeldman]

Vivian,

There are many different formulations of table constraints, and the JSR331 Expert Group have not agreed on any of them yet - so they are not a part of the standard yet. I do have one particular formulation influenced by ILOG CP Solver. Here it is:

        /**

         * Creates and returns a new constraint stating that all variables from "vars"

* must take values compatible with the table "table", in which

* each row of the table represents either a (permitted) or (not permitted) combination,

* depending on the value of "status". The variables of "vars" are

* compatible with a row of a (permitted) table if the first variable is bound to the value in the first

* column of the row, the 2nd variable is bound to the value in the 2nd column etc for all

* variables and columns. If it is a (not permitted) table, then the values the variables

* in "vars" take must not form any of the rows present in the table.

*

* @param vars the array of variables this table constraint constrains.

* @param table a 2-dimensional array of ints, where each row of the table represents a

*              tuple containing a value for all the variables in "vars".

* @param status - Constant.EXCLUDE indicating the tuples expressed in the table are not permitted,

*              or Constant.INCLUDE indicating the tuples expressed in the table are permitted.

* @return a Constraint enforcing that the variables in "vars" take values which are compatible

*         with the table "table".

* @throws Exception if table[i].length != vars.length for all i.

*/

public Constraint tableConstraintImpl(Var[] vars, int[][] table, int status) throws Exception;

I will probably add it to the "extra" but it could be useful if meanwhile you explain your exact needs.

Jacob

[Vivian Steller]

Hello Jacob,

great, that's exactly what I'm looking for!

My use case would be exactly covered by this interface: in my kind of application it's quite a common use case that users specify constraints extensionally (by specifying the tuples that form valid assignments) rather than intensionally (by specifying the constraints to express the relationships between variables). For example, my application will read all feasible tuples from a relational database table. Using a table constraint transformation of database tuples into the world of CP is straightforward.

Otherwise I would have had to generate constraints like (a = 1 AND b = 2 AND c = 3) OR (a = 1 AND b = 1 AND c = 1) OR ... for a set of tuples like ((1, 2, 3), (1, 1, 1), ...) and I think this scales very bad.

À propos scalability: Choco not only provides table constraints but also a tuple constraint that tests each tuple agains a given Java predicate implemented through the "LargeRelation" interface. See http://www.emn.fr/z-info/choco-solver/choco-kernel/apidocs/choco/Choco.html#relationTupleAC(choco.kernel.model.variables.integer.IntegerVariable%5B%5D,%20choco.kernel.solver.constraints.integer.extension.LargeRelation) I think this could also be quite reasonable to use for large relations but I wouldn't really expect for this one to be standardized (although it would be great, of course) since use cases might be rather rare for CP.

Anyway, if you could add the above method to the extras would be great!

Thanks very much in advance, Jacob.

- Vivian

[JacobFeldman]

Vivian,

I believe I could quickly provide a very basic, common implementation of the specfied Table constraint. Then concrete solvers will overload it with more efficient solver-specific implementations - I know that JaCoP and Choco provide very good table constraints. I will do it as time permits. However, let me know when you actually need it and I will try to accommodate your needs. 

Jacob

[Vivian Steller]

Hello Jacob,

sorry for the long delay of my response.

Meanwhile, I implemented the underlying core model of my application and the time to implement the "constraint" part on top of it comes closer. As stated earlier, I'm going to implement some kind of "object-oriented CSP", which could be seen as the mathematical/logical foundation of my application. Let me shortly explain what I mean by "OO-CSP":

Say we have two classes:

class A

{

   int x;

   int y;

}

class B

{

   int z;

}

For these classes there are some constraints defined, e.g.:

C1: A.x < 5;

C2: feasible-tuples(A(x,y), {(1, 2), (3, 4), (5, 6), (7, 8)})

C3: A.y = B.z;

Now, the task of the solver effectively is to find values for the classes' variables in a manner that all constraints imposed on these two classes are satisfied when the classes are instantiated using these values. Consequently, solutions for the given CSP include:

{ {A(1,2), B(2)}, {A(3,4), B(4)} } or, equivalently but written more CSP like as tuples of (x, y, z): { (1, 2, 2), (3, 4, 4) }

Furthermore, I want to employ this OO-CSP approach incrementally, that is, combined with user interaction: the application presents the user an interactive form, containing dropdowns for each variable A.x, A.y and B.z. The dropdowns contain only values that are part of the solution spaces/the variable's domain: A.x = {1, 3}, A.y = {2, 4}, B.z = {2, 4}. Now, if the user selects value "4" for B.z, there is only one possible solution remaining and thus, also the other dropdowns should automatically be selected correctly: A.x = {3}, A.y = {4} and B.z = {4}.

Of course, this is just the beginning. Both, the constraints can get more complex (e.g. C.c = A.x * A.y, C.c < 10) and the class structure (the "domain model") can get much more elaborated (think inheritance, nested objects, aka. associations, arrays, sets, maps etc. - for some of these I'm still not sure how to translate these into a CSP though).

So, this is the overall use case. I'd be quite interested what you think about this and if you have any tips at hand for me implementing this (I just found a single paper on OO-CSP, somewhere read about Hierarchical CSP and dynamic CSP... do you know any technique applicable in my context)? Have you doubts whether it is possible at all translating this into a regular CSP and solving this with JSR-331?

Well, and to get back to the topic on "feasible tuples"/the table constraint: in the use case above one could image that there might be a class A whose exact instances might be loaded from a database, that is, the constraint C2 is populated with database rows, and the solver should constraint the solutions to those tuples found in the database.

I'm really looking forward to here from you (and others of course!). It would be great if you could share some ideas on how to implement this (the table constraint as well as the OO-Approach in general). If you'd be interested I could keep you up to date with my findings about OO-CSP?

Thanks in advance and best regards,

Vivian

[JacobFeldman]

Vivian,

I do not see anything unusual in your intentions. Most of applications developers do exactly what you want. They define their own Java classes for their business objects (like your A, B, etc.). Let's say a class BusinessProblem is a singleton that is a factory and a placeholder for all my business objects.  You express constraints between your business objects as methods of BusinessProblem, and/or, A, B, etc. For example, BusinessProblem may have a business method like  public boolean makeEqual(A a, B b); for your constraint C3.

Then you create a class ConstrainedProblem that is parallel to BusinessProblem and that is inherited from JSR-331 ProblemDelegator. Possibly you also create classes ConstrainedA, ConstrainedB, etc. You create constrained objects that are parallel to business objects and keep references between them. You implement business constraint like "makeEqual" by posting constraints between the proper constrained variables. When all constraints (or even 1 constraint) are posted you call business method "solve" that correspond to the constrained method getSolver().findSolution(). If a solution is found you take from the solution's values for all instantiated constrained variables and assign them to the related business variables.

In the old presentation "Design Patterns for CP" we called this approach "CCC" (consistent constrained core) - see http://openrules.com/presentations/pact98.pdf. It works especially good for constrained graphical interfaces - see the proper pattern. By the way, a good example of this approach is our own implementation of a Scheduler built on top of the JSR-331 (see my post) - I may provide you with all sources if you are interested.

Regarding the table constraint - my old offer stay the same: I can do the proposed implementation when you need it (but not earlier than in March).

Good luck,

Jacob

[Vivian Steller]

Jacob, thanks very much. You provided quite useful ideas, I've to see how to match these with my exact use case, but this is definitely a good way to start. The thing is that my use case is still slightly more complex: as I'm about to design a framework (for building web-based configurators) neither the domain model (again, modeled as JavaBeans) itself and the constraints imposed on that model are known in advance. So the framework inspects the domain model, the constraints (defined using Bean Validation annoations, see JSR-303) and transforms both of these generically into a CSP and tries to solve it. Nevertheless, I think your ideas about the API are basically applicable in that case, too. Let's see.

The presentation on "Design Patterns for CP" seems quite interesting, I'll have a more closer look on them soon. And yes, even though scheduling and resource allocation is not really in range of my topic, I'm certainly interested in any practical implementation of CP as there can't be found much resources on the web (except those implementations for classical CP problems). It would be great if you could send me some code!

Also, I'd still be very thankful if you could provide some implementation of the table constraint (march/april is quite okay - I'll come back to you then ;). Beyond StringVars (on which you already helped me) and this table constraint there is only one issue left for my use case to be solved (the "modulo operator", see my next topic), at least for the moment :) By the way, I looked into some implementation of a table constraint (from Choco) and even implemented my own little "solver" including a tuple constraint, however, I'm not really skilled enough regarding CP and JSR-331 to implement it myself. Thus, I'm quite curious about your solution. Another thing is that I'm still not able to see how/where the algorithms known from scientific papers about CP such as propagation, node consistency, ac-3 consistency etc. are implemented within JSR-331 (aka. one of it's implementation). I think sooner or later I'll open another thread for this to gather some more input ;)

Anyway, for now, thanks again for your help.

Cheers,

Vivian  

[JacobFeldman]

Vivian,

1. JSR-331 interface for configuration problems.  The development of the Configurator interface (along with Scheduler, Router) was announced in JSR-331 future plans. I'd be really glad if you decide to do it on top of JSR-331. If this development is going to be open sourced I 'd gladly participate in it.

2. We will include the Table constraint (as previously specified) in the next release (March/April).

If you want an access to the JSR-331 SVN repository (that includes Scheduler's sources) send a request to jacobf...@openrules.com.

Best,

Jacob

[Vivian Steller]

Jacob, 

about 2) that's great news! I'm looking forward to the next release already!

about 1) it would be really fantastic if there was standardized support for configuration problems and I'd be happy to follow and participate in discussions about this standardization effort. In fact, the framework I'm trying to implement as my diploma thesis project really tries to solve exactly this issue: standardize the development of configurators. However, I'm not directly focussing on how to model these problems using CSP (there are plenty of related papers about this) but instead I'm trying to design an approach that makes implementing the configurator tremendously simple for the "average" Java web developer (e.g using standards like JPA and Bean Validation that are widely accepted in the community). And yes, all this IS going to be open sourced, too! However, I'm not sure about the exact licensing model yet. By the way, the project is named OpenConfigurator, a name that should sound appealing to you ;) As soon as I've something written down for my thesis I'll let you know. It would be fantastic to discuss some ideas with you!!

Until soon, 

best regard,

Vivian