#29955 closed enhancement (fixed)

Reduction from dancing links instance to MILP instance

Reported by: slabbe Owned by:
Priority: major Milestone: sage-9.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:

Status badges

Description (last modified by slabbe)

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 16 months ago by slabbe

  • Branch set to u/slabbe/29955
  • Commit set to 8cf91eca49d83fae744d881c6be5be3858836962
  • Status changed from new to needs_review

New commits:

542c3fc29338: reduction from DLX to SAT
2e9734529338:return None if no solution found
8cf91ec29955: reduction from DLX to MILP

comment:2 Changed 16 months ago by git

  • Commit changed from 8cf91eca49d83fae744d881c6be5be3858836962 to b2f02481c09b7f54b9ad80aad5b9be493b16a22f

Branch pushed to git repo; I updated commit sha1. New commits:

b2f024829955: making the MILP variable indices correspond to dlx row indices

comment:3 Changed 16 months ago by slabbe

  • Authors set to Sébastien Labbé

comment:4 Changed 16 months ago by saliola

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 2020-06-24-13-55-51-1a738b74.
Git branch: u/slabbe/29955
Using --optional=build,cmake,cryptominisat,dochtml,glucose,pycosat,sage,sage_numerical_backends_gurobi
Doctesting 1 file.
sage -t --warn-long 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 0-th column: 1.0 <= x_0 + x_1 <= 1.0
      one 1 in 1-th column: 1.0 <= x_0 + x_2 <= 1.0
      one 1 in 2-th column: 1.0 <= x_0 + x_1 <= 1.0
      one 1 in 3-th 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 0-th column: 1.0 <= x_ + x_ <= 1.0
      one 1 in 1-th column: 1.0 <= x_ + x_ <= 1.0
      one 1 in 2-th column: 1.0 <= x_ + x_ <= 1.0
      one 1 in 3-th 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 --warn-long 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 follow-up: Changed 16 months ago by saliola

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 16 months ago by saliola

Replying to saliola:

I'm not sure why this error is not caught by the doctest system.

I just learned about the --show-skipped 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 16 months ago by saliola

  • 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:

90c4d47cleanup optional tags & correct doctest output

comment:8 Changed 16 months ago by saliola

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 16 months ago by slabbe

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: 2020-06-13
$ sage -bt --optional=sage,optional,external --show-skipped 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 16 months ago by saliola

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 follow-up: Changed 16 months ago by saliola

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 16 months ago by saliola

  • Status changed from needs_review to positive_review

comment:13 Changed 16 months ago by saliola

Thank you so much for this Sébastien!

comment:14 in reply to: ↑ 11 ; follow-up: Changed 16 months ago by mkoeppe

Replying to saliola:

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.

Upstream is https://github.com/mkoeppe/sage-numerical-backends-gurobi

comment:15 Changed 16 months ago by mkoeppe

  • Reviewers set to Franco Saliola

comment:16 Changed 16 months ago by slabbe

Thank you for your review Franco!

comment:17 Changed 16 months ago by saliola

  • 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/sage-numerical-backends-gurobi/issues/2

comment:19 Changed 16 months ago by slabbe

oups, we did the same thing at the same time!

comment:20 Changed 16 months ago by slabbe

  • Reviewers set to Franco Saliola

comment:21 Changed 16 months ago by slelievre

  • Cc slelievre added
  • Description modified (diff)

comment:22 Changed 16 months ago by mkoeppe

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 16 months ago by git

  • 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:

da23ad129955:to_milp_solver -> to_milp

comment:24 Changed 16 months ago by slabbe

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 16 months ago by mkoeppe

  • Reviewers changed from Franco Saliola to Franco Saliola, Matthias Koeppe
  • Status changed from needs_review to positive_review

comment:26 Changed 16 months ago by slabbe

  • Description modified (diff)

comment:27 Changed 16 months ago by vbraun

  • Branch changed from public/29955 to da23ad1d5973bea8e7df69800ca2dd0a4c647ea3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.