Opened 5 years ago
Closed 5 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, GitHub, GitLab) | Commit: | 8fc11ea544a0b46cf8af427fcd58ac5bc7eec816 |
Dependencies: | Stopgaps: |
Description (last modified by )
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 5 years ago by
- Branch set to u/mkoeppe/glpkexactbackend___a_variation_on_glpkbackend_that_sets_a_solver_parameter_and_signals_errors_on_integer_variables
comment:2 Changed 5 years ago by
- Commit set to 07266d71797ff836515cf929c9e6aa6f70fa65a3
- Status changed from new to needs_review
comment:3 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
do we plan on having this merged, or "wishlist" means something elese?
comment:6 Changed 5 years ago by
- Commit changed from 07266d71797ff836515cf929c9e6aa6f70fa65a3 to e7a2bd7d86034b16c8407ae534d75c39956edbf4
Branch pushed to git repo; I updated commit sha1. New commits:
e7a2bd7 | Clean up some MIP backend docstrings
|
comment:7 Changed 5 years ago by
- Milestone changed from sage-wishlist to sage-7.2
comment:8 Changed 5 years ago by
- Description modified (diff)
comment:9 Changed 5 years ago by
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 5 years ago by
I get a merge conflict with #20414 here.
comment:11 Changed 5 years ago by
Seems to merge cleanly here.
comment:12 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
Ah, that's #20406.
comment:15 Changed 5 years ago by
- Commit changed from e7a2bd7d86034b16c8407ae534d75c39956edbf4 to 39a902f337bcdc4e53141e89f80bab289f6ba016
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
|
comment:16 Changed 5 years ago by
comment:17 Changed 5 years ago by
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 5 years ago by
- Commit changed from 39a902f337bcdc4e53141e89f80bab289f6ba016 to 550a5c39f99b98c92ad81b392ccca2c7a50efa50
Branch pushed to git repo; I updated commit sha1. New commits:
550a5c3 | Add missing .pxd file
|
comment:19 Changed 5 years ago by
Yes, you were missing this file that I forgot to check in! Apologies...
comment:20 Changed 5 years ago by
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 5 years ago by
- Commit changed from 550a5c39f99b98c92ad81b392ccca2c7a50efa50 to c0fa6b4919b236a385b66975e91c43b419aafd36
Branch pushed to git repo; I updated commit sha1. New commits:
c0fa6b4 | MIP backends: Documentation updates, add to index
|
comment:22 Changed 5 years ago by
- Reviewers set to Dima Pasechnik
- Status changed from needs_review to positive_review
OK, good.
comment:23 Changed 5 years ago by
- 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 5 years ago by
- Commit changed from c0fa6b4919b236a385b66975e91c43b419aafd36 to 8fc11ea544a0b46cf8af427fcd58ac5bc7eec816
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
|
comment:25 Changed 5 years ago by
- 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 5 years ago by
- Status changed from needs_review to positive_review
comment:27 Changed 5 years ago by
- 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
Branch is on top of #20323.
Last 10 new commits:
More _test_... functions
get_solver: Make doctest work no matter whether backends are Python or Sage objects
Run testsuite with all MIP backends
GenericBackend._test_add_variables(): Add tests from CVXOPTBackend
Add a classmethod _test_solve
GenericBackend._test_solve: Finish
Change from mutating instance _test methods to class methods
New method _test_ncols_nonnegative
GenericBackend: Remove failing _test methods from this ticket to make the patchbot and its friends happy
GLPKExactBackend: New