Opened 3 years ago

Closed 3 years ago

#20406 closed enhancement (fixed)

get_solver should allow passing a function (a solver factory) as the solver argument

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-7.2
Component: numerical Keywords: lp
Cc: dimpase, vdelecroix, vbraun, jdemeyer Merged in:
Authors: Matthias Koeppe Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 37e87a5 (Commits) Commit: 37e87a5df7de14853e63074e0d07d678e61b1029
Dependencies: Stopgaps:

Description (last modified by mkoeppe)

For example, to use GLPK's exact simplex algorithm:

from sage.numerical.backends.generic_backend import get_solver
def glpk_exact_solver():
    b = get_solver(solver="GLPK")
    b.solver_parameter("simplex_or_intopt", "exact_simplex_only")
    return b

delsarte_bound_additive_hamming_space(19,15,7,solver=glpk_exact_solver)

Change History (20)

comment:1 Changed 3 years ago by mkoeppe

  • Branch set to u/mkoeppe/get_solver_factory

comment:2 Changed 3 years ago by mkoeppe

  • Authors set to Matthias Koeppe
  • Cc dimpase vdelecroix added
  • Commit set to b4146a786814506fda760abd4dd25b5793c7ce68
  • Description modified (diff)

New commits:

b4146a7get_solver: Allow a callable as the solver argument

comment:3 Changed 3 years ago by mkoeppe

  • Description modified (diff)
  • Status changed from new to needs_review

comment:4 Changed 3 years ago by mkoeppe

  • Cc vbraun jdemeyer added

comment:5 Changed 3 years ago by git

  • Commit changed from b4146a786814506fda760abd4dd25b5793c7ce68 to d9ce11ecc6e0867d3877632666a12c5ebf3b17ec

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

d9ce11eMixedIntegerLinearProgram.__copy__: Don't create a throw-away GLPK instance

comment:6 Changed 3 years ago by dimpase

  • Status changed from needs_review to needs_work

this also needs a rebase (sorry for sitting on this too long...)

comment:7 Changed 3 years ago by git

  • Commit changed from d9ce11ecc6e0867d3877632666a12c5ebf3b17ec to 09377ac96d08efa39b9148a690fe19bd33b8a07a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

623a2e2get_solver: Allow a callable as the solver argument
09377acMixedIntegerLinearProgram.__copy__: Don't create a throw-away GLPK instance

comment:8 Changed 3 years ago by mkoeppe

Rebased on 7.2.beta4

comment:9 Changed 3 years ago by mkoeppe

  • Status changed from needs_work to needs_review

comment:10 Changed 3 years ago by dimpase

without the example in the ticket description it's hard to get the idea of this change. Can you add this example into the code?

comment:11 Changed 3 years ago by git

  • Commit changed from 09377ac96d08efa39b9148a690fe19bd33b8a07a to cc2d999c5234040914a4fee66708f33124eef8a9

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

d1d84c6get_solver: Add doctest
cc2d999Mention solver=callable in docstrings and error messages

comment:12 Changed 3 years ago by dimpase

the doctest in the commit d1d84c6 appears to demonstrate a bug in the ILP solver of GLPK. The correct answer should be 3, not 2. Indeed, look at the entry n=19, k=2 in http://www.codetables.de/BKLC/Tables.php?q=7&n0=1&n1=100&k0=1&k1=100; it is 16, not 15.

(one also gets 3 when using PPL's ILP solver)

Last edited 3 years ago by dimpase (previous) (diff)

comment:13 Changed 3 years ago by mkoeppe

GLPK has an exact simplex, not an exact MIP solver. See #20446

comment:14 Changed 3 years ago by dimpase

anyhow, this answer by GLPK is wrong, ILP or LP! (the bound obtained by solving LP cannot be smaller than the one obtained from ILP)

sage: delsarte_bound_additive_hamming_space(19,15,7,isinteger=True) # ppl used
3
sage: delsarte_bound_additive_hamming_space(19,15,7) # ppl used
3

comment:15 Changed 3 years ago by dimpase

sage: a,p,v=delsarte_bound_additive_hamming_space(19,15,7,solver=glpk_exact_solver,return_data=True)
...
sage:  [ZZ(j) for i,j in p.get_values(a).iteritems()]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 48, 0, 0, 0, 0]

I need to do ZZ as otherwise it outputs floats. This is a maximization (of the sum of the coordinates) LP, and the following vector (computed by PPL) should be feasible, too:

[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 307, 0, 0, 1, 34]
Last edited 3 years ago by dimpase (previous) (diff)

comment:16 Changed 3 years ago by git

  • Commit changed from cc2d999c5234040914a4fee66708f33124eef8a9 to 37e87a5df7de14853e63074e0d07d678e61b1029

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

37e87a5Replace delsarte test by one that does not expose a bug in GLPK exact

comment:17 Changed 3 years ago by mkoeppe

To move this ticket forward, I have replaced the test by something else

comment:18 Changed 3 years ago by mkoeppe

The wrong result is now the subject of ticket #20447.

comment:19 Changed 3 years ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

OK!

comment:20 Changed 3 years ago by vbraun

  • Branch changed from u/mkoeppe/get_solver_factory to 37e87a5df7de14853e63074e0d07d678e61b1029
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.