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
Reduction from dancing links instance to SAT instance #29338
Comments
Author: Sébastien Labbé |
Branch: u/slabbe/29338 |
Commit: |
Branch pushed to git repo; I updated commit sha1. New commits:
|
comment:3
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date. |
comment:4
This is really nice. Only one suggestion: make it so that Personally, I prefer |
comment:6
I rebased on top of a more recent version of Sage. Needs review. I will implement |
comment:7
See #29955 for the reduction to MILP. |
comment:8
A question about the interface. Since we are going to have:
|
comment:9
I made that choice to make it explicit that we are not using the dlx solver (we can not compare timing (at least on the first call) for example, because of the initialization of the rows is already done when using "dlx") and to make explicit that there is a overhead in doing the translation of the thousands of rows into something else. I think What do you think is best to do? |
comment:10
Ah, this is a very good point! So I should think of the principal goal of this ticket as the implementation of
[Note that |
Reviewer: Franco Saliola |
comment:12
All doctests pass, including the optional doctests with 'glucose', 'picosat', etc. Thank you, Sébastien! |
comment:13
But this is not enough, because one need to translate the solution of the SAT problem into a solution to a DLX problem... |
comment:14
Thanks for the review! |
Changed branch from u/slabbe/29338 to |
The proposed branch adds 2 new methods which allows what follows:
This is based on the new method:
Component: combinatorics
Author: Sébastien Labbé
Branch/Commit:
2e97345
Reviewer: Franco Saliola
Issue created by migration from https://trac.sagemath.org/ticket/29338
The text was updated successfully, but these errors were encountered: