Common TestSuite for MIP backends

mkoeppe commented 8 years ago

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

Depends on #20326

CC: @dimpase @nathanncohen @videlec @vbraun @nthiery

Component: numerical

Author: Matthias Koeppe

Branch/Commit: 7138fa0

Reviewer: Thierry Monteil, Dima Pasechnik

Issue created by migration from https://trac.sagemath.org/ticket/20323

dimpase commented 8 years ago

comment:1

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.

mkoeppe commented 8 years ago

Branch: u/mkoeppe/common_testsuite_for_mip_backends

mkoeppe commented 8 years ago

Commit: f5f69bd

mkoeppe commented 8 years ago

comment:3

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

tscrim commented 8 years ago

comment:4

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

mkoeppe commented 8 years ago

comment:5

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`d2a8a26`	`Add comment`
`5034459`	`More _test_... functions`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from f5f69bd to 5034459

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`2f8d672`	`InteractiveLPBackend: Remove commented-out 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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 5034459 to 06f1482

mkoeppe commented 8 years ago

comment:8

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

mkoeppe commented 8 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,2 @@
- I think the 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.)
+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.)

-Pointers on how to do this would be welcome.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

af4bcd5 GenericBackend._test_add_variables(): Add tests from CVXOPTBackend

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 06f1482 to af4bcd5

nthiery commented 8 years ago

comment:11

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from af4bcd5 to 65afba2

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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`

mkoeppe commented 8 years ago

comment:13

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 65afba2 to 407532d

mkoeppe commented 8 years ago

comment:15

Rebased on top of 7.2.beta3 + #20326.

mkoeppe commented 8 years ago

comment:16

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

videlec commented 8 years ago

comment:17

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.

mkoeppe commented 8 years ago

comment:18

Replying to @videlec:

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.

tscrim commented 8 years ago

comment:19

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.

nthiery commented 8 years ago

comment:20

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

Cheers, Nicolas

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 407532d to d93b798

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

d93b798 Change from mutating instance _test methods to class methods

mkoeppe commented 8 years ago

comment:22

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.

videlec commented 8 years ago

comment:23

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 (?).

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from d93b798 to 94a4ac5

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

94a4ac5 New method _test_ncols_nonnegative

mkoeppe commented 8 years ago

comment:25

Replying to @videlec:

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.

mkoeppe commented 8 years ago

comment:26

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 94a4ac5 to c4e7a83

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`2810de4`	`_test_copy: New`
`c4e7a83`	`_test_copy_does_not_share_data: New`

mkoeppe commented 8 years ago

comment:28

Replying to @videlec:

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`43bd851`	`Test backend.copy() rather than copy(backend)`
`7faac98`	`test_copy_some_mips: New`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from c4e7a83 to 7faac98

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from 7faac98 to f409806

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

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

`a206c85`	`Add _test_solve_trac_18572 (autogenerated)`
`f409806`	`_test_solve_trac_18572: Replace float integers by integers to make test suitable for PPL backend`

mkoeppe commented 8 years ago

Author: Matthias Koeppe

dimpase commented 8 years ago

comment:32

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.

edd8e884-f507-429a-b577-5d554626c0fe commented 8 years ago

Reviewer: Thierry Monteil

edd8e884-f507-429a-b577-5d554626c0fe commented 8 years ago

comment:33

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

dimpase commented 8 years ago

comment:34

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?

edd8e884-f507-429a-b577-5d554626c0fe commented 8 years ago

comment:35

Replying to @dimpase:

Wrong git branch?

Apparently not, the indicated commit is f40980646e129eeb501a51fd06e99eb98d83a4f3

mkoeppe commented 8 years ago

comment:36

Yes, lots of tests fail! And I haven't even really started adding tests.

It's the whole point of writing this test suite.

mkoeppe commented 8 years ago

comment:37

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 8 years ago

Changed commit from f409806 to 2251125

sagemath / sage

Common TestSuite for MIP backends #20323