Opened 4 years ago

Closed 4 years ago

#20446 closed enhancement (fixed)

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

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

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

Change History (27)

comment:1 Changed 4 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 4 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 4 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 4 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 4 years ago by dimpase

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

comment:6 Changed 4 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 4 years ago by mkoeppe

  • Milestone changed from sage-wishlist to sage-7.2

comment:8 Changed 4 years ago by mkoeppe

  • Description modified (diff)

comment:9 Changed 4 years ago by mkoeppe

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

comment:10 Changed 4 years ago by dimpase

I get a merge conflict with #20414 here.

comment:11 Changed 4 years ago by mkoeppe

Seems to merge cleanly here.

comment:12 Changed 4 years ago by 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

comment:13 Changed 4 years ago by 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

comment:14 Changed 4 years ago by mkoeppe

Ah, that's #20406.

comment:15 Changed 4 years ago by git

  • Commit changed from e7a2bd7d86034b16c8407ae534d75c39956edbf4 to 39a902f337bcdc4e53141e89f80bab289f6ba016

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
d1d84c6get_solver: Add doctest
cc2d999Mention solver=callable in docstrings and error messages
37e87a5Replace delsarte test by one that does not expose a bug in GLPK exact
68f9a57Merge branch 'get_solver_factory' into 7.2.beta4+lpfixes
149056dMerge branch 'u/mkoeppe/common_testsuite_for_mip_backends' into 7.2.beta4+lpfixes
bfa4616GLPKExactBackend: New
39a902fClean up some MIP backend docstrings

comment:16 Changed 4 years ago by mkoeppe

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

comment:17 Changed 4 years ago by 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

comment:18 Changed 4 years ago by git

  • Commit changed from 39a902f337bcdc4e53141e89f80bab289f6ba016 to 550a5c39f99b98c92ad81b392ccca2c7a50efa50

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

550a5c3Add missing .pxd file

comment:19 Changed 4 years ago by mkoeppe

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

comment:20 Changed 4 years ago by 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...

comment:21 Changed 4 years ago by git

  • Commit changed from 550a5c39f99b98c92ad81b392ccca2c7a50efa50 to c0fa6b4919b236a385b66975e91c43b419aafd36

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

c0fa6b4MIP backends: Documentation updates, add to index

comment:22 Changed 4 years ago by dimpase

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

OK, good.

comment:23 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work
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]

comment:24 Changed 4 years ago by git

  • Commit changed from c0fa6b4919b236a385b66975e91c43b419aafd36 to 8fc11ea544a0b46cf8af427fcd58ac5bc7eec816

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

4e1f368GLPKExactBackend: New
fe06f11Clean up some MIP backend docstrings
2e13284Add missing .pxd file
064f1c2MIP backends: Documentation updates, add to index
8fc11eaMake __copy__ methods work in subclassed backends

comment:25 Changed 4 years ago by mkoeppe

  • Status changed from needs_work to needs_review

Nice, the new testsuite actually works.

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

comment:26 Changed 4 years ago by dimpase

  • Status changed from needs_review to positive_review

comment:27 Changed 4 years ago by vbraun

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