Opened 6 years ago

Last modified 6 years ago

#20446 closed enhancement

GLPKExactBackend - a variation on GLPKBackend that sets a solver parameter and signals errors on integer variables — at Version 8

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-7.2
Component: numerical Keywords: lp
Cc: dimpase, vdelecroix Merged in:
Authors: Matthias Koeppe Reviewers:
Report Upstream: N/A Work issues:
Branch: u/mkoeppe/glpkexactbackend___a_variation_on_glpkbackend_that_sets_a_solver_parameter_and_signals_errors_on_integer_variables (Commits, GitHub, GitLab) Commit: e7a2bd7d86034b16c8407ae534d75c39956edbf4
Dependencies: Stopgaps:

Status badges

Description (last modified by mkoeppe)

GLPK has an exact simplex method, which can be requested by setting a solver parameter. Via #20406, a user can set this parameter.

It would be more convenient to define a named backend that does that.

Also, setting the solver parameter actually causes GLPK to solve the continuous relaxation, ignoring all integer variables. This might be surprising to users.

sage: delsarte_bound_additive_hamming_space(19,15,7,isinteger=True)
sage: from sage.numerical.backends.generic_backend import get_solver
sage: def glpk_exact_solver():                                               
        b = get_solver(solver="GLPK")
        b.solver_parameter("simplex_or_intopt", "exact_simplex_only")
        return b
sage: delsarte_bound_additive_hamming_space(19,15,7,solver=glpk_exact_solver,isinteger=True)
glp_exact: 54 rows, 20 columns, 795 non-zeros

So there would be value in a named backend that actually signals an error when the user requests integer variables (like the CVXOpt and InteractiveLP backends do).

sage: delsarte_bound_additive_hamming_space(19,15,7,solver="GLPK/exact",isinteger=True)
ValueError: This backend does not handle integer variables

Follow-up wishlist item: #20458: GLPKBackend/GLPKExactBackend: Support "glp_simplex followed by glp_exact"

Change History (8)

comment:1 Changed 6 years ago by mkoeppe

  • Branch set to u/mkoeppe/glpkexactbackend___a_variation_on_glpkbackend_that_sets_a_solver_parameter_and_signals_errors_on_integer_variables

comment:2 Changed 6 years ago by mkoeppe

  • Authors set to Matthias Koeppe
  • Commit set to 07266d71797ff836515cf929c9e6aa6f70fa65a3
  • Status changed from new to needs_review

Branch is on top of #20323.

Last 10 new commits:

e70a97bMore _test_... functions
0a76184get_solver: Make doctest work no matter whether backends are Python or Sage objects
a6f0f4dRun testsuite with all MIP backends
0bd7a87GenericBackend._test_add_variables(): Add tests from CVXOPTBackend
6b55e16Add a classmethod _test_solve
e14afd3GenericBackend._test_solve: Finish
48b9fe5Change from mutating instance _test methods to class methods
5394729New method _test_ncols_nonnegative
7138fa0GenericBackend: Remove failing _test methods from this ticket to make the patchbot and its friends happy
07266d7GLPKExactBackend: New

comment:3 Changed 6 years ago by dimpase

the docstring is not correct here:

+    def _test_add_linear_constraint_vector(cls, tester=None, **options):
+        """
+        Run tests on the method :meth:`.add_linear_constraints`.

comment:4 Changed 6 years ago by dimpase

indentation here is weird:

cdef class PPLBackend(GenericBackend):
+    """
+    TESTS::
+            sage: from sage.numerical.backends.generic_backend import get_solver
+            sage: p = get_solver(solver = "PPL")
+            sage: TestSuite(p).run(skip="_test_pickling")

comment:5 Changed 6 years ago by dimpase

do we plan on having this merged, or "wishlist" means something elese?

comment:6 Changed 6 years ago by git

  • Commit changed from 07266d71797ff836515cf929c9e6aa6f70fa65a3 to e7a2bd7d86034b16c8407ae534d75c39956edbf4

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

e7a2bd7Clean up some MIP backend docstrings

comment:7 Changed 6 years ago by mkoeppe

  • Milestone changed from sage-wishlist to sage-7.2

comment:8 Changed 6 years ago by mkoeppe

  • Description modified (diff)
Note: See TracTickets for help on using tickets.