Reduction from dancing links instance to MILP instance

[seblabbe]

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 

Depends on #29338

CC: @slel

Component: combinatorics

Author: Sébastien Labbé

Branch/Commit: da23ad1

Reviewer: Franco Saliola, Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/29955

[seblabbe]

New commits:

542c3fc	29338: reduction from DLX to SAT
2e97345	29338:return None if no solution found
8cf91ec	29955: reduction from DLX to MILP

[seblabbe]

Commit: 8cf91ec

[seblabbe]

Branch: u/slabbe/29955

[sagetrac-git]

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

b2f0248

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

[sagetrac-git]

Changed commit from 8cf91ec to b2f0248

[seblabbe]

Author: Sébastien Labbé

[saliola]

comment:4

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

[saliola]

comment:5

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.

[saliola]

comment:6

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.

[saliola]

comment:7

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

[saliola]

Changed commit from b2f0248 to 90c4d47

[saliola]

Changed branch from u/slabbe/29955 to public/29955

[saliola]

comment:8

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()?

[seblabbe]

comment:9

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?

[saliola]

comment:10

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.

[saliola]

comment:11

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.

[saliola]

comment:13

Thank you so much for this Sébastien!

[mkoeppe]

comment:14

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

[mkoeppe]

Reviewer: Franco Saliola

[seblabbe]

comment:16

Thank you for your review Franco!

[saliola]

comment:17

Thank you. I created an issue upstream with an example that does not require this ticket; see sagemath/sage-numerical-backends-gurobi#2

[saliola]

Changed reviewer from Franco Saliola to none

[seblabbe]

comment:18

Replying to @mkoeppe:

I just created
sagemath/sage-numerical-backends-gurobi#3

[seblabbe]

comment:19

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

[seblabbe]

Reviewer: Franco Saliola

[mkoeppe]

comment:22

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.

[sagetrac-git]

Changed commit from 90c4d47 to da23ad1

[sagetrac-git]

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

[seblabbe]

comment:24

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.

[mkoeppe]

Changed reviewer from Franco Saliola to Franco Saliola, Matthias Koeppe

[vbraun]

Changed branch from public/29955 to da23ad1