Common TestSuite for MIP backends

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

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]

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]

Branch: u/mkoeppe/common_testsuite_for_mip_backends

[mkoeppe]

Commit: f5f69bd

[mkoeppe]

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]

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]

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.

[sagetrac-git]

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

d2a8a26	Add comment
5034459	More _test_... functions

[sagetrac-git]

Changed commit from f5f69bd to 5034459

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 5034459 to 06f1482

[mkoeppe]

comment:8

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

[sagetrac-git]

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

af4bcd5

GenericBackend._test_add_variables(): Add tests from CVXOPTBackend

[sagetrac-git]

Changed commit from 06f1482 to af4bcd5

[nthiery]

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

[sagetrac-git]

Changed commit from af4bcd5 to 65afba2

[sagetrac-git]

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]

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.

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 65afba2 to 407532d

[mkoeppe]

comment:15

Rebased on top of 7.2.beta3 + #20326.

[mkoeppe]

comment:16

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

[videlec]

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]

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.

[sagetrac-tmonteil]

Reviewer: Thierry Monteil

[sagetrac-tmonteil]

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]

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?

[sagetrac-tmonteil]

comment:35

Replying to @dimpase:

Wrong git branch?

Apparently not, the indicated commit is f40980646e129eeb501a51fd06e99eb98d83a4f3

[mkoeppe]

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]

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.

[sagetrac-git]

Changed commit from f409806 to 2251125

[sagetrac-git]

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

[mkoeppe]

comment:39

I've split this ticket. Now the branch has only tests that pass; other tests will appear on #20424.
Ready for review.

[mkoeppe]

Dependencies: #20326

[dimpase]

comment:40

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

[dimpase]

comment:41

---

[sagetrac-git]

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

[sagetrac-git]

Changed commit from 2251125 to 7138fa0

[mkoeppe]

comment:43

rebased on 7.2.beta4

[dimpase]

comment:44

OK, good.

[dimpase]

Changed reviewer from Thierry Monteil to Thierry Monteil, Dima Pasechnik

[vbraun]

Changed branch from u/mkoeppe/common_testsuite_for_mip_backends to 7138fa0