Opened 5 years ago
Closed 5 years ago
#20323 closed enhancement (fixed)
Common TestSuite for MIP backends
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage7.2 
Component:  numerical  Keywords:  lp 
Cc:  dimpase, ncohen, vdelecroix, vbraun, nthiery  Merged in:  
Authors:  Matthias Koeppe  Reviewers:  Thierry Monteil, Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  7138fa0 (Commits, GitHub, GitLab)  Commit:  7138fa03a951cf62d970bf346893499fe8fd3daa 
Dependencies:  #20326  Stopgaps: 
Description (last modified by )
The MIP backends should be tested using a common TestSuite
. Right now each backend uses its own doctests, which have slightly diverged from each other, so there is nothing (other than the fact that they were the result of copypaste from each other) that ensures consistency. (#20296 fixes several wrong doctests in GenericBackend
, from which I tried to copypaste, for example.)
Change History (46)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
 Branch set to u/mkoeppe/common_testsuite_for_mip_backends
comment:3 Changed 5 years ago by
 Cc nthiery added
 Commit set to f5f69bd5500538071542b3f85d53771c476b10cc
Not ready for review yet, but I'm hoping that perhaps someone familiar with the TestSuite
mechanism could tell me whether I'm on the right track with this initial patch on this ticket.
New commits:
f5f69bd  Use TestSuite for testing MIP backends

comment:4 followup: ↓ 5 Changed 5 years ago by
It looks like you are. Any method that starts with _test
gets run by TestSuite
. Although I am not really in favor of any test mutating the object in question.
Also, is there a reason why GenericBackend
needs to inherit from SageObject
(as opposed to just the Python object
)? I am pretty sure this is strictly needed...
comment:5 in reply to: ↑ 4 Changed 5 years ago by
Thanks for taking a look, Travis.
Replying to tscrim:
Also, is there a reason why
GenericBackend
needs to inherit fromSageObject
(as opposed to just the Pythonobject
)?
SageObject
provides some of the basic testing infrastructure, such as ._test_not_implemented_methods
.
Well, there's also sage.misc.sage_unittest.PythonObjectWithTests
, but I can't seem to cimport
it to make it a base class of GenericBackend
. So I guess I'll stick with SageObject
.
comment:6 Changed 5 years ago by
 Commit changed from f5f69bd5500538071542b3f85d53771c476b10cc to 503445990bccbb61c5d94f7205f3495043f6be76
comment:7 Changed 5 years ago by
 Commit changed from 503445990bccbb61c5d94f7205f3495043f6be76 to 06f148210bcf75fddf6384fb6d101ffb7deae217
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
2f8d672  InteractiveLPBackend: Remove commentedout code

3a26453  InteractiveLPBackend: Expand example with algebraic numbers

b7f1ed8  get_solver: Add another doctest

8c1fd4a  get_solver: Fix last doctest

d23c57f  Merge branch 't/20296/mixedintegerlinearprogram__new_backend_using_interactivelpproblem' into lp_fixes

3f827ea  Use TestSuite for testing MIP backends

ec68338  Add comment

1d617b7  More _test_... functions

3c6a759  get_solver: Make doctest work no matter whether backends are Python or Sage objects

06f1482  Run testsuite with all MIP backends

comment:8 Changed 5 years ago by
Branch is on top of various closed/reviewed LP tickets from #20302. Will rebase on top of next 'develop' later.
comment:9 Changed 5 years ago by
 Description modified (diff)
comment:10 Changed 5 years ago by
 Commit changed from 06f148210bcf75fddf6384fb6d101ffb7deae217 to af4bcd5c4605dcf4e5b6321335e9137174f14940
Branch pushed to git repo; I updated commit sha1. New commits:
af4bcd5  GenericBackend._test_add_variables(): Add tests from CVXOPTBackend

