Opened 8 years ago

Closed 8 years ago

#10043 closed enhancement (fixed)

Complete rewrite of LP solver interfaces

Reported by: ncohen Owned by: ncohen
Priority: major Milestone: sage-4.6.1
Component: linear programming Keywords:
Cc: malb, mvngu, schilly, leif Merged in: sage-4.6.1.alpha0
Authors: Nathann Cohen Reviewers: Martin Albrecht, Nathann Cohen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

This (large) patch creates a backends directory in the numerical/ folder.

It adds the following files :

  • glpk_backend.pyx/pxd
  • coin_backend.pyx/pxd
  • cplex_backend.pyx/pxd
  • generic_backend.pyx/pxd

It removes the following files from numerical

  • mip_glpk.pyx/pxd
  • mip_coin.pyx/pxd
  • mip_cplex.pyx/pxd
  • osi_interface.pyx/pxd

What for ? There is no a real interface between Sage and all these solvers. Not just a "solve"function that does everything at the same time. It is now much clearer, much more efficient, and it will be faaaaaaaar easier to use solver-specific features. It can now be used directly in Cython, and we can now deal with constraint generation (see patches XXX and XXX), which is a great news.

I know this patch is huge, and I swear I tried to avoid it by considering step-by-step patches, which slowly became a nightmare... The good point in all this is that all the LP-related methods are extensively tested through all the graph methods, which are very likely to detect the important mistakes. I do not doubt there are many left, and I expect this patch to be followed by several "fixes" as these new features are being used, but.... I hope this review will get us rid of most of them !

Thankssssssssss !!!

Nathann

