Opened 7 years ago

Closed 7 years ago

#20406 closed enhancement (fixed)

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

Reported by: Matthias Köppe Owned by:
Priority: major Milestone: sage-7.2
Component: numerical Keywords: lp
Cc: Dima Pasechnik, Vincent Delecroix, Volker Braun, Jeroen Demeyer Merged in:
Authors: Matthias Koeppe Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 37e87a5 (Commits, GitHub, GitLab) Commit: 37e87a5df7de14853e63074e0d07d678e61b1029
Dependencies: Stopgaps:

Status badges

Description (last modified by Matthias Köppe)

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 7 years ago by Matthias Köppe

Branch: u/mkoeppe/get_solver_factory

comment:2 Changed 7 years ago by Matthias Köppe

Authors: Matthias Koeppe
Cc: Dima Pasechnik Vincent Delecroix added
Commit: b4146a786814506fda760abd4dd25b5793c7ce68
Description: modified (diff)

New commits:

b4146a7get_solver: Allow a callable as the solver argument

comment:3 Changed 7 years ago by Matthias Köppe

Description: modified (diff)
Status: newneeds_review

comment:4 Changed 7 years ago by Matthias Köppe

Cc: Volker Braun Jeroen Demeyer added

comment:5 Changed 7 years ago by git

Commit: b4146a786814506fda760abd4dd25b5793c7ce68d9ce11ecc6e0867d3877632666a12c5ebf3b17ec

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

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

comment:6 Changed 7 years ago by Dima Pasechnik

Status: needs_reviewneeds_work

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

comment:7 Changed 7 years ago by git

Commit: d9ce11ecc6e0867d3877632666a12c5ebf3b17ec09377ac96d08efa39b9148a690fe19bd33b8a07a

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 7 years ago by Matthias Köppe

Rebased on 7.2.beta4

comment:9 Changed 7 years ago by Matthias Köppe

Status: needs_workneeds_review

comment:10 Changed 7 years ago by Dima Pasechnik

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 7 years ago by git

Commit: 09377ac96d08efa39b9148a690fe19bd33b8a07acc2d999c5234040914a4fee66708f33124eef8a9

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 7 years ago by Dima Pasechnik

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 7 years ago by Dima Pasechnik (previous) (diff)

comment:13 Changed 7 years ago by Matthias Köppe

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

comment:14 Changed 7 years ago by Dima Pasechnik

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 7 years ago by Dima Pasechnik

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 7 years ago by Dima Pasechnik (previous) (diff)

comment:16 Changed 7 years ago by git

Commit: cc2d999c5234040914a4fee66708f33124eef8a937e87a5df7de14853e63074e0d07d678e61b1029

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 7 years ago by Matthias Köppe

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

comment:18 Changed 7 years ago by Matthias Köppe

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

comment:19 Changed 7 years ago by Dima Pasechnik

Reviewers: Dima Pasechnik
Status: needs_reviewpositive_review

OK!

comment:20 Changed 7 years ago by Volker Braun

Branch: u/mkoeppe/get_solver_factory37e87a5df7de14853e63074e0d07d678e61b1029
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.