comment:11 Changed 5 years ago by
Hi Matthias!
Just had a brief look at your TestSuite? usage. This sounds very sensible indeed.
Inheriting from PythonObjectWithTests? would indeed make sense; however since it's currently a plain Python class, one can't inherit from it in a Cython class. This could be fixed though.
Cheers,
Nicolas
comment:12 Changed 5 years ago by
 Commit changed from af4bcd5c4605dcf4e5b6321335e9137174f14940 to 65afba2d6bc7fdd31ea54e05845f5eb07b57fb5c
Branch pushed to git repo; I updated commit sha1. New commits:
b3a14bb  Fix #20326: GenericBackend: Fix doctest of add_linear_constraint_vector

690b1a5  add_linear_constraint: Use 'optional  Nonexistent_LP_solver' test as well

ec1b0e1  Merge branch 't/20326/genericbackend__fix_doctest_of_add_linear_constraint_vector' into t/20323/common_testsuite_for_mip_backends

41f9c98  Add a classmethod _test_solve

65afba2  GenericBackend._test_solve: Finish

comment:13 Changed 5 years ago by
 Status changed from new to needs_review
There are two types of _test_...
methods, which are illustrated by the following examples:
## This test method is written as an instance method that works ## even if variables and constraints have already been added to the backend. ## The test makes changes to the backend. def _test_add_linear_constraints(self, **options): """ Run tests on the method :meth:`.add_linear_constraints`. TESTS: Test, with an actual working backend, that the test works even if the problem is not empty at the beginning:: sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver='GLPK') sage: p.add_variables(2) 1 sage: p.add_linear_constraint([[0, 17], [1, 89]], None, 42) sage: p._test_add_linear_constraints() """ tester = self._tester(**options) nrows_before = self.nrows() nrows_added = 5 self.add_linear_constraints(nrows_added, None, 2) nrows_after = self.nrows() # Test correct number of rows tester.assertEqual(nrows_after, nrows_before+nrows_added, "Added the wrong number of rows") # Test contents of the new rows are correct (sparse zero) for i in range(nrows_before, nrows_after): tester.assertEqual(self.row(i), ([], [])) tester.assertEqual(self.row_bounds(i), (None, 2.0)) ## Any test methods involving calls to 'solve' are set up as class methods, ## which make a fresh instance of the backend. @classmethod def _test_solve(cls, tester=None, **options): """ Trivial test for the solve method. TEST:: sage: from sage.numerical.backends.generic_backend import GenericBackend sage: p = GenericBackend() sage: p._test_solve() Traceback (most recent call last): ... NotImplementedError: ... """ p = cls() # fresh instance of the backend if tester is None: tester = p._tester(**options) # From doctest of GenericBackend.solve: tester.assertIsNone(p.add_linear_constraints(5, 0, None)) tester.assertIsNone(p.add_col(range(5), range(5))) tester.assertEqual(p.solve(), 0) tester.assertIsNone(p.objective_coefficient(0,1)) from sage.numerical.mip import MIPSolverException #with tester.assertRaisesRegexp(MIPSolverException, "unbounded") as cm: ##  too specific with tester.assertRaises(MIPSolverException) as cm: # unbounded p.solve()
I've translated these from existing doctests (either from GenericBackend
or some real backend) by hand. _test_solve
already reveals another bug in the CVXOPT backend.
The plan is to use #20376 to semiautomatically add new _test
methods.
comment:14 Changed 5 years ago by
 Commit changed from 65afba2d6bc7fdd31ea54e05845f5eb07b57fb5c to 407532db90231cb924b73fc87fa6e252aff33c8d
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
3581a14  Merge branch 't/20326/genericbackend__fix_doctest_of_add_linear_constraint_vector' into 7.2.beta3_lpfixes

3b6bbbc  Use TestSuite for testing MIP backends

a583cf9  Add comment

b5acc34  More _test_... functions

2171d75  get_solver: Make doctest work no matter whether backends are Python or Sage objects

e2e228c  Run testsuite with all MIP backends