(With this patch, there is no need anymore to install CBC in order to use CPLEX. Just adding the cplex files to include/ and lib/, as indicated at the end of http://www.sagemath.org/doc/constructions/linear_programming.html#solvers and running sage -b is enough)

Attachments (5)

trac_10043.patch (239.0 KB) - added by ncohen 8 years ago.
trac_10043 - review 1.patch (144.5 KB) - added by ncohen 8 years ago.
trac_10043_referee.patch (17.2 KB) - added by malb 8 years ago.
trac_10043_review1.patch (144.5 KB) - added by jdemeyer 8 years ago.
Same as trac_10043 - review 1.patch
trac_10043-review1.patch (144.6 KB) - added by ncohen 8 years ago.
updated version or review 1 patch : with commit message and no spaces

Download all attachments as: .zip

Change History (26)

comment:1 Changed 8 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 8 years ago by ncohen

  • Status changed from new to needs_review

comment:3 Changed 8 years ago by ncohen

(updated to be compatible with alpha2)

comment:4 Changed 8 years ago by ncohen

Rebased on #10043

Nathann

comment:5 follow-up: Changed 8 years ago by malb

  • Status changed from needs_review to needs_work

I applied the patch to 4.6.alpha3 without problems and doctests pass. The overall design looks good. However, the documentation is much much too sparse, especially since this is supposed to be a generic interface. All functions should get a docstring describing their expected behaviour and all instantiations should have docstrings testing them (of course, only indirectly since they are cdef'ed). I know it is a lot of work I'm asking for, but I think it is necessary.

comment:6 in reply to: ↑ 5 ; follow-up: Changed 8 years ago by ncohen

Replying to malb:

Hello !

I applied the patch to 4.6.alpha3 without problems and doctests pass.

Before anything else, thank you for that :-)

The overall design looks good. However, the documentation is much much too sparse, especially since this is supposed to be a generic interface. All functions should get a docstring describing their expected behaviour and all instantiations should have docstrings testing them (of course, only indirectly since they are cdef'ed).

Got it. I will document the expected INPUT/OUTPUT, but do you really think doctests are necessary at this level ? As you say, it will be indirect as these methods are all cdef (sage -coverage answers 100% on these files because of that), so as there is a wealth of methods testing them all in the graph/ and numerical/ directory... That's an honest question, as I do not see how to write smarter doctests than just a short example of how LP is used in Sage, and copy/paste it in each function as the same code would test them all...

I know it is a lot of work I'm asking for, but I think it is necessary.

Indeed. As long as you ask it knowing it means a lot of time, I do not mind doing it (as soon as I will have your advise onthe previous question)

Thanks

Nathann

comment:7 in reply to: ↑ 6 Changed 8 years ago by malb

Replying to ncohen:

Got it. I will document the expected INPUT/OUTPUT, but do you really think doctests are necessary at this level ? As you say, it will be indirect as these methods are all cdef (sage -coverage answers 100% on these files because of that), so as there is a wealth of methods testing them all in the graph/ and numerical/ directory... That's an honest question, as I do not see how to write smarter doctests than just a short example of how LP is used in Sage, and copy/paste it in each function as the same code would test them all...

There should at least be doctests in the generic backend class, which highlight how these cdef functions are used. My reason for asking for doctests for all functions in the instantiations is that e.g. the graph class will only test the default LP backend and would not check the other (optional) backends. I'm happy to have the same doctests in all instantiations except that a different solver is used each time. In fact, we could write a template file which has all the doctests in it, and one string replace of e.g. "YOUR_SOLVER" with e.g. "SCIP" would make it easy to have nice coverage of all the functions. Also, the more low level a doctest is, the easier it is to debug a failure.

comment:8 Changed 8 years ago by ncohen

  • Status changed from needs_work to needs_review

Rewritten... Again. With proper documentation which appear in the reference manual and for each backend (and not only generic_backend), with tests, with.... Well, just improved I hope :-)

Nathann

Changed 8 years ago by ncohen

comment:9 Changed 8 years ago by malb

  • Status changed from needs_review to needs_work

Hi, a few comments. They are rather nitpicky but since you're defining an interface it would be hard to change any of this at a later time.

  • there is one doctest failure, where you forgot to catch the NotImplementedError
  • getSolver should be get_solver according to Python coding conventions
  • Sage matrices use ncols() instead of n_cols(), I suggest to do the same for consistency (same for (nrows, add_column instead of add_col)
  • Isn't set_sense() the canonical vocabulary instead of set_direction()?
  • I think we have a bias in Sage to using coefficient instead of coeff in function names
  • One could rename set_log_level to set_verbose(_level)() to match the global function names already defined in Sage (see below for comments on getters and setters)
  • I wonder if it would make sense to rename add_constraint to add_linear_constraint. Of course, this is a linear programming backend but many of the solvers we support also support non-linear constraints.
  • Sage matrices define row() instead of get_row(). I guess if you change the name then maybe all get_XXX() might be replaced by XXX() which seems to conform to Python conventions.
  • In the same spirit one could replace get/set_variable_min/max by functions variable_min/max which return the value if no optional argument is given and set the value if it is given. Same for similar functions. It seems getter and setter functions are considered unpythonic. http://tomayko.com/writings/getters-setters-fuxors

comment:10 Changed 8 years ago by ncohen

  • Status changed from needs_work to needs_review

After several more hours... All of it is addressed :-)

Nathann

Changed 8 years ago by ncohen

Changed 8 years ago by malb

comment:11 Changed 8 years ago by malb

I've attached a referee patch which fixes the following issues:

  • Nathan didn't claim copyright but he should, I've also added him as AUTHOR in the docstring
  • get_objective_coeff -> get_objective_coefficient, it seems to be an oversight that it wasn't renamed
  • removed the optional modules Coin and CPLEX from the reference manual (the produce errors since they cannot be found if they are not installed)

I guess it would be nice to have pickling for these backends but it is unrealistic that it can be implemented for all (or even most) of them. Thus, I'd say if my referee patch is accepted by Nathann, this is good to go.

comment:12 follow-up: Changed 8 years ago by ncohen

Sorry for this coefficient thing.... I was convinced to have changed it but ^^;

You're right about this cplex/cbc thing. But maybe we will also have to deal with optional doc, as we already deal with libraries conditionally built according to the spkg installed.

About the copyright, I have a *technical* question : why do you think I should ?.. I often see people adding their names in methods they add, or at the head of files, and I really do not mind as they wrote them themselves... But I tried to "forget it" when I could, not willing to play a patent game I do not like.... Philosophically, I prefer to contribute without really leaving my name, but why do you think these files should be copyrighted ? Isn't it some "sage copyright" by default ?

Nathann

comment:13 in reply to: ↑ 12 ; follow-up: Changed 8 years ago by schilly

Replying to ncohen:

About the copyright, I have a *technical* question : why do you think I should ?

We license this software via GPLv2+ to everybody. To license something, it needs to have a copyright (reversed, you cannot license something that has no assigned creator). Also, internationally there is nothing like "public domain" like in the usa. We can rely on mercurial to do this, but if somebody only looks at the source there has this to be. You can read more about this in the history of international copyright (e.g. berne convention) and of course in the text of the GPL itself.

comment:14 in reply to: ↑ 13 ; follow-up: Changed 8 years ago by ncohen

  • Status changed from needs_review to positive_review

We license this software via GPLv2+ to everybody. To license something, it needs to have a copyright (reversed, you cannot license something that has no assigned creator). Also, internationally there is nothing like "public domain" like in the usa. We can rely on mercurial to do this, but if somebody only looks at the source there has this to be. You can read more about this in the history of international copyright (e.g. berne convention) and of course in the text of the GPL itself.

Well, the book I'm reading these days is actually entitled "intellectual property", I'll probably learn about all this pretty soon... It's french law though... I really had no idea there was nothing like "public domain" in the USA !

Thank you for this lesson.

And thank you *very much* Mike for your help with this ticket !!! :-)

All tests pass. Nothing that worries me for the moment. Positive review to this ticket !

Nathann

comment:15 in reply to: ↑ 14 Changed 8 years ago by schilly

Replying to ncohen:

Well, the book I'm reading these days is actually entitled "intellectual property", I'll probably learn about all this pretty soon...

soon we will consult you about these matters ;)

It's french law though... I really had no idea there was nothing like "public domain" in the USA !

uhm, i meant, internationally. in the usa exists public domain, but not in other countries and afaik there is no way to apply this us copyright law automatically outside the usa ;) There is also a difference if you want to make something public domain right now or if you want to wait ~80 years.

... and on top of that, things are even more complicated because law changes all the time.

comment:16 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-4.6 to sage-4.6.1
  • Reviewers set to Martin Albrecht, Nathann Cohen

Changed 8 years ago by jdemeyer

Same as trac_10043 - review 1.patch

comment:17 Changed 8 years ago by jdemeyer

Please don't put "strange" characters such as spaces in patch filenames.

comment:18 Changed 8 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Please update the commit message of trac_10043_review1.patch

Changed 8 years ago by ncohen

updated version or review 1 patch : with commit message and no spaces

comment:19 Changed 8 years ago by ncohen

  • Status changed from needs_work to positive_review

Done !

comment:20 Changed 8 years ago by leif

  • Cc leif added

comment:21 Changed 8 years ago by jdemeyer

  • Merged in set to sage-4.6.1.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.