Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

Restricting domains in executeAfterSolution()

Help
2012-06-22
2013-05-30
  • Hi,

    I have a SimpleSolutionListener to a DepthFirstSearch, and I would like to know how I can restrict the domain of a variable in executeAfterSolution() such that the restriction will remain valid during the rest of the search, and won't be removed as soon as the search backtracks.

    I have had a look at how it is done for the cost variable in an optimization search, at it appears that this is done simply by calling IntDomain.in() with the current store level. (I noticed that the DepthFirstSearch also creates a XltC constraint on the cost variable that then doesn't seem to be used anywhere afterwards…)

    Can I just do the same on any variable in SimpleSolutionListener.executeAfterSolution() to permanently shrink the domain of the variable?

    Thank you in advance for your suggestions.

     
  • kris
    kris
    2012-06-23

    I would solve this problem using the following method. Create a list of variables and values you want to restrict and then at the beginning of search (DepthFirstSearch) always prune domains of these variables using either method in() or a constraint. This list can be dynamic and variable can be added or removed but of course restriction of domains will be valid on all level below the current one. You probably can use initialize listener but this I am not sure and cannot check the code right now.

    Good luck,
    /Kris

     
  • Hi Kris,

    Thanks for your answer. Let me clarify a bit what would like to do, though.

    I would like to enforce a restriction on one variable *during* the search (every time a solution is found — I'm searching for all solutions), not just at the beginning of the search. Furthermore, I would like that restriction to be valid at *all* levels, including levels above the current one (i.e. above the level at which a solution has just been found).

    This is basically what is currently done to the cost variable during an optimization search: every time a new solution is found, the domain of the cost variable is restricted to make sure that all subsequently found solutions are strictly better than the incumbent.

    I have looked at how it is currently done for the cost variable in an optimization search, at it appears to me that all that is needed is to restrict the domain of the variable at the level at which the solution was just found. This looks a bit counter-intuitive to me, since I would expect this restriction to be undone as soon as the search for the next solution resumes. I talked with Radek about this a long time ago, and I think I remember he mentioned that the cost variable was handled in a very special way, to make sure that restrictions made to its domain are not undone when backtracking to search for a strictly better solution.

    Could you explain how the cost variable is handled in an optimization search so that restrictions to its domain remain valid across all levels?

    Thanks a lot

     
  • kris
    kris
    2012-06-23

    Hi!

    Yes, this is what I tried to suggest but was probably not very clear. In solution listener you handle list of variables yo want to limit their domains. You basically record variables and their required values. Then during search, each time you start a new node in search tree you limit domains of variables you have on the list you created and maintain in solution listener.

    This is, in fact, what we do with cost variable. Each time we found a solution we store the value of cost variable. Then during search we basically impose that the cost variable must have a domain that is strictly lower than the last found value.

    I hope, it helps and explains a little bit the idea.

    Best,
    /Kris

     
  • I see; now I understand how it is done for the cost variable. I was confused by the fact that when you wrote "at the beginning of search," you meant "at each search node."

    If I don't want to implement my own search and just reuse DepthFirstSearch, what kind of listener do I need to use, which would be called at each search node, so that I can impose restrictions on the domains? For the moment I am only using a SimpleSolutionListener, which I believe is only notified when a solution is found.

     
  • kris
    kris
    2012-06-23

    Hi again,

    I did not program the final version of DepthFirstSearch so I might not be totally correct but I think you can do the following. In solution listener you record all your variables and their values. Of course only the variables that you are interested in. Then I think you need to add your own code to DepthFirstSearch or add call for additional listener you define and add a call in DepthFirstSearch. This code should enforce new restriction of domains of variables. I do not see in the code a listener that is called before calling consistency for each search node. Sorry!

    /Kris

     
  • Maybe I could use a ConsistencyListener? It is called only after the consistency check, but maybe I can then impose the domain restriction and then check consistency again? Do you think this could be significantly less efficient than first imposing the restriction and then checking consistency only once? If so, adding support for listeners called before consistency checking is a suggestion of improvement that you might want to consider.

     
  • kris
    kris
    2012-06-23

    No, it is not a good idea. The consistency in such case will be checked first on **the next** level. You should add your constraints or domain restrictions before calling consistency method.

    /Kris

     
  • I might have found a workaround, using the existing cost variable mechanism, but then re-defining the cost of the incumbent in my SolutionListenener. We'll see if this achieves what I want.

    Thanks a lot again for your clarifications and suggestions!