Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Idea: postpone or eliminate isSolved checks during propagation #92

Open
pvdz opened this issue Jun 29, 2016 · 1 comment
Open

Idea: postpone or eliminate isSolved checks during propagation #92

pvdz opened this issue Jun 29, 2016 · 1 comment

Comments

@pvdz
Copy link
Contributor

pvdz commented Jun 29, 2016

Right now the code will check whether a variable is rejected on every step of a propagator. This is somewhat of an optimization because it means propagation can stil there immediately.

What if we stop doing that during propagation and only afterwards, once none of the propagator make any changes? Then we could eliminate some of this overhead at the cost of propagating longer than absolutely needed. However, since the changes per space are often rather limited after the first few, this may not be a bad thing considering the overhead of checking for it explicitly right now.

  • Currently space_propagate will propagate all propagators (low level representation of constraints) until they either reject (when any domain becomes empty the current path to a solution can not lead to a solution and is aborted immediately) or no more changes apply. This does not mean the propagator is solved (like [0,1] == [0,1] but simply that the propagator can't infer any furthe reductions on its own.
  • All propagators actively check whether vars have become empty. They return a constant to reflect the result of propagating; REJECTED, SOME_CHANGES, NOCHANGES. We could omit this check and simply return whether or not something changed.
  • It could be that not stopping a failed branch prematurely leads to doing more steps which in turn could outweigh the potential gains of not checking in the first place. This may also simply differ case by case.
  • Can't outright eliminate rejected checks in propagate because some propagators may need to reject explicitly even though their vars are not EMPTY...
@pvdz
Copy link
Contributor Author

pvdz commented Jun 29, 2016

While investigating this ticket I noticed that there was a redundant layer of isSolved checks. I've eliminated those in #102 and it saves a lot in large data sets.

That PR is not completely doing the things outlined in this ticket so I'm leaving it open for the time being.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant