Sage: Ticket #6869: [with patch, positive review] LP and MIP Solvers in Sage ( with symbolics )
https://trac.sagemath.org/ticket/6869
<p>
Hello everybody !!!
</p>
<p>
After the work done in <a class="closed ticket" href="https://trac.sagemath.org/ticket/6502" title="enhancement: Linear Program Solver and Mixed Integer Program Solver in Sage (closed: wontfix)">#6502</a> I rewrote the whole class taking into account the fact that some people may want to use this class too, instead of just focusing on the fact I needed it quickly to write Graph-Theoretic functions.
</p>
<p>
Here is the new numerical.MIP class, using symbolics, I hope sufficiently documented and tested, and everything... Thank you for your help !! This should be the last run ;-)
</p>
<p>
To use it, you have to install either GLPK from ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/6867" title="enhancement: [with spkg, positive review] GLPK ( compatible with the symbolics from ... (closed: fixed)">#6867</a> or Coin-OR CBC from <a class="closed ticket" href="https://trac.sagemath.org/ticket/6868" title="enhancement: [with spkg, positive review] Coin-OR CBC ( compatible with the ... (closed: fixed)">#6868</a> ( if you have installed a former version, they won't be compatible ! )
</p>
<p>
The class and the doctests, though, should behave peacefully if none of them is installed ! :-)
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/6869
Trac 1.1.6ncohenThu, 03 Sep 2009 08:26:49 GMTsummary changed
https://trac.sagemath.org/ticket/6869#comment:1
https://trac.sagemath.org/ticket/6869#comment:1
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs work] LP and MIP Solvers in Sage ( with symbolics )</em> to <em>[with patch, needs review] LP and MIP Solvers in Sage ( with symbolics )</em>
</li>
</ul>
TicketwdjTue, 08 Sep 2009 14:54:00 GMT
https://trac.sagemath.org/ticket/6869#comment:2
https://trac.sagemath.org/ticket/6869#comment:2
<p>
This applies fine to 4.1.2.a0 and passes testall without any other packages installed (no glpk, etc).
</p>
<p>
Running more tests...
</p>
TicketmvnguWed, 09 Sep 2009 12:17:09 GMTsummary changed
https://trac.sagemath.org/ticket/6869#comment:3
https://trac.sagemath.org/ticket/6869#comment:3
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] LP and MIP Solvers in Sage ( with symbolics )</em> to <em>[with patch, needs work] LP and MIP Solvers in Sage ( with symbolics )</em>
</li>
</ul>
<p>
The module <code>sage/numerical/mip.pyx</code> should have 100% doctest coverage, given that it's being added to the Sage library:
</p>
<pre class="wiki">[mvngu@sage numerical]$ sage -coverage mip.pyx
----------------------------------------------------------------------
mip.pyx
ERROR: Please define a s == loads(dumps(s)) doctest.
SCORE mip.pyx: 62% (18 of 29)
Missing documentation:
* __init__(self, value):
* __str__(self):
* __getitem__(self,i):
* keys(self):
* items(self):
* depth(self):
* values(self):
Missing doctests:
* __init__(self,sense=1):
* _NormalForm(self,exp):
* _addElementToRing(self):
* __init__(self,x,f,dim=1):
----------------------------------------------------------------------
</pre>
TicketncohenWed, 09 Sep 2009 17:52:37 GMT
https://trac.sagemath.org/ticket/6869#comment:4
https://trac.sagemath.org/ticket/6869#comment:4
<p>
Done !
</p>
TicketncohenWed, 09 Sep 2009 17:52:56 GMTattachment set
https://trac.sagemath.org/ticket/6869
https://trac.sagemath.org/ticket/6869
<ul>
<li><strong>attachment</strong>
set to <em>MIP-now-symbolic.patch</em>
</li>
</ul>
TicketncohenWed, 09 Sep 2009 17:53:08 GMTsummary changed
https://trac.sagemath.org/ticket/6869#comment:5
https://trac.sagemath.org/ticket/6869#comment:5
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs work] LP and MIP Solvers in Sage ( with symbolics )</em> to <em>[with patch, needs review] LP and MIP Solvers in Sage ( with symbolics )</em>
</li>
</ul>
TicketmvnguWed, 09 Sep 2009 18:43:38 GMT
https://trac.sagemath.org/ticket/6869#comment:6
https://trac.sagemath.org/ticket/6869#comment:6
<p>
ncohen asked this question in IRC:
</p>
<pre class="wiki">10:45 < ncohen> mvngu: do you know what this is ?
10:45 < ncohen> ERROR: Please define a s == loads(dumps(s)) doctest.
</pre><p>
This is encouraging you to define an equality method <code>__eq__()</code> for each of the three classes <code>MIP</code>, <code>MIPSolverException</code>, and <code>MIPVariable</code>. Say you have instantiated two objects of the class <code>MIPVariable</code>. How can you test to see whether or not they are the same object? In Python, this is usually implemented in the method <code>__equ__()</code> of a class. If a class defines this method, you can compare two objects of that class using the double-equal operator <code>==</code>. For example:
</p>
<pre class="wiki">sage: a1 = AlphabeticStrings()
sage: a2 = AlphabeticStrings()
sage: a1 == a2
True
</pre><p>
Take the case of writing the method <code>__eq__()</code> for the class <code>MIPVariable</code>. Are there criteria to tell us that two objects of the class <code>MIPVariable</code> are the same? If <code>m1</code> and <code>m2</code> are two such objects, you can define them to be the same object if their corresponding attributes have the same values. Each object of <code>MIPVariable</code> has these attributes: <code>dim</code>, <code>dict</code>, <code>x</code>, <code>f</code>. One way to write the <code>__eq__()</code> method for <code>MIPVariable</code> is this:
</p>
<pre class="wiki">def __eq__(self, other):
r"""
<insert lengthy documentation here, with examples>
"""
return self.dim == other.dim and self.dict == other.dict and self.x == other.x and self.f == other.f
</pre><p>
In the "EXAMPLES" section of that method, you should have an example as follows with appropriate values for <code>x</code>, <code>f</code>, and <code>dim</code>:
</p>
<pre class="wiki">sage: m = MIPVariable(someX, someF, someDim)
sage: m == loads(dumps(m))
True
</pre><p>
which should return True when you actually doctest the MIP module. Define a similar equality method for the other two classes.
<br />
</p>
<p>
One thing I dislike in code is to see it squashed together. This makes it more difficult to read, taking into account also that other people need to understand what that code does, its logical flow, and they might have been spending all day reading code. Good coding style is a plus here if you want your code to be as easily understandable as possible. Instead of doing this:
</p>
<pre class="wiki">self.dim=dim
self.dict={}
self.x=x
self.f=f
</pre><p>
do this:
</p>
<pre class="wiki">self.dim = dim
self.dict = {}
self.x = x
self.f = f
</pre><p>
<br />
</p>
<p>
Another issue is global namespace pollution. What I mean is that you should try to avoid as much as possible injecting your module, class, or function names into the global namespace when Sage loads itself. This is what you're currently doing with this code:
</p>
<pre class="wiki">from sage.numerical.mip import *
</pre><p>
What this means is that when you load Sage, all the class and function names defined in the module mip.pyx are loaded into the global namespace. An advantage to this is that a user doesn't have to first import the relevant class or function prior to using it. With the above import statement, I can do this
</p>
<pre class="wiki">sage: m = MIPVariable(x,f)
</pre><p>
Without the import statement, I would need to do this:
</p>
<pre class="wiki">sage: from sage.numerical.mip import MIPVariable
sage: m = MIPVariable(x,f)
</pre><p>
I can see that importing stuff when Sage is being loaded saves a lot of time explicitly importing that stuff. But a downside is that the global namespace is being polluted with module, class or function names that are not really necessary to load at the start. As more names are put into the global namespace, it takes longer and longer to load Sage.
</p>
TicketwdjWed, 09 Sep 2009 21:20:58 GMTsummary changed
https://trac.sagemath.org/ticket/6869#comment:7
https://trac.sagemath.org/ticket/6869#comment:7
<ul>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] LP and MIP Solvers in Sage ( with symbolics )</em> to <em>[with patch, positive review] LP and MIP Solvers in Sage ( with symbolics )</em>
</li>
</ul>
<p>
This applies fine to 4.1.2.a0 on an ubuntu 9.04 machine and passes sage -testall (with no packages, eg glpk, applied). The docstrings look fine (as before).
</p>
<p>
I then applies glpk and reran sage -testall. All tests passes sage -testall except this:
</p>
<pre class="wiki">
wdj@tinah:~/sagefiles/sage-4.1.2.alpha0$ ./sage -t "devel/sage/sage/server/notebook/cell.py"
sage -t "devel/sage/sage/server/notebook/cell.py"
*** *** Error: TIMED OUT! PROCESS KILLED! *** ***
*** *** Error: TIMED OUT! *** ***
*** *** Error: TIMED OUT! *** ***
[366.5 s]
exit code: 1024
</pre><p>
I doubt this is related, so giving this a positive review.
</p>
TicketmvnguThu, 10 Sep 2009 11:07:54 GMT
https://trac.sagemath.org/ticket/6869#comment:8
https://trac.sagemath.org/ticket/6869#comment:8
<p>
See <a class="closed ticket" href="https://trac.sagemath.org/ticket/6913" title="defect: __eq__ methods for the classes in numerical.MIP (closed: fixed)">#6913</a> for a follow-up to this ticket. It addresses the issue of writing those <code>__eq__()</code> methods.
</p>
TicketmvnguThu, 10 Sep 2009 11:36:16 GMTstatus changed; reviewer, resolution, merged, author set
https://trac.sagemath.org/ticket/6869#comment:9
https://trac.sagemath.org/ticket/6869#comment:9
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>closed</em>
</li>
<li><strong>reviewer</strong>
set to <em>David Joyner, Minh Van Nguyen</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>Sage 4.1.2.alpha2</em>
</li>
<li><strong>author</strong>
set to <em>Nathann Cohen</em>
</li>
</ul>
TicketmhansenFri, 25 Sep 2009 07:42:39 GMT
https://trac.sagemath.org/ticket/6869#comment:10
https://trac.sagemath.org/ticket/6869#comment:10
<p>
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,
</p>
<ol><li>Almost all of the docstrings are incorrectly formatted.
</li></ol><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><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><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 have some code that addresses some of these things that I'll put up shortly.
</p>
TicketmvnguFri, 25 Sep 2009 08:08:41 GMT
https://trac.sagemath.org/ticket/6869#comment:11
https://trac.sagemath.org/ticket/6869#comment:11
<p>
See <a class="closed ticket" href="https://trac.sagemath.org/ticket/7012" title="defect: clean up sage/numerical/mip.pyx (closed: fixed)">#7012</a> for a follow up to this ticket. It addresses mhansen's suggestions.
</p>
Ticket