Opened 4 years ago

Closed 4 years ago

#20323 closed enhancement (fixed)

Common TestSuite for MIP backends

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-7.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) Commit: 7138fa03a951cf62d970bf346893499fe8fd3daa
Dependencies: #20326 Stopgaps:

Description (last modified by mkoeppe)

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 copy-paste from each other) that ensures consistency. (#20296 fixes several wrong doctests in GenericBackend, from which I tried to copy-paste, for example.)

Change History (46)

comment:1 Changed 4 years ago by dimpase

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.

comment:2 Changed 4 years ago by mkoeppe

  • Branch set to u/mkoeppe/common_testsuite_for_mip_backends

comment:3 Changed 4 years ago by mkoeppe

  • 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:

f5f69bdUse TestSuite for testing MIP backends

comment:4 follow-up: Changed 4 years ago by tscrim

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 4 years ago by mkoeppe

Thanks for taking a look, Travis.

Replying to tscrim:

Also, is there a reason why GenericBackend needs to inherit from SageObject (as opposed to just the Python object)?

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 4 years ago by git

  • Commit changed from f5f69bd5500538071542b3f85d53771c476b10cc to 503445990bccbb61c5d94f7205f3495043f6be76

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

d2a8a26Add comment
5034459More _test_... functions

comment:7 Changed 4 years ago by git

  • Commit changed from 503445990bccbb61c5d94f7205f3495043f6be76 to 06f148210bcf75fddf6384fb6d101ffb7deae217

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

2f8d672InteractiveLPBackend: Remove commented-out code
3a26453InteractiveLPBackend: Expand example with algebraic numbers
b7f1ed8get_solver: Add another doctest
8c1fd4aget_solver: Fix last doctest
d23c57fMerge branch 't/20296/mixedintegerlinearprogram__new_backend_using_interactivelpproblem' into lp_fixes
3f827eaUse TestSuite for testing MIP backends
ec68338Add comment
1d617b7More _test_... functions
3c6a759get_solver: Make doctest work no matter whether backends are Python or Sage objects
06f1482Run testsuite with all MIP backends

comment:8 Changed 4 years ago by mkoeppe

Branch is on top of various closed/reviewed LP tickets from #20302. Will rebase on top of next 'develop' later.

Last edited 4 years ago by mkoeppe (previous) (diff)

comment:9 Changed 4 years ago by mkoeppe

  • Description modified (diff)

comment:10 Changed 4 years ago by git

  • Commit changed from 06f148210bcf75fddf6384fb6d101ffb7deae217 to af4bcd5c4605dcf4e5b6321335e9137174f14940

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

af4bcd5GenericBackend._test_add_variables(): Add tests from CVXOPTBackend

comment:11 Changed 4 years ago by nthiery

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 4 years ago by git

  • Commit changed from af4bcd5c4605dcf4e5b6321335e9137174f14940 to 65afba2d6bc7fdd31ea54e05845f5eb07b57fb5c

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

b3a14bbFix #20326: GenericBackend: Fix doctest of add_linear_constraint_vector
690b1a5add_linear_constraint: Use 'optional - Nonexistent_LP_solver' test as well
ec1b0e1Merge branch 't/20326/genericbackend__fix_doctest_of_add_linear_constraint_vector' into t/20323/common_testsuite_for_mip_backends
41f9c98Add a classmethod _test_solve
65afba2GenericBackend._test_solve: Finish

comment:13 Changed 4 years ago by mkoeppe

  • 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 semi-automatically add new _test methods.

comment:14 Changed 4 years ago by git

  • Commit changed from 65afba2d6bc7fdd31ea54e05845f5eb07b57fb5c to 407532db90231cb924b73fc87fa6e252aff33c8d

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

3581a14Merge branch 't/20326/genericbackend__fix_doctest_of_add_linear_constraint_vector' into 7.2.beta3_lpfixes
3b6bbbcUse TestSuite for testing MIP backends
a583cf9Add comment
b5acc34More _test_... functions
2171d75get_solver: Make doctest work no matter whether backends are Python or Sage objects
e2e228cRun testsuite with all MIP backends
703494dGenericBackend._test_add_variables(): Add tests from CVXOPTBackend
053361aAdd a classmethod _test_solve
407532dGenericBackend._test_solve: Finish

comment:15 Changed 4 years ago by mkoeppe

Rebased on top of 7.2.beta3 + #20326.

comment:16 Changed 4 years ago by mkoeppe

Needs review, especially regarding my use or abuse of the testing framework...

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

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, copy-paste-driven 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 4 years ago by tscrim

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 follow-up: Changed 4 years ago by nthiery

Or maybe putting the _test_* methods on the backends, with each _test_method starting by creating a new instance.

Cheers,

Nicolas

comment:21 Changed 4 years ago by git

  • Commit changed from 407532db90231cb924b73fc87fa6e252aff33c8d to d93b79857bdacc92a8a2a93155ab5f20bb0b1a8a

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

d93b798Change from mutating instance _test methods to class methods

comment:22 in reply to: ↑ 20 Changed 4 years ago by mkoeppe

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 follow-up: Changed 4 years ago by 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.
  • This approach does not allow to cross check the backends (?).

comment:24 Changed 4 years ago by git

  • Commit changed from d93b79857bdacc92a8a2a93155ab5f20bb0b1a8a to 94a4ac546369b8b12d36635e2c74d7113420b144

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

94a4ac5New method _test_ncols_nonnegative

comment:25 in reply to: ↑ 23 ; follow-up: Changed 4 years ago by mkoeppe

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 copy-paste 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 4 years ago by mkoeppe

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 4 years ago by git

  • Commit changed from 94a4ac546369b8b12d36635e2c74d7113420b144 to c4e7a839e348f0469b84bde2edcb2dfd69bc71b9

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

2810de4_test_copy: New
c4e7a83_test_copy_does_not_share_data: New

comment:28 in reply to: ↑ 25 Changed 4 years ago by mkoeppe

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 4 years ago by git

  • Commit changed from c4e7a839e348f0469b84bde2edcb2dfd69bc71b9 to 7faac98bba71be74cb75ead66e0f432a1180f0c4

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

43bd851Test backend.copy() rather than copy(backend)
7faac98test_copy_some_mips: New

comment:30 Changed 4 years ago by git

  • Commit changed from 7faac98bba71be74cb75ead66e0f432a1180f0c4 to f40980646e129eeb501a51fd06e99eb98d83a4f3

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

a206c85Add _test_solve_trac_18572 (autogenerated)
f409806_test_solve_trac_18572: Replace float integers by integers to make test suitable for PPL backend

comment:31 Changed 4 years ago by mkoeppe

  • Authors set to Matthias Koeppe

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

Last edited 4 years ago by dimpase (previous) (diff)

comment:33 Changed 4 years ago by tmonteil

  • 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.0-4-586/tmonteil-debian-jessie-32/2016-04-11%2008:33:06

comment:34 follow-up: Changed 4 years ago by dimpase

this would also show errors just fine: http://patchbot.sagemath.org/log/20323/debian/8.3/i686/3.16.0-4-586/tmonteil-debian-jessie-32/2016-04-11%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 4 years ago by tmonteil

Replying to dimpase:

Wrong git branch?

Apparently not, the indicated commit is f40980646e129eeb501a51fd06e99eb98d83a4f3

comment:36 Changed 4 years ago by mkoeppe

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 4 years ago by mkoeppe

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 4 years ago by git

  • Commit changed from f40980646e129eeb501a51fd06e99eb98d83a4f3 to 22511250dd688bba5d98672fb89b0f779fd28e97

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

2251125GenericBackend: Remove failing _test methods from this ticket to make the patchbot and its friends happy

comment:39 Changed 4 years ago by mkoeppe

  • 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 4 years ago by dimpase

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

  • Status changed from needs_review to needs_work

'

comment:42 Changed 4 years ago by git

  • Commit changed from 22511250dd688bba5d98672fb89b0f779fd28e97 to 7138fa03a951cf62d970bf346893499fe8fd3daa

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

052960cAdd comment
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

comment:43 Changed 4 years ago by mkoeppe

  • Status changed from needs_work to needs_review

rebased on 7.2.beta4

comment:44 Changed 4 years ago by dimpase

  • Reviewers changed from Thierry Monteil to Thierry Monteil, Dima Pasechnik

OK, good.

comment:45 Changed 4 years ago by dimpase

  • Status changed from needs_review to positive_review

comment:46 Changed 4 years ago by vbraun

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