Opened 23 months ago
Closed 23 months ago
#29955 closed enhancement (fixed)
Reduction from dancing links instance to MILP instance
Reported by:  slabbe  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  combinatorics  Keywords:  
Cc:  slelievre  Merged in:  
Authors:  Sébastien Labbé  Reviewers:  Franco Saliola, Matthias Koeppe 
Report Upstream:  N/A  Work issues:  
Branch:  da23ad1 (Commits, GitHub, GitLab)  Commit:  da23ad1d5973bea8e7df69800ca2dd0a4c647ea3 
Dependencies:  #29338  Stopgaps: 
Description (last modified by )
Following #29338, the proposed branch adds 2 new methods which allows what follows:
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [3,4,5], [0,1], [2,3,4,5], [0], [1,2,3,4,5]] sage: d = dlx_solver(rows) sage: d.one_solution() [1, 0] sage: d.one_solution_using_milp_solver() [0, 1] sage: d.one_solution_using_milp_solver('Gurobi') [2, 3] sage: d.one_solution_using_milp_solver('CPLEX') [2, 3] etc.
This is based on the new method:
sage: p,x = d.to_milp() sage: p Boolean Program (no objective, 6 variables, 6 constraints) sage: x MIPVariable of dimension 1
Change History (27)
comment:1 Changed 23 months ago by
 Branch set to u/slabbe/29955
 Commit set to 8cf91eca49d83fae744d881c6be5be3858836962
 Status changed from new to needs_review
comment:2 Changed 23 months ago by
 Commit changed from 8cf91eca49d83fae744d881c6be5be3858836962 to b2f02481c09b7f54b9ad80aad5b9be493b16a22f
Branch pushed to git repo; I updated commit sha1. New commits:
b2f0248  29955: making the MILP variable indices correspond to dlx row indices

comment:3 Changed 23 months ago by
comment:4 Changed 23 months ago by
I found two issues with the doctests. I'll post them as two separate comments.
First, there is a doctest error (all the variables in the constraints are named x_
instead of x_0
, x_1
, etc.).
Running doctests with ID 202006241355511a738b74. Git branch: u/slabbe/29955 Using optional=build,cmake,cryptominisat,dochtml,glucose,pycosat,sage,sage_numerical_backends_gurobi Doctesting 1 file. sage t warnlong 44.8 dancing_links.pyx ********************************************************************** File "dancing_links.pyx", line 1037, in sage.combinat.matrices.dancing_links.dancing_linksWrapper.to_milp_solver Failed example: p.show() Expected: Maximization: <BLANKLINE> <BLANKLINE> Constraints: one 1 in 0th column: 1.0 <= x_0 + x_1 <= 1.0 one 1 in 1th column: 1.0 <= x_0 + x_2 <= 1.0 one 1 in 2th column: 1.0 <= x_0 + x_1 <= 1.0 one 1 in 3th column: 1.0 <= x_3 <= 1.0 Variables: x_0 is a boolean variable (min=0.0, max=1.0) x_1 is a boolean variable (min=0.0, max=1.0) x_2 is a boolean variable (min=0.0, max=1.0) x_3 is a boolean variable (min=0.0, max=1.0) Got: Maximization: <BLANKLINE> <BLANKLINE> Constraints: one 1 in 0th column: 1.0 <= x_ + x_ <= 1.0 one 1 in 1th column: 1.0 <= x_ + x_ <= 1.0 one 1 in 2th column: 1.0 <= x_ + x_ <= 1.0 one 1 in 3th column: 1.0 <= x_ <= 1.0 Variables: x_ = x_0 is a boolean variable (min=0.0, max=1.0) x_ = x_1 is a boolean variable (min=0.0, max=1.0) x_ = x_2 is a boolean variable (min=0.0, max=1.0) x_ = x_3 is a boolean variable (min=0.0, max=1.0) ********************************************************************** 1 item had failures: 1 of 8 in sage.combinat.matrices.dancing_links.dancing_linksWrapper.to_milp_solver [250 tests, 1 failure, 3.73 s]  sage t warnlong 44.8 dancing_links.pyx # 1 doctest failed  Total time for all tests: 3.8 seconds cpu time: 3.2 seconds cumulative wall time: 3.7 seconds
comment:5 followup: ↓ 6 Changed 23 months ago by
Second, the answer I get from the following doctest does not agree with the answer specified in the doctest.
sage: from sage.combinat.matrices.dancing_links import dlx_solver sage: rows = [[0,1,2], [0,2], [1], [3]] sage: d = dlx_solver(rows) sage: d.to_milp_solver("gurobi") (Boolean Program (no objective, 4 variables, 4 constraints), MIPVariable of dimension 1)
The doctest says the above should be:
sage: d.to_milp_solver('gurobi') # optional gurobi sage_numerical_backends_gurobi Boolean Program (no objective, 4 variables, 4 constraints)
I'm not sure why this error is not caught by the doctest system.
comment:6 in reply to: ↑ 5 Changed 23 months ago by
Replying to saliola:
I'm not sure why this error is not caught by the doctest system.
I just learned about the showskipped
option for sage t
. Since gurobi
is not a sage optional package, I had to specify it explicitly with the optional
command. If I run
sage t optional=sage,gurobi,sage_numerical_backends_gurobi dancing_links.pyx
then I see two doctest failures.
comment:7 Changed 23 months ago by
 Branch changed from u/slabbe/29955 to public/29955
 Commit changed from b2f02481c09b7f54b9ad80aad5b9be493b16a22f to 90c4d47cccbb4ad31dd4835ddf3842ee0d694cfe
