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: implement cycle cutting #100

Open
pvdz opened this issue Jun 29, 2016 · 0 comments
Open

Idea: implement cycle cutting #100

pvdz opened this issue Jun 29, 2016 · 0 comments

Comments

@pvdz
Copy link
Contributor

pvdz commented Jun 29, 2016

The idea of a cycle cut is to find secluded groups of variables such that the constraints that use them do not use variables outside that group. Smaller groups have smaller search spaces which may lead to considerable improvement in solving time. These disjointed groups can be solved independently from each other, in parallel even, as a solution to on group will not affect the other group(s).

I've already tried to implement this once and my conclusion at the time was that finding these cycles is rather expensive. To make matters worse most configurations had little to no cycles in the first place; every var was somehow tied into every other var. And in the cases where something was found, the overhead outweighed any potential gains.

We should still revisit this as I'm not convinced that the approach is useless.

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