Sage: Ticket #7012: clean up sage/numerical/mip.pyx
https://trac.sagemath.org/ticket/7012
<p>
As the subject says. This is a follow up to <a class="closed ticket" href="https://trac.sagemath.org/ticket/6869" title="enhancement: [with patch, positive review] LP and MIP Solvers in Sage ( with symbolics ) (closed: fixed)">#6869</a> to address mhansen's suggestions:
</p>
<pre class="wiki">
After going through this patch, I think it would be best to revert it before 4.1.2 is released. There is still a lot of things that need to be done to get it cleaned up. Some of the things,
1. Almost all of the docstrings are incorrectly formatted.
1. This module should _definitely_ not be a Cython module as it does not gain any benefit from Cython. It just makes Sage slower to compile and things harder to debug.
1. Some of the naming conventions do not match Sage's conventions. (isbinary vs. is_binary). Also, names like the more explicit MixedIntegerProgram? are preferred over the shortened MIP.
1. The optional spkgs should not install modules into the sage.* namespace (sage.numerical.mipGlpk). This is not the right way to do things and will eventually break. I think it also makes sense to use (and contribute to) something like ctypes-glpk to allow greater functionality and not reinvent the wheel.
I have some code that addresses some of these things that I'll put up shortly.
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/7012
Trac 1.1.6ncohenSat, 26 Sep 2009 14:50:13 GMT
https://trac.sagemath.org/ticket/7012#comment:1
https://trac.sagemath.org/ticket/7012#comment:1
<p>
Hello !!!
</p>
<p>
Could I have more information about some points :
</p>
<ol><li>Almost all of the docstrings are incorrectly formatted.
</li></ol><p>
Could you tell me in which way ? I am still learning how to write these, and may have learnt a few things since this patch but I would like to know what you have in mind.
</p>
<ol><li>This module should _definitely_ not be a Cython module as it does not gain any benefit from Cython. It just makes Sage slower to compile and things harder to debug.
</li></ol><ul><li>I understand that there may be very few reasons left ( now ) for keeping this as a Cython module. Here is the reason why I built it this way : initially, I thought the GLPK package would be merged immediately merged to standard Sage, and the function sending the LP problem to the solver GLPK ( necessarily written in Cython as it uses C functions ) was at this time contained in the file numerical.mip. I did not know how to change this when I learnt GLPK was to be optional for a while, and this is the reason why I just moved the function solveGLPK to the optional package. This, though, is way less handy when I need to improve functions like solveGLPK or solveCBC, as I always need to update the whole package.. I intended to move function solveGLPK to the file numerical.MIP as soon as GLPK is accepted as a standard spkg.
</li></ul><ol><li>Some of the naming conventions do not match Sage's conventions. (isbinary vs. is_binary). Also, names like the more explicit <a class="missing wiki">MixedIntegerProgram?</a>? are preferred over the shortened MIP.
</li></ol><ul><li>I quite agree
</li></ul><ol><li>The optional spkgs should not install modules into the sage.* namespace (sage.numerical.mipGlpk). This is not the right way to do things and will eventually break. I think it also makes sense to use (and contribute to) something like ctypes-glpk to allow greater functionality and not reinvent the wheel.
</li></ol><p>
I wrote to many people to get informations about how best these things should be done. I am not happy either with the way it is now... What would you advise ? I know nothing of ctypes-glpk ! I just visited its front page and I can only see that it makes C functions available under python, which Cython can already do.
</p>
<p>
On top of all this, I have a "personal" request.... I intend to write a lot of things that will be added to the MIP class ( soon to be <a class="missing wiki">MixedIntegerProgram?</a> ), but I initially wrote this class just to write new Graph-related functions. I have still a lot of patches waiting to be reviewed/accepted ( <a class="closed ticket" href="https://trac.sagemath.org/ticket/6764" title="enhancement: Independent Set of Representatives (closed: fixed)">#6764</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/6763" title="enhancement: [with patch, needs review] Bin Packing (uses Linear Programming) (closed: fixed)">#6763</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/6680" title="enhancement: Flow, Matching, Connectivity, and some Hard problems (closed: duplicate)">#6680</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/6679" title="enhancement: Vertex Coloring, Edge Coloring (closed: fixed)">#6679</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/6765" title="enhancement: Linear Programming in Tutorial's Tour ! (closed: wontfix)">#6765</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/6962" title="enhancement: Feedback vertex set, Feedback arc set (closed: fixed)">#6962</a> ), all using this class. Each time a modification is brought to the main class MIP, I have to rewrite patches for all of these tickets to make them coherent with the "current" state of the MIP Class. Could this ticket wait for these patches to be merged ? It would be easier, later, to change MIP to <a class="missing wiki">MixedIntegerProgram?</a>, isbinary to is_binary, and many other problems/bugs I already noticed in an unique patch to correct them all at once.... :-)
</p>
<p>
Thank you a lot for your interest, though :-)
</p>
<p>
Nathann
</p>
TicketmvnguSat, 26 Sep 2009 22:48:07 GMT
https://trac.sagemath.org/ticket/7012#comment:2
https://trac.sagemath.org/ticket/7012#comment:2
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7012#comment:1" title="Comment 1">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Hello !!!
</p>
<p>
Could I have more information about some points :
</p>
<ol><li>Almost all of the docstrings are incorrectly formatted.
</li></ol><p>
Could you tell me in which way ? I am still learning how to write these, and may have learnt a few things since this patch but I would like to know what you have in mind.
</p>
</blockquote>
<p>
The Developers' Guide has a section on <a href="http://www.sagemath.org/doc/developer/conventions.html#documentation-strings">docstring</a>. You should follow the conventions listed in that section.
<br /><br />
</p>
<blockquote class="citation">
<ol><li>This module should _definitely_ not be a Cython module as it does not gain any benefit from Cython. It just makes Sage slower to compile and things harder to debug.
</li></ol><ul><li>I understand that there may be very few reasons left ( now ) for keeping this as a Cython module. Here is the reason why I built it this way : initially, I thought the GLPK package would be merged immediately merged to standard Sage, and the function sending the LP problem to the solver GLPK ( necessarily written in Cython as it uses C functions ) was at this time contained in the file numerical.mip. I did not know how to change this when I learnt GLPK was to be optional for a while, and this is the reason why I just moved the function solveGLPK to the optional package. This, though, is way less handy when I need to improve functions like solveGLPK or solveCBC, as I always need to update the whole package.. I intended to move function solveGLPK to the file numerical.MIP as soon as GLPK is accepted as a standard spkg.
</li></ul></blockquote>
<p>
In light of the recent discussion about making a package standard, a package that is to be a standard spkg must satisfy at minimum the following requirements:
</p>
<ol><li>Build as 32-bit with GCC on SPARC
</li><li>Build as 64-bit with GCC on SPARC
</li><li>Build as 32-bit with Sun's compiler on SPARC
</li><li>Build as 64-bit with Sun's compiler on SPARC
</li><li>Build as 32-bit with GCC on x86
</li><li>Build as 64-bit with GCC on x86_64
</li><li>Build as 32-bit with Sun's compiler on x86
</li><li>Build as 64-bit with Sun's compiler on x86_64
</li></ol><p>
Note that satisfying the first four would likely satisfy the remaining criteria. It much less work to have GLPK and CBC be optional packages and hence improve on the MIP module. As far as I can tell, both of these packages are already optional spkg's and they satisfy the minimum of being optional packages, namely they build on supported Linux distributions and Mac OS X 10.5. I have not tried building and using them on OS X 10.6 yet. But if you have an account on bsd.math which runs OS X 10.6 now, you could test on that machine. See <a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_thread/thread/15c461b1355a8460/d9660e265ad982d8"><span class="icon"></span>here</a> and <a class="ext-link" href="http://groups.google.com/group/sage-devel/browse_thread/thread/b54a6b4317add033/bf7224be375df49f"><span class="icon"></span>here</a> for the discussions about making a package standard.
<br /><br />
</p>
<blockquote class="citation">
<ol><li>The optional spkgs should not install modules into the sage.* namespace (sage.numerical.mipGlpk). This is not the right way to do things and will eventually break. I think it also makes sense to use (and contribute to) something like ctypes-glpk to allow greater functionality and not reinvent the wheel.
</li></ol><p>
I wrote to many people to get informations about how best these things should be done. I am not happy either with the way it is now... What would you advise ? I know nothing of ctypes-glpk ! I just visited its front page and I can only see that it makes C functions available under python, which Cython can already do.
</p>
</blockquote>
<p>
I have little experience with Cython and much less with maintaining an optional package. Since I'm busy with release management in the next week or so, I won't have time to investigate this issue. After finishing the 4.1.2 release, I won't be able to work on anything but my thesis project.
<br /><br />
</p>
<blockquote class="citation">
<p>
On top of all this, I have a "personal" request.... I intend to write a lot of things that will be added to the MIP class ( soon to be <a class="missing wiki">MixedIntegerProgram?</a> ), but I initially wrote this class just to write new Graph-related functions. I have still a lot of patches waiting to be reviewed/accepted ( <a class="closed ticket" href="https://trac.sagemath.org/ticket/6764" title="enhancement: Independent Set of Representatives (closed: fixed)">#6764</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/6763" title="enhancement: [with patch, needs review] Bin Packing (uses Linear Programming) (closed: fixed)">#6763</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/6680" title="enhancement: Flow, Matching, Connectivity, and some Hard problems (closed: duplicate)">#6680</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/6679" title="enhancement: Vertex Coloring, Edge Coloring (closed: fixed)">#6679</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/6765" title="enhancement: Linear Programming in Tutorial's Tour ! (closed: wontfix)">#6765</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/6962" title="enhancement: Feedback vertex set, Feedback arc set (closed: fixed)">#6962</a> ), all using this class. Each time a modification is brought to the main class MIP, I have to rewrite patches for all of these tickets to make them coherent with the "current" state of the MIP Class. Could this ticket wait for these patches to be merged ? It would be easier, later, to change MIP to <a class="missing wiki">MixedIntegerProgram?</a>, isbinary to is_binary, and many other problems/bugs I already noticed in an unique patch to correct them all at once.... :-)
</p>
</blockquote>
<p>
I think a good way about this is to look through how Simon King produced his optional p_group_cohomology package. You should ask Simon about his experiences with writing a self-contained package.
<br /><br />
</p>
<p>
I do intend to clean up the MIP class before releasing Sage 4.1.2. Any help is appreciated.
</p>
TicketncohenMon, 28 Sep 2009 07:57:09 GMTsummary changed
https://trac.sagemath.org/ticket/7012#comment:3
https://trac.sagemath.org/ticket/7012#comment:3
<ul>
<li><strong>summary</strong>
changed from <em>clean up sage/numerical/mip.pyx</em> to <em>[work in progress] clean up sage/numerical/mip.pyx</em>
</li>
</ul>
<p>
Ok... I will be trying to send some coherent patch in the next few days, so it would be better if I am the only one working on this so our modification do not overlap. I changed some methods like setmin to set_min to let them be more Sage-like, and this involves modifying once more the packages CBC and GLPK ( which will have to be reviewed again... )
</p>
<p>
I may bring several other modifications too, while I'm at it. How close is next release ?
</p>
<p>
Nathann
</p>
TicketmvnguMon, 28 Sep 2009 08:00:57 GMT
https://trac.sagemath.org/ticket/7012#comment:4
https://trac.sagemath.org/ticket/7012#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/7012#comment:3" title="Comment 3">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Ok... I will be trying to send some coherent patch in the next few days, so it would be better if I am the only one working on this so our modification do not overlap.
</p>
</blockquote>
<p>
Thanks letting me know. I'll leave it to you to clean up MIP. Inform me when it's ready and I'll take a look.
<br /><br />
</p>
<blockquote class="citation">
<p>
I changed some methods like setmin to set_min to let them be more Sage-like, and this involves modifying once more the packages CBC and GLPK ( which will have to be reviewed again... )
</p>
</blockquote>
<p>
Inform me when it's ready and I'll take a look.
<br /><br />
</p>
<blockquote class="citation">
<p>
I may bring several other modifications too, while I'm at it. How close is next release ?
</p>
</blockquote>
<p>
The upcoming rc0 is in about 3 days or so.
</p>
TicketncohenMon, 28 Sep 2009 09:34:59 GMTtype, summary changed
https://trac.sagemath.org/ticket/7012#comment:5
https://trac.sagemath.org/ticket/7012#comment:5
<ul>
<li><strong>type</strong>
changed from <em>enhancement</em> to <em>defect</em>
</li>
<li><strong>summary</strong>
changed from <em>[work in progress] clean up sage/numerical/mip.pyx</em> to <em>[with patch, needs review] clean up sage/numerical/mip.pyx</em>
</li>
</ul>
<p>
What this patch does :
</p>
<ul><li>renames function getmin to get_min, isinteger to is_integer, etc ....
</li><li>renames class MIP to <a class="missing wiki">MixedIntegerLinearProgram?</a>
</li><li>function
</li><li>Typos
</li><li>stupid bugfix 1 : setinteger was setting variables as binary in some cases ...
</li><li>stupid bugfix 2 : setinteger(x) did not set x[2] as integer if x[2] had not been mentionned before setinteger()
</li><li>Some ":" replaced by "::", some <em> by <code></code>
</em></li></ul>
TicketncohenMon, 28 Sep 2009 09:35:25 GMTattachment set
https://trac.sagemath.org/ticket/7012
https://trac.sagemath.org/ticket/7012
<ul>
<li><strong>attachment</strong>
set to <em>trac_7012.patch</em>
</li>
</ul>
TicketncohenMon, 28 Sep 2009 09:36:32 GMT
https://trac.sagemath.org/ticket/7012#comment:6
https://trac.sagemath.org/ticket/7012#comment:6
<p>
I forgot to mention this new patch can only be used through GLPK at <a class="closed ticket" href="https://trac.sagemath.org/ticket/7049" title="defect: GLPK, just minor changes (closed: fixed)">#7049</a> as many methods had to be renamed and brek compatibility with old spkg.
</p>
TicketmhansenMon, 28 Sep 2009 09:51:58 GMT
https://trac.sagemath.org/ticket/7012#comment:7
https://trac.sagemath.org/ticket/7012#comment:7
<p>
Nathann, can you sign into #sage-devel on IRC?
</p>
TicketmvnguThu, 01 Oct 2009 11:29:22 GMTattachment set
https://trac.sagemath.org/ticket/7012
https://trac.sagemath.org/ticket/7012
<ul>
<li><strong>attachment</strong>
set to <em>trac_7012-rebased.patch</em>
</li>
</ul>
<p>
rebased against Sage 4.1.2.rc0
</p>
TicketmvnguThu, 01 Oct 2009 11:33:53 GMT
https://trac.sagemath.org/ticket/7012#comment:8
https://trac.sagemath.org/ticket/7012#comment:8
<p>
Applying the patch <code>trac_7012.patch</code> results in a hunk failure:
</p>
<pre class="wiki">[mvngu@sage sage-main]$ hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/7012/trac_7012.patch && hg qpush
adding trac_7012.patch to series file
applying trac_7012.patch
patching file sage/numerical/knapsack.py
Hunk #1 FAILED at 640
1 out of 1 hunks FAILED -- saving rejects to file sage/numerical/knapsack.py.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
Errors during apply, please fix and refresh trac_7012.patch
</pre><p>
The hunk in question is:
</p>
<pre class="wiki">[mvngu@sage sage-main]$ cat sage/numerical/knapsack.py.rej
--- knapsack.py
+++ knapsack.py
@@ -641,16 +641,16 @@
if reals:
seq=[(x,1) for x in seq]
- from sage.numerical.mip import MIP
- p=MIP(sense=1)
- present=p.newvar()
- p.setobj(sum([present[i]*seq[i][1] for i in range(len(seq))]))
- p.addconstraint(sum([present[i]*seq[i][0] for i in range(len(seq))]),max=max)
+ from sage.numerical.mip import MixedIntegerLinearProgram
+ p=MixedIntegerLinearProgram(sense=1)
+ present=p.new_variable()
+ p.set_objective(sum([present[i]*seq[i][1] for i in range(len(seq))]))
+ p.add_constraint(sum([present[i]*seq[i][0] for i in range(len(seq))]),max=max)
if binary:
- p.setbinary(present)
+ p.set_binary(present)
else:
- p.setinteger(present)
+ p.set_integer(present)
if value_only:
return p.solve(objective_only=True)
</pre><p>
I have rebased the patch against Sage 4.1.2.rc0; see <code>trac_7012-rebased.patch</code>.
</p>
TicketmvnguThu, 01 Oct 2009 17:37:46 GMTattachment set
https://trac.sagemath.org/ticket/7012
https://trac.sagemath.org/ticket/7012
<ul>
<li><strong>attachment</strong>
set to <em>trac_7012-reviewer.patch</em>
</li>
</ul>
<p>
reviewer patch; apply on top of previous patch
</p>
TicketmvnguThu, 01 Oct 2009 17:43:24 GMTreviewer set
https://trac.sagemath.org/ticket/7012#comment:9
https://trac.sagemath.org/ticket/7012#comment:9
<ul>
<li><strong>reviewer</strong>
set to <em>Mike Hansen, Minh Van Nguyen</em>
</li>
</ul>
<p>
I have uploaded a reviewer patch that makes the following changes (see <code>trac_7012-reviewer.patch</code>):
</p>
<ol><li>Consistent use of double quotation marks in <code>sage/numerical/mip.pyx</code>.
</li><li>Doesn't use trailing white spaces.
</li><li>Limit the line width to about 75 characters. Don't go over 75 or so characters per line if you don't need to.
</li><li>Some typo fixes.
</li><li>Add <code>sage/numerical/mip.pyx</code> to the reference manual.
</li><li>Use 4-space indentation.
</li><li>Proper ReST formatting so the module appears nicely when rendered.
</li><li>Use <code>ValueError</code> instead of <code>Exception</code>. <code>ValueError</code> is more explicit, whereas <code>Exception</code> would catch anything.
</li><li>Use <code>maximization</code> with boolean values, instead of <code>sense</code> with either 1 or -1. This was suggested by Mike Hansen on IRC. So I would credit Mike and myself as reviewers for this ticket.
</li></ol><p>
Now my patch needs some reviewing by anyone other than me.
</p>
TicketncohenThu, 01 Oct 2009 18:55:02 GMT
https://trac.sagemath.org/ticket/7012#comment:10
https://trac.sagemath.org/ticket/7012#comment:10
<p>
Minh you're really amazing !! Thank you for your work ! :-)
</p>
TicketncohenFri, 02 Oct 2009 16:32:14 GMT
https://trac.sagemath.org/ticket/7012#comment:11
https://trac.sagemath.org/ticket/7012#comment:11
<p>
I tested it with <a class="closed ticket" href="https://trac.sagemath.org/ticket/7049" title="defect: GLPK, just minor changes (closed: fixed)">#7049</a> :
</p>
<ul><li>I updated <a class="closed ticket" href="https://trac.sagemath.org/ticket/7049" title="defect: GLPK, just minor changes (closed: fixed)">#7049</a> because the change from variable sense to variable maximization had to be mentionned there
</li><li>There was a wrong docstring report because GLPK sometines returns 1.684643648434 * 10<sup>(-16) instead of 0 ( as CBC does )
I added a "random" near the "optional" as GLPK and CBC do not agree on this.
</sup></li><li>sense->minimization needed changing in knapsack too
</li></ul><p>
The docstrings are perfect !!!
</p>
<p>
Here is a new flattened patch with those two modifications included
</p>
TicketmvnguSun, 04 Oct 2009 15:14:30 GMTattachment set
https://trac.sagemath.org/ticket/7012
https://trac.sagemath.org/ticket/7012
<ul>
<li><strong>attachment</strong>
set to <em>trac_7012-flattened.patch</em>
</li>
</ul>
<p>
flattened patch; include rebased patch and reviewer patch
</p>
TicketncohenSun, 04 Oct 2009 15:23:55 GMTattachment set
https://trac.sagemath.org/ticket/7012
https://trac.sagemath.org/ticket/7012
<ul>
<li><strong>attachment</strong>
set to <em>trac_7012-details.patch</em>
</li>
</ul>
TicketncohenWed, 14 Oct 2009 23:52:24 GMT
https://trac.sagemath.org/ticket/7012#comment:12
https://trac.sagemath.org/ticket/7012#comment:12
<p>
This ticket depends on <a class="closed ticket" href="https://trac.sagemath.org/ticket/7049" title="defect: GLPK, just minor changes (closed: fixed)">#7049</a>
</p>
TicketmvnguWed, 21 Oct 2009 22:36:22 GMTstatus, summary changed; author set
https://trac.sagemath.org/ticket/7012#comment:13
https://trac.sagemath.org/ticket/7012#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] clean up sage/numerical/mip.pyx</em> to <em>clean up sage/numerical/mip.pyx</em>
</li>
</ul>
<p>
I applied patches against Sage 4.2.alpha0 in the following order:
</p>
<ol><li><code>trac_7012-flattened.patch</code>
</li><li><code>trac_7012-details.patch</code>
</li></ol><p>
These two patches touch modules under <code>sage/numerical</code>. All doctests under this directory pass with the two patches. Doctesting the whole Sage library results in the following failure:
</p>
<pre class="wiki">[mvngu@sage sage-4.2.alpha0-sage.math]$ sage -t -long devel/sage-main/sage/modules/vector_real_double_dense.pyx
sage -t -long "devel/sage-main/sage/modules/vector_real_double_dense.pyx"
A mysterious error (perhaps a memory error?) occurred, which may have crashed doctest.
[3.1 s]
exit code: 768
----------------------------------------------------------------------
The following tests failed:
sage -t -long "devel/sage-main/sage/modules/vector_real_double_dense.pyx"
Total time for all tests: 3.1 seconds
</pre><p>
This is a known failure and has been reported before at ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/6825" title="defect: intermittent failure in vector_real_double_dense.pyx (closed: fixed)">#6825</a>. I then installed the optional GLPK package at <a class="closed ticket" href="https://trac.sagemath.org/ticket/7049" title="defect: GLPK, just minor changes (closed: fixed)">#7049</a>. All doctests passed when doctesting the whole Sage library. If the above two patches are merged, then the updated GLPK package at <a class="closed ticket" href="https://trac.sagemath.org/ticket/7049" title="defect: GLPK, just minor changes (closed: fixed)">#7049</a> should also be merged in the optional spkg repository.
</p>
TicketmhansenFri, 23 Oct 2009 09:05:24 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/7012#comment:14
https://trac.sagemath.org/ticket/7012#comment:14
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.2.alpha1</em>
</li>
</ul>
Ticket