I made some changes to address the second doctest problem above and I've updated the branch. Hopefully I didn't mess up....
New commits:
90c4d47  cleanup optional tags & correct doctest output

comment:8 Changed 23 months ago by
OK, it seems I was able to correctly create and set a public branch for this ticket. Any ideas on what to do for the doctest for p.show()
?
comment:9 Changed 23 months ago by
Yes indeed, I wanted to write
sage: p,x = d.to_milp_solver(solver='Gurobi') sage: p Boolean Program (no objective, 6 variables, 6 constraints) sage: x MIPVariable of dimension 1
...as you fixed it is okay as well.
On another machine running a more recent version of Sage, with the current public branch, I get:
$ sage version SageMath version 9.2.beta1, Release Date: 20200613 $ sage bt optional=sage,optional,external showskipped src/sage/combinat/matrices/dancing_links.pyx ... sage t src/sage/combinat/matrices/dancing_links.pyx 3 gurobi tests not run 0 tests not run because we ran out of time [250 tests, 2.26 s]  All tests passed!  External software detected for doctesting:
(The licence of my Gurobi licence just expired. I need to renew it.)
So the error with the x_
in the p.show()
is weird. Are you able to reproduce it on another machine?
comment:10 Changed 23 months ago by
I was using sage version 9.1rc1 because that is what the branch switched too. I'll update to the develop version and test again.
comment:11 followup: ↓ 14 Changed 23 months ago by
I figured out what is causing the error with the x_
in the p.show()
command. It is somehow caused by the sage_numerical_backends_gurobi
optional package. The error is triggered as soon as this package is installed. I am not sure how to report this problem.
comment:12 Changed 23 months ago by
 Status changed from needs_review to positive_review
comment:13 Changed 23 months ago by
Thank you so much for this Sébastien!
comment:14 in reply to: ↑ 11 ; followup: ↓ 18 Changed 23 months ago by
Replying to saliola:
I figured out what is causing the error with the
x_
in thep.show()
command. It is somehow caused by thesage_numerical_backends_gurobi
optional package. The error is triggered as soon as this package is installed. I am not sure how to report this problem.
Upstream is https://github.com/mkoeppe/sagenumericalbackendsgurobi
comment:15 Changed 23 months ago by
 Reviewers set to Franco Saliola
comment:16 Changed 23 months ago by
Thank you for your review Franco!
comment:17 Changed 23 months ago by
 Reviewers Franco Saliola deleted
Thank you. I created an issue upstream with an example that does not require this ticket; see https://github.com/mkoeppe/sagenumericalbackendsgurobi/issues/2
comment:18 in reply to: ↑ 14 Changed 23 months ago by
Replying to mkoeppe:
I just created https://github.com/mkoeppe/sagenumericalbackendsgurobi/issues/3
comment:19 Changed 23 months ago by
oups, we did the same thing at the same time!
comment:20 Changed 23 months ago by
 Reviewers set to Franco Saliola
comment:21 Changed 23 months ago by
 Cc slelievre added
 Description modified (diff)
comment:22 Changed 23 months ago by
A quick comment. I think to_milp_solver
should be renamed to to_milp
. In terminology of sage.numerical.mip
, "solver" would be an instance of a subclass of GenericBackend
.
comment:23 Changed 23 months ago by
 Commit changed from 90c4d47cccbb4ad31dd4835ddf3842ee0d694cfe to da23ad1d5973bea8e7df69800ca2dd0a4c647ea3
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
da23ad1  29955:to_milp_solver > to_milp

comment:24 Changed 23 months ago by
I agree. I just did a commit. Hoping that Volker did not started to merge that ticket while it was on positive review status. Needs review.
comment:25 Changed 23 months ago by
 Reviewers changed from Franco Saliola to Franco Saliola, Matthias Koeppe
 Status changed from needs_review to positive_review
comment:26 Changed 23 months ago by
 Description modified (diff)
comment:27 Changed 23 months ago by
 Branch changed from public/29955 to da23ad1d5973bea8e7df69800ca2dd0a4c647ea3
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
29338: reduction from DLX to SAT
29338:return None if no solution found
29955: reduction from DLX to MILP