Opened 2 years ago
Closed 2 years ago
#29955 closed enhancement (fixed)
Reduction from dancing links instance to MILP instance
Reported by:  Sébastien Labbé  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  combinatorics  Keywords:  
Cc:  Samuel Lelièvre  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 2 years ago by
Branch:  → u/slabbe/29955 

Commit:  → 8cf91eca49d83fae744d881c6be5be3858836962 
Status:  new → needs_review 
comment:2 Changed 2 years ago by
Commit:  8cf91eca49d83fae744d881c6be5be3858836962 → 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 2 years ago by
Authors:  → Sébastien Labbé 

comment:4 Changed 2 years 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 2 years 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 Changed 2 years 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 2 years ago by
Branch:  u/slabbe/29955 → public/29955 

Commit:  b2f02481c09b7f54b9ad80aad5b9be493b16a22f → 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 2 years 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 2 years 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 2 years 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 2 years 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 2 years ago by
Status:  needs_review → positive_review 

comment:14 followup: 18 Changed 2 years 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 2 years ago by
Reviewers:  → Franco Saliola 

comment:17 Changed 2 years ago by
Reviewers:  Franco Saliola 

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 Changed 2 years ago by
Replying to mkoeppe:
I just created https://github.com/mkoeppe/sagenumericalbackendsgurobi/issues/3
comment:20 Changed 2 years ago by
Reviewers:  → Franco Saliola 

comment:21 Changed 2 years ago by
Cc:  Samuel Lelièvre added 

Description:  modified (diff) 
comment:22 Changed 2 years 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 2 years ago by
Commit:  90c4d47cccbb4ad31dd4835ddf3842ee0d694cfe → da23ad1d5973bea8e7df69800ca2dd0a4c647ea3 

Status:  positive_review → 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 2 years 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 2 years ago by
Reviewers:  Franco Saliola → Franco Saliola, Matthias Koeppe 

Status:  needs_review → positive_review 
comment:26 Changed 2 years ago by
Description:  modified (diff) 

comment:27 Changed 2 years ago by
Branch:  public/29955 → da23ad1d5973bea8e7df69800ca2dd0a4c647ea3 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
29338: reduction from DLX to SAT
29338:return None if no solution found
29955: reduction from DLX to MILP