GLPKExactBackend - a variation on GLPKBackend that sets a solver parameter and signals errors on integer variables

[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)
3
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
...
2

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"

[mkoeppe]

Branch is on top of #20323.

---

Last 10 new commits:

​e70a97b	More _test_... functions
​0a76184	get_solver: Make doctest work no matter whether backends are Python or Sage objects
​a6f0f4d	Run testsuite with all MIP backends
​0bd7a87	GenericBackend._test_add_variables(): Add tests from CVXOPTBackend
​6b55e16	Add a classmethod _test_solve
​e14afd3	GenericBackend._test_solve: Finish
​48b9fe5	Change from mutating instance _test methods to class methods
​5394729	New method _test_ncols_nonnegative
​7138fa0	GenericBackend: Remove failing _test methods from this ticket to make the patchbot and its friends happy
​07266d7	GLPKExactBackend: New

[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`.

[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")

[dimpase]

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

[git]

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

​e7a2bd7

Clean up some MIP backend docstrings

[mkoeppe]

It's ready for review, with the intent of having it merged. I've created a new ticket for an additional wishlist item.

[dimpase]

I get a merge conflict with #20414 here.

[mkoeppe]

Seems to merge cleanly here.

[dimpase]

here is what I see in backends/generic_backend.pyx

<<<<<<< HEAD
        raise ValueError("'solver' should be set to 'GLPK', 'Coin', 'CPLEX', 'CVXOPT', 'Gurobi', 'PPL', 'InteractiveLP', None (in which case the default one is used), or a callable.")
=======
        raise ValueError("'solver' should be set to 'GLPK', 'GLPK/exact', 'Coin', 'CPLEX', 'CVXOPT', 'Gurobi', 'PPL', 'InteractiveLP', or None (in which case the default one is used).")
>>>>>>> e7a2bd7d86034b16c8407ae534d75c39956edbf4

[dimpase]

It's this commit:

commit cc2d999c5234040914a4fee66708f33124eef8a9
Author: Matthias Koeppe <mkoeppe@math.ucdavis.edu>
Date:   Thu Apr 14 10:19:22 2016 -0700

    Mention solver=callable in docstrings and error messages

that causes the clash

[mkoeppe]

Ah, that's #20406.

[git]

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

​623a2e2	get_solver: Allow a callable as the solver argument
​09377ac	MixedIntegerLinearProgram.__copy__: Don't create a throw-away GLPK instance
​d1d84c6	get_solver: Add doctest
​cc2d999	Mention solver=callable in docstrings and error messages
​37e87a5	Replace delsarte test by one that does not expose a bug in GLPK exact
​68f9a57	Merge branch 'get_solver_factory' into 7.2.beta4+lpfixes
​149056d	Merge branch 'u/mkoeppe/common_testsuite_for_mip_backends' into 7.2.beta4+lpfixes
​bfa4616	GLPKExactBackend: New
​39a902f	Clean up some MIP backend docstrings

[mkoeppe]

OK, rebased on top of 7.2.beta4 + #20406 + #20323.

[dimpase]

more commits missing? I am trying your branch on top of 7.2.beta4:

Error compiling Cython file:
------------------------------------------------------------
...
#  Distributed under the terms of the GNU General Public License (GPL)
#  The full text of the GPL is available at:
#                  http://www.gnu.org/licenses/
##############################################################################

cdef class GLPKExactBackend(GLPKBackend):
    ^
------------------------------------------------------------

sage/numerical/backends/glpk_exact_backend.pyx:17:5: 'GLPKBackend' is not declared

Error compiling Cython file:
------------------------------------------------------------
...
            ...
            ValueError: GLPK/exact only supports continuous variables
        """
        if binary or integer:
            raise ValueError("GLPK/exact only supports continuous variables")
        return GLPKBackend.add_variable(self, lower_bound, upper_bound, binary, continuous,
                         ^
------------------------------------------------------------

sage/numerical/backends/glpk_exact_backend.pyx:109:26: undeclared name not builtin: GLPKBackend

[git]

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

​550a5c3

Add missing .pxd file

[mkoeppe]

Yes, you were missing this file that I forgot to check in! Apologies...

[dimpase]

your new backends are not listed in this index: local/share/doc/sage/html/en/reference/numerical/index.html which is produced from src/doc/en/reference/numerical/index.rst

please add them all...

[git]

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

​c0fa6b4

MIP backends: Documentation updates, add to index

[dimpase]

OK, good.

[vbraun]

sage -t --long src/sage/numerical/backends/glpk_exact_backend.pyx
**********************************************************************
File "src/sage/numerical/backends/glpk_exact_backend.pyx", line 33, in sage.numerical.backends.glpk_exact_backend.GLPKExactBackend
Failed example:
    TestSuite(p.get_backend()).run(skip="_test_pickling")
Expected nothing
Got:
    Failure in _test_copy:
    Traceback (most recent call last):
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/misc/sage_unittest.py", line 283, in run
        test_method(tester = tester)
      File "sage/numerical/backends/generic_backend.pyx", line 1127, in sage.numerical.backends.generic_backend.GenericBackend._test_copy (/mnt/disk/home/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/numerical/backends/generic_backend.c:10824)
        self._do_test_problem_data(tester, cp)
      File "sage/numerical/backends/generic_backend.pyx", line 1095, in sage.numerical.backends.generic_backend.GenericBackend._do_test_problem_data (/mnt/disk/home/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/numerical/backends/generic_backend.c:10504)
        tester.assertEqual(type(self), type(cp),
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python/unittest/case.py", line 515, in assertEqual
        assertion_func(first, second, msg=msg)
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python/unittest/case.py", line 508, in _baseAssertEqual
        raise self.failureException(msg)
    AssertionError: Classes do not match
    ------------------------------------------------------------
    Failure in _test_copy_does_not_share_data:
    Traceback (most recent call last):
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/misc/sage_unittest.py", line 283, in run
        test_method(tester = tester)
      File "sage/numerical/backends/generic_backend.pyx", line 1137, in sage.numerical.backends.generic_backend.GenericBackend._test_copy_does_not_share_data (/mnt/disk/home/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/numerical/backends/generic_backend.c:11033)
        self._do_test_problem_data(tester, cpcp)
      File "sage/numerical/backends/generic_backend.pyx", line 1095, in sage.numerical.backends.generic_backend.GenericBackend._do_test_problem_data (/mnt/disk/home/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/numerical/backends/generic_backend.c:10504)
        tester.assertEqual(type(self), type(cp),
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python/unittest/case.py", line 515, in assertEqual
        assertion_func(first, second, msg=msg)
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python/unittest/case.py", line 508, in _baseAssertEqual
        raise self.failureException(msg)
    AssertionError: Classes do not match
    ------------------------------------------------------------
    Failure in _test_copy_some_mips:
    Traceback (most recent call last):
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/misc/sage_unittest.py", line 283, in run
        test_method(tester = tester)
      File "sage/numerical/backends/generic_backend.pyx", line 1151, in sage.numerical.backends.generic_backend.GenericBackend._test_copy_some_mips (/mnt/disk/home/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/numerical/backends/generic_backend.c:11276)
        p._test_copy(**options)
      File "sage/numerical/backends/generic_backend.pyx", line 1127, in sage.numerical.backends.generic_backend.GenericBackend._test_copy (/mnt/disk/home/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/numerical/backends/generic_backend.c:10824)
        self._do_test_problem_data(tester, cp)
      File "sage/numerical/backends/generic_backend.pyx", line 1095, in sage.numerical.backends.generic_backend.GenericBackend._do_test_problem_data (/mnt/disk/home/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/numerical/backends/generic_backend.c:10504)
        tester.assertEqual(type(self), type(cp),
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python/unittest/case.py", line 515, in assertEqual
        assertion_func(first, second, msg=msg)
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python/unittest/case.py", line 508, in _baseAssertEqual
        raise self.failureException(msg)
    AssertionError: Classes do not match
    ------------------------------------------------------------
    The following tests failed: _test_copy, _test_copy_does_not_share_data, _test_copy_some_mips
**********************************************************************
1 item had failures:
   1 of   3 in sage.numerical.backends.glpk_exact_backend.GLPKExactBackend
    [26 tests, 1 failure, 0.12 s]

[git]

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

​4e1f368	GLPKExactBackend: New
​fe06f11	Clean up some MIP backend docstrings
​2e13284	Add missing .pxd file
​064f1c2	MIP backends: Documentation updates, add to index
​8fc11ea	Make __copy__ methods work in subclassed backends

[mkoeppe]

Nice, the new testsuite actually works.

Fixed copying of GLPKExactBackend instances. Rebased on 7.2.beta5.