Incremental CSP

[Vivian Steller]

Dear all,

Just a quick question:
Using JSR-331 API, is it possible to add a constraint after solver.findAllSolutions() has been called?

What I basically want to do:
Step 0: initialize a problem
Step 1: calculate all solutions (by calling solver.fAS)
Step 2: add constraint x to problem
Step 3: calculate remaining solutions (again by calling solver.fAS) considering constraint x
Step 4: add constraint y ...
Step 5: calculate remaining solutions ... and so on

Thanks for any insights!

- Vivian

[JacobFeldman]

Vivian,

The specification of the Solver's method "findAlSolutions" states that "The problem state after the execution of this method is always restored". However, I've just tried to do what you want with a slightly modified Test3 in the TCK. It does not work. The reason is that all 3 current implementations rely on a very basic solution iterator implemented on the common level. This implementation does not actually restores the problem state after all solutions are found (it keeps intermediate constraints posted during the search). I will look at it ASAP and will try to improve it. Meanwhile, you may simply create a new instance of the problem after all solutions are found (while I understand it could be costly in your actual application).

In general, some people expressed a concern that JSR-331 should not include the concept of the solution iterator at all. The reasons: 1) a user may misuse it; 2) it could be difficult to implement in some solvers. It would be interesting to hear what users think about it.

Jacob

[JacobFeldman]

Vivian,

I have implemented Solver's method "findAllSolutions" that accurately restores the Problem's state, and allows you to use "incremental CSP".  To do this,I haven't changed the common implementation of the AbstractSolver because it requires an access to an internal organization of search strategies or "goals".  It was decided by the JSR331 Expert Group not to include Goal Programming at this version of the standard. So, there is a special package "javax.constraints.impl.search.goal" that supports goal programming but is not a part of the official standard. Currently this package is used only by the JSR-331 implementation that is based on Constrainer. So, I've added the method  "findAllSolutions" to the class javax.constraints.impl.search.goal.SolverWithGoals that extends the common class AbstractSolver. You may get the latest version from the same URL http://openrules.com/downloads/jsr331/org.jcp.jsr331.tck.zip.  You may execute a new Test5 that demonstrate your "incremental" CSP. Again,currently it is limited to Constrainer only, but I will talk to developers of other solvers - hopefully they will re-implement "findAllSolutions" too. Let me know if it works for you.

Jacob

[Vivian Steller]

Jacob, thanks for your investigation here, sounds great so far and I'll have a look at the updated TCK.

Well, to be honest, I'm not really sure how to live without the solution iterator? I mean, how to get/iterate over all solutions without it? And for me using CSP it's quite essential to determine not only one but exactly all solutions to the problem. So without and iterator I'd simply have to implementing myself, calling solver.solve() multiple times?

By the way, not only because of this functionality but also functionality (like table constraints) discussed in other threads I thought it might be a good idea (maybe not now but in the future) to split the specification into implementation levels. For example, their could be a common base layer that builds the minimum required set for all compatible implementations to implement and their could be additional extension layers that deal with more complex functionalities which could however be implemented in a standardized fashion. One JSR that is organized this way is JSR-170 that standardizes Java Content Repositories (JCR, see http://www.day.com/specs/jcr/1.0/index.html). This way, we could provide a low barrier for implementations to be basically compatible with the specification and additional functionalities could subsequently adjusted to the specification. Maybe we could discuss this idea in a different thread, WDYT?

Thanks meanwhile, as I said I'll have a look at the updated version and will provide further feedback.

Cheers,

- Vivian  

[JacobFeldman]

Vivian,

One reason against "findAllSolutions" was that a "naive" user could be in a loop forever or will get an "out of memory" exception because a number of solutions may grow exponentially even for relatively small CSPs. We are saving all solutions as we go. However, you always may use something like solver.setMaxNumberOfSolutions(10) to stop your solution search after (or before) the first 10 solutions are found. There is also time limits that control time for one solution and for overall search.  

Still from my perspective a better solution will be to give a user control over the way how he/she wants to organize the search using goals as building blocks. Look, for example, how Goal Programming allowed me to implement "findAllSolutions" in a quite intuitive way: 

        public Solution[] findAllSolutions() {

clearSolutions();

Goal searchGoal = combineSearchStrategies();

Goal addGoal = new GoalAddSolution(this);

Goal maxGoal = new GoalCheckMaxNumberOfSolutions(this);

Goal backtrackGoal = new GoalBacktrack(this);

Goal goal1 = searchGoal.and(addGoal);

Goal goal2 = maxGoal.or(backtrackGoal);

Goal goal = goal1.and(goal2);

execute(goal); 

return getSolutions();

}

Now about the JSR-331 implementation. What you described is exactly how JSR331 is implemented. Look at the architectural picture:

We do have a common level that really "provides a low barrier for implementations to be basically compatible with the specification and additional functionalities could subsequently adjusted to the specification." Read more at http://openrules.com/downloads/jsr331/JSR331.Specification.v081.pdf.

I will think how to move my implementation of "findAllSolution" from the SolverWithGoals to the common level. 

Best,

Jacob