Luis Quesada
2012-04-22
Dear all,
I am having some issues with the example of the Tree constraint in Page 161 of choco-doc-2.1.3.pdf. Not sure this is due to misusing the tool or to actual bugs in the implementation. Also, I am not sure whether the first issue is caused by the Tree constraint or whether this bug is independent of the csp being encoded.
The issues are the following:
1. I added few lines at the end of the example to print the statistics. I am getting a negative number for the number of failures:
- http://dl.dropbox.com/u/40279973/Bug1and2.java
2. I decided to use "s.minimize(s.getVar(objective),false)" instead of "s.solve()". But I get the following exception when doing so:
Exception in thread "main" choco.kernel.solver.SolverException: Illegal state: the best objective 52 is not equal to the best solution objective 1
at choco.kernel.solver.search.AbstractOptimize.restoreBestSolution(AbstractOptimize.java:180)
at choco.kernel.solver.search.AbstractGlobalSearchStrategy.endTreeSearch(AbstractGlobalSearchStrategy.java:297)
at choco.kernel.solver.search.AbstractOptimize.incrementalRun(AbstractOptimize.java:155)
at choco.cp.solver.CPSolver.launch(CPSolver.java:955)
at choco.cp.solver.CPSolver.optimize(CPSolver.java:2243)
at choco.cp.solver.CPSolver.minimize(CPSolver.java:2207)
at base.Bug1and2.runBug(Bug1and2.java:102)
at base.Bug1and2.main(Bug1and2.java:110)
3. I modified the example a bit to see whether it is possible to constrain the successor variables. In the following example I am stating the the forest should have 2 proper trees. But I am also constraining the successor variables in such a way that there is only one proper tree. Clearly, the encoded csp is inconsistent. But I still get a solution:
- http://dl.dropbox.com/u/40279973/Bug3.java
Thanks in advance for explaining the three issues.
Cheers,
Luis
Charles Prud'homme
2012-04-25
Hi Luis,
I am getting a negative number for the number of failures
This an expected behavior, I mean, the failure count is not plugged by default. To do so, you must call:
s.monitorFailLimit(true);
before solving your problem.
I decided to use "s.minimize(s.getVar(objective),false)" instead of "s.solve()"
When the search ends, in optimization, the best (last) solution is restored and checked, that is, a loop is made over variables of the problem to set the solution value and a propagation loop is run.
A default value is stored for not instantiated variables in a solution.
When an incomplete solution is restored, those variables are restored with the default value (Integer.MAX_VALUE) and the propagation fails.
To prevent from getting this error, you can add "-ea" JVM option: it forces the solver to check to completeness and correction of every solution.
But, you can interpret this error in two ways:
- the search strategy is incomplete,
- the propagation is incomplete.
In your case, I think the incompleteness comes from the propagation.
But I still get a solution
Hmmm… there is a tiny bug in the awake of the constraint Tree. Fixing it solves your issues.
I can give you a patched JAR file, if you need it now.
Hope it helps,
CP
Luis Quesada
2012-04-25
Hi Charles,
Thank you very much for your answer! Indeed I also thought that Tree was missing some events. I would certainly love to have the fixed JAR file.
Thanks in advance for this!
Cheers,
Luis
Luis Quesada
2012-05-11
All,
I am having a new issue with the fixed version of the constraint. Please try the second file that I sent in my first message:
http://dl.dropbox.com/u/40279973/Bug3.java
But this time comment out the for loop binding the successor variables:
for (IntegerVariable var:parameters.getSuccVars()){ m.addConstraint(eq(var,0)); }
I get the following exception when doing so:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0 >= 0
at java.util.Vector.elementAt(Vector.java:427)
at choco.cp.solver.constraints.global.tree.filtering.structuralFiltering.tree.Tree.feasibility(Tree.java:89)
at choco.cp.solver.constraints.global.tree.filtering.FilteringAdvisor.applyFiltering(FilteringAdvisor.java:200)
at choco.cp.solver.constraints.global.tree.TreeSConstraint.propagate(TreeSConstraint.java:168)
at choco.cp.solver.constraints.global.tree.TreeSConstraint.awake(TreeSConstraint.java:139)
at choco.kernel.solver.propagation.event.ConstraintEvent.propagateEvent(ConstraintEvent.java:106)
at choco.cp.solver.propagation.ConstraintEventQueue.propagateOneEvent(ConstraintEventQueue.java:178)
at choco.cp.solver.propagation.ChocoEngine.propagateEvents(ChocoEngine.java:222)
at choco.cp.solver.CPSolver.propagate(CPSolver.java:2044)
at choco.kernel.solver.search.AbstractGlobalSearchStrategy.initialPropagation(AbstractGlobalSearchStrategy.java:204)
at choco.kernel.solver.search.AbstractGlobalSearchStrategy.incrementalRun(AbstractGlobalSearchStrategy.java:261)
at choco.cp.solver.CPSolver.launch(CPSolver.java:956)
at choco.cp.solver.CPSolver.solve(CPSolver.java:2114)
at choco.cp.solver.CPSolver.solve(CPSolver.java:2119)
at base.Bug3.main(Bug3.java:122)
Cheers,
Luis
Charles Prud'homme
2012-05-22
Hi Luis,
cf. BUG # 3528829
I've fixed it in revision 1912 in the trunk.
It should work correctly now, it was a side effect of the previous bug in initial propagation.
I'll release Choco very soon, but you can dl the source to test the patch.
CP
Luis Quesada
2012-05-22
Thanks a lot Charles!
I just compiled the sources. The example is working fine for me now.
Thanks a lot!
Cheers,
Luis
PS: I wonder whether, for the next release, you would also consider the cancellation of the deprecation of the following taking into account the recommended way of computing solutions on demand:
s.setDoMaximize(false);
s.setRestart(false);
s.setFirstSolution(true);
Also, I noticed that these ones are also deprecated:
s.monitorNodeLimit(true);
s.monitorTimeLimit(true);
Are we supposed to use the latter ones when measuring the time and the nodes?