Issues with the Tree constraint

Help
2012-04-22
2013-04-06
  • Luis Quesada
    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

     
  • 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
    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
    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

     
  • 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
    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?