703494d  GenericBackend._test_add_variables(): Add tests from CVXOPTBackend

053361a  Add a classmethod _test_solve

407532d  GenericBackend._test_solve: Finish

comment:15 Changed 5 years ago by
Rebased on top of 7.2.beta3 + #20326.
comment:16 Changed 5 years ago by
Needs review, especially regarding my use or abuse of the testing framework...
comment:17 followup: ↓ 18 Changed 5 years ago by
You should not implement _test_*
method that modifies the object. I am not sure there is any control in which order things are executed. It would be better in this case to not use the test suite. I would rather have a file tests.py that is only made of doctests.
Moreover, it would make sense to also have comparison between different implementations. You can start with
sage: milps = [] sage: milps.append(MixedIntegerLinearProgram(solver='cplex') # optional  cplex sage: milps.append(MixedIntegerLinearProgram(solver='coin') # optional  cbc
and then loop over the elements in milps.
comment:18 in reply to: ↑ 17 Changed 5 years ago by
Replying to vdelecroix:
You should not implement
_test_*
method that modifies the object. I am not sure there is any control in which order things are executed.
As I pointed out in the comment above _test_add_linear_constraints
in comment 13, these instance methods are written in a way that the order does not matter.
The second example uses a class method and runs its tests on fresh instances, so it does not make modifications.
If it is policy that _test
methods cannot modify the object, then I can rewrite all tests as class methods like in the second example.
I would rather like to avoid using doctests (in fact I'm trying to replace the superficial, copypastedriven testing that is there now); and TestSuite
seems like exactly the right thing to enforce the API of concrete implementations of an abstract class.
comment:19 Changed 5 years ago by
From taking a quick look at what you are testing, it looks more like you should have a separate file with test functions that takes a backend, creates an instance of it, and runs the basic tests, and then have a "master" function which takes the backend and feeds it to each of those functions (or some small variant of this). IMO, this is a better way to do the things that you want, and it means for each (new) backend, you only have to add a test to pass it to the "master" function. It also has a bit of a fringe benefit of consolidating the testing of the backends.
It is possible the user will want to run TestSuite
on a particular instance, and will be quite surprised if the object has mutated. Another valid option would be to make a copy of the instance and do the mutations to that.
comment:20 followup: ↓ 22 Changed 5 years ago by
Or maybe putting the _test_* methods on the backends, with each _test_method starting by creating a new instance.
Cheers,
Nicolas
comment:21 Changed 5 years ago by
 Commit changed from 407532db90231cb924b73fc87fa6e252aff33c8d to d93b79857bdacc92a8a2a93155ab5f20bb0b1a8a
Branch pushed to git repo; I updated commit sha1. New commits:
d93b798  Change from mutating instance _test methods to class methods

comment:22 in reply to: ↑ 20 Changed 5 years ago by
Replying to nthiery:
Or maybe putting the _test_* methods on the backends, with each _test_method starting by creating a new instance.
Thanks Nicolas, Vincent, and Travis for your comments.
I agree, making changes to the object may be surprising to users who are in the habit of running the testsuite on objects.
I have now converted the _test_*
methods that were previously making changes into methods that create a new instance.
(This is in line with what Nicolas suggests.)
All _test_*
methods are now actually marked as classmethods, so these methods don't even get access to the instance, so they can't modify it. Here's an example.
@classmethod def _test_add_linear_constraints(cls, tester=None, **options): """ Run tests on the method :meth:`.add_linear_constraints`. TEST:: sage: from sage.numerical.backends.generic_backend import GenericBackend sage: p = GenericBackend() sage: p._test_add_linear_constraints() Traceback (most recent call last): ... NotImplementedError """ p = cls() # fresh instance of the backend if tester is None: tester = p._tester(**options) nrows_before = p.nrows() nrows_added = 5 p.add_linear_constraints(nrows_added, None, 2) nrows_after = p.nrows() # Test correct number of rows tester.assertEqual(nrows_after, nrows_before+nrows_added, "Added the wrong number of rows") # Test contents of the new rows are correct (sparse zero) for i in range(nrows_before, nrows_after): tester.assertEqual(p.row(i), ([], [])) tester.assertEqual(p.row_bounds(i), (None, 2.0))
Some of you suggested that the tests should be in a different file; but I don't see how that would help. I would rather like to keep them as close as possible to the definitions of the methods in GenericBackend
; after all the point of the new tests is to tighten the definition of the API of the backends.
The nice thing about having these _test_*
methods automatically inherited by all concrete backends is that they cannot just "forget" running the tests for them when it would be "convenient" to do so.
comment:23 followup: ↓ 25 Changed 5 years ago by
Some remarks before looking once more at the code:
 It would actually be interesting for the tests to have access to the objects. They are non trivially initialized (maximization vs minimization, constraints, etc). Using them as a base (with copy) each test suite would actually run different tests.
 This approach does not allow to cross check the backends (?).
comment:24 Changed 5 years ago by
 Commit changed from d93b79857bdacc92a8a2a93155ab5f20bb0b1a8a to 94a4ac546369b8b12d36635e2c74d7113420b144
Branch pushed to git repo; I updated commit sha1. New commits:
94a4ac5  New method _test_ncols_nonnegative

comment:25 in reply to: ↑ 23 ; followup: ↓ 28 Changed 5 years ago by
Replying to vdelecroix:
Some remarks before looking once more at the code:
 It would actually be interesting for the tests to have access to the objects. They are non trivially initialized (maximization vs minimization, constraints, etc). Using them as a base (with copy) each test suite would actually run different tests.
If one wants to write such a test, one can just remove the @classmethod decorator. This makes indeed sense for the various getter methods. As an example, I have just added the following test method:
def _test_ncols_nonnegative(self, **options): tester = self._tester(**options) p = self tester.assertGreaterEqual(self.ncols(), 0)
 This approach does not allow to cross check the backends (?).
The idea is that all backends are checked against the same set of tests. (In contrast to the current doctests, in which each backend decides by copypaste what is convenient to be tested.) I plan to distill a good set of tests by means of #20376 from the existing doctests of the various backends.
comment:26 Changed 5 years ago by
I forgot to remark, I wouldn't want to rely on copy
so much at the moment, because the nontrivial copy methods of the backends are essentially untested (doctests there to please the patchbot), just like the rest of the API.
comment:27 Changed 5 years ago by
 Commit changed from 94a4ac546369b8b12d36635e2c74d7113420b144 to c4e7a839e348f0469b84bde2edcb2dfd69bc71b9
comment:28 in reply to: ↑ 25 Changed 5 years ago by
Replying to vdelecroix:
 It would actually be interesting for the tests to have access to the objects. They are non trivially initialized (maximization vs minimization, constraints, etc). Using them as a base (with copy) each test suite would actually run different tests.
I think now I understand better what you meant.
Indeed, at least some instance _test
methods  such as the _test
methods for copy
that I just wrote  would benefit from being invoked for various examples.
comment:29 Changed 5 years ago by
 Commit changed from c4e7a839e348f0469b84bde2edcb2dfd69bc71b9 to 7faac98bba71be74cb75ead66e0f432a1180f0c4
comment:30 Changed 5 years ago by
 Commit changed from 7faac98bba71be74cb75ead66e0f432a1180f0c4 to f40980646e129eeb501a51fd06e99eb98d83a4f3
comment:31 Changed 5 years ago by
comment:32 followup: ↓ 37 Changed 5 years ago by
I recall asking how one deals with different backends producing different, albeit equivalent, outputs. E.g. some of them would even introduce extra variables for some constraints. Some backends assign names to constraints automatically.
comment:33 Changed 5 years ago by
 Reviewers set to Thierry Monteil
 Status changed from needs_review to needs_work
Note that currently the tests do not pass when cbc
is installed, see the logs at http://patchbot.sagemath.org/log/20323/debian/8.3/i686/3.16.04586/tmonteildebianjessie32/20160411%2008:33:06
comment:34 followup: ↓ 35 Changed 5 years ago by
this would also show errors just fine: http://patchbot.sagemath.org/log/20323/debian/8.3/i686/3.16.04586/tmonteildebianjessie32/20160411%2008:33:06?short
anyhow, it looks as if there are also errors not related to cbc. Wrong git branch?
comment:35 in reply to: ↑ 34 Changed 5 years ago by
Replying to dimpase:
Wrong git branch?
Apparently not, the indicated commit is f40980646e129eeb501a51fd06e99eb98d83a4f3
comment:36 Changed 5 years ago by
Yes, lots of tests fail! And I haven't even really started adding tests.
It's the whole point of writing this test suite.
comment:37 in reply to: ↑ 32 Changed 5 years ago by
Replying to dimpase:
I recall asking how one deals with different backends producing different, albeit equivalent, outputs. E.g. some of them would even introduce extra variables for some constraints (see e.g. here). Some backends assign names to constraints automatically.
Thanks for the pointer to that ticket. Yes, the tests need to be written in a way that they accommodate the solvers.
comment:38 Changed 5 years ago by
 Commit changed from f40980646e129eeb501a51fd06e99eb98d83a4f3 to 22511250dd688bba5d98672fb89b0f779fd28e97
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
2251125  GenericBackend: Remove failing _test methods from this ticket to make the patchbot and its friends happy

comment:39 Changed 5 years ago by
 Dependencies set to #20326
 Status changed from needs_work to needs_review
I've split this ticket. Now the branch has only tests that pass; other tests will appear on #20424. Ready for review.
comment:40 Changed 5 years ago by
please rebase over the latest beta. there is a small merge conflict:
diff cc src/sage/numerical/backends/generic_backend.pyx index aef0cb0,d554470..0000000  a/src/sage/numerical/backends/generic_backend.pyx +++ b/src/sage/numerical/backends/generic_backend.pyx @@@ 1330,9 1408,7 +1414,13 @@@ cpdef GenericBackend get_solver(constra sage: p.base_ring() Real Double Field sage: p = get_solver(base_ring=QQ); p ++<<<<<<< HEAD + <sage.numerical.backends.ppl_backend.PPLBackend object at ...> + sage: p = get_solver(base_ring=ZZ); p + <sage.numerical.backends.ppl_backend.PPLBackend object at ...> ++======= + <...sage.numerical.backends.ppl_backend.PPLBackend...> ++>>>>>>> 22511250dd688bba5d98672fb89b0f779fd28e97 sage: p.base_ring() Rational Field sage: p = get_solver(base_ring=AA); p
comment:42 Changed 5 years ago by
 Commit changed from 22511250dd688bba5d98672fb89b0f779fd28e97 to 7138fa03a951cf62d970bf346893499fe8fd3daa
Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
052960c  Add comment

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

comment:43 Changed 5 years ago by
 Status changed from needs_work to needs_review
rebased on 7.2.beta4
comment:44 Changed 5 years ago by
 Reviewers changed from Thierry Monteil to Thierry Monteil, Dima Pasechnik
OK, good.
comment:45 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:46 Changed 5 years ago by
 Branch changed from u/mkoeppe/common_testsuite_for_mip_backends to 7138fa03a951cf62d970bf346893499fe8fd3daa
 Resolution set to fixed
 Status changed from positive_review to closed
within the existing framework it's easy to create a separate module, say, lp_backend_tests, and do such tests there. Not sure how to minimize the bloat, though, as each function should have doctests...
Note that total consistency is hard to get, as each backend has its own ideas on how, say, to number and order constraints. E.g., IIRC, gurobi does automatic conversions of some particular kinds of constraints.