Sage: Ticket #19097: Refactor run_[revised]_simplex_method; add run_dual_[revised]_simplex_method
https://trac.sagemath.org/ticket/19097
<p>
This patch refactors the <code>InteractiveLPProblemStandardForm</code> methods <code>run_simplex_method</code> and <code>run_revised_simplex_method</code> by moving the bulk of their implementations to dictionary methods.
</p>
<p>
It also implements the dual simplex method, adding methods <code>run_dual_simplex_method</code> to both <code>InteractiveLPProblemStandardForm</code> and dictionary classes.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/19097
Trac 1.1.6mkoeppeMon, 12 Oct 2015 21:42:04 GMTbranch set
https://trac.sagemath.org/ticket/19097#comment:1
https://trac.sagemath.org/ticket/19097#comment:1
<ul>
<li><strong>branch</strong>
set to <em>u/mkoeppe/dual_simplex_method</em>
</li>
</ul>
TicketnovoseltMon, 12 Oct 2015 22:32:28 GMTcommit set
https://trac.sagemath.org/ticket/19097#comment:2
https://trac.sagemath.org/ticket/19097#comment:2
<ul>
<li><strong>commit</strong>
set to <em>528c8d3451b2d2bc63f8967e5846f5d5dc18dde5</em>
</li>
</ul>
<p>
I would very much appreciate more discussion and planning before charging in with changes to the existing code.
</p>
<p>
As I have said before - <code>ELLUL</code> is not necessarily the best name in the first place and for revised dictionaries it just does not make sense. For regular dictionaries where one can see for simple problems entering/leaving pairs right away, it is a convenient shortcut for entering
</p>
<pre class="wiki">D.enter(1)
D.leave(2)
show(D)
D.update()
show(D)
</pre><p>
and even here the necessity of first show is questionable since all if does is repeating the old output with different colours that convey no new information - it is just visually pleasing to some extent.
</p>
<p>
With revised dictionaries, however, a student CANNOT determine the leaving variable before setting the entering one and either displaying the dictionary (which will have new information allowing picking leaving) or at least asking for ratios. A typical sequence of commands for a single step is then
</p>
<pre class="wiki">D.enter(1)
show(D)
D.leave(2)
show(D)
D.update()
show(D)
</pre><p>
where the intermediate show may be dropped since it does not add anything but colours.
</p>
<p>
Of course, that's what one does when working "by hand" and for an automated solution one may want to show ONLY that "unnecessary" intermediate dictionary with all the information and colours.
</p>
<p>
So how about:
</p>
<ul><li>do not add new stupidly named methods (I am allowed to call <code>ELLUL</code> stupid since I've invented it ;-))
</li><li>add <code>run_simplex_method</code> and <code>run_dual_simplex_method</code> to abstract dictionaries with implementation relying on abstract methods only and something like <code>_preupdate_output</code> (empty string or None by default) to allow stuff like inversion of matrices in the revised case, we'll get something like
<pre class="wiki">if not self.is_feasible():
ValueError("simplex method is applicable to feasible dictionaries only")
while not self.is_optimal():
entering = min(self.possible_entering())
self.enter(entering)
leaving = min(self.possible_leaving())
if leaving is not None:
self.leave(leaving)
add_to_output(latex(self))
if leaving is None:
add_to_output("The problem is unbounded in ${}$ direction.".format(latex(entering)))
break
add_to_output("Entering: ${}$. Leaving: ${}$.".format(latex(entering), latex(leaving))))
add_to_output(self._preupdate_output)
self.update()
if self.is_optimal():
add_to_output(latex(self))
return output_as_HTMLFragment
</pre></li><li>simplify <code>run_simplex_method</code> etc in the problems that will now build a bigger HTMLFragment based on the stuff returned from dictionaries.
</li></ul><p>
In 6.9 it is possible to create <code>HTMLFragments</code> and my thinking here is
</p>
<pre class="wiki">\begin{array} %dictionary
...
\end{array}
Entering $x_1$. Leaving $x_2$.
\begin{array}
...
\end{array}
...
</pre><p>
which will work both as HTML code (with <a class="missing wiki">MathJax?</a> drawing only small formulas rather than everything as a single nested array) and as LaTeX code (with automatic pagination since again formulas are as small as actual formulas rather than the current situation). It is not going to display nicely yet in the notebook or cloud but hopefully we can work on it during 6.10 release cycle. I've made necessary adjustments to the notebook: <a class="ext-link" href="https://github.com/sagemath/sagenb/pull/350"><span class="icon"></span>https://github.com/sagemath/sagenb/pull/350</a> and work is under way to fit rich output system into cloud.
</p>
<p>
How does this sound? I am happy to implement the above for current dictionaries and leave you the dual ones.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=528c8d3451b2d2bc63f8967e5846f5d5dc18dde5"><span class="icon"></span>528c8d3</a></td><td><code>New: run_dual_simplex_method</code>
</td></tr></table>
TicketmkoeppeMon, 12 Oct 2015 22:52:47 GMT
https://trac.sagemath.org/ticket/19097#comment:3
https://trac.sagemath.org/ticket/19097#comment:3
<p>
Thanks for taking a look.
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19097#comment:2" title="Comment 2">novoselt</a>:
</p>
<blockquote class="citation">
<p>
As I have said before - <code>ELLUL</code> is not necessarily the best name in the first place and for revised dictionaries it just does not make sense.
</p>
</blockquote>
<p>
Agreed that ELLUL is not a good name. But there's value in a routine that does "one pivot + output" as a subroutine of the simplex method with output.
</p>
<blockquote class="citation">
<p>
So how about:
</p>
<ul><li>do not add new stupidly named methods (I am allowed to call <code>ELLUL</code> stupid since I've invented it ;-))
</li><li>add <code>run_simplex_method</code> and <code>run_dual_simplex_method</code> to abstract dictionaries with implementation relying on abstract methods only [...]
</li></ul></blockquote>
<p>
Yes.
</p>
<blockquote class="citation">
<ul><li>simplify <code>run_simplex_method</code> etc in the problems that will now build a bigger HTMLFragment based on the stuff returned from dictionaries.
</li></ul></blockquote>
<p>
Agreed.
</p>
<blockquote class="citation">
<p>
In 6.9 it is possible to create <code>HTMLFragments</code> [....]
</p>
</blockquote>
<p>
This sounds like a good direction.
</p>
<blockquote class="citation">
<p>
How does this sound? I am happy to implement the above for current dictionaries and leave you the dual ones.
</p>
</blockquote>
<p>
Sounds good.
</p>
TicketnovoseltTue, 20 Oct 2015 01:33:09 GMTbranch changed
https://trac.sagemath.org/ticket/19097#comment:4
https://trac.sagemath.org/ticket/19097#comment:4
<ul>
<li><strong>branch</strong>
changed from <em>u/mkoeppe/dual_simplex_method</em> to <em>u/novoselt/dual_simplex_method</em>
</li>
</ul>
TicketnovoseltTue, 20 Oct 2015 01:34:26 GMTattachment set
https://trac.sagemath.org/ticket/19097
https://trac.sagemath.org/ticket/19097
<ul>
<li><strong>attachment</strong>
set to <em>19097.pdf</em>
</li>
</ul>
TicketnovoseltTue, 20 Oct 2015 01:45:16 GMTcommit changed
https://trac.sagemath.org/ticket/19097#comment:5
https://trac.sagemath.org/ticket/19097#comment:5
<ul>
<li><strong>commit</strong>
changed from <em>528c8d3451b2d2bc63f8967e5846f5d5dc18dde5</em> to <em>671e58947e62a0fe1812e2b61fa26b5071c1da1c</em>
</li>
</ul>
<p>
OK, here is my first take (not ready for final review, not sufficiently tested yet, and almost certainly not working well with floats). For testing in SageNB you need my fix to it - I am attaching a printout for a getting some sense of how things look like.
</p>
<p>
Note nice pagination for <code>P.run_simplex_method2()</code> due to the fact that each dictionary is a separate formula and compare it to <code>P.run_simplex_method()</code> (old version, single formula) which occupies a separate page but gets truncated.
</p>
<p>
In SMC and perhaps Jupiter notebook you can try it right away, I guess.
</p>
<p>
The float problem is demonstrated here: <a class="ext-link" href="https://sage373.math.ualberta.ca/home/pub/21/"><span class="icon"></span>https://sage373.math.ualberta.ca/home/pub/21/</a> where optimality of the auxiliary dictionary is detected because <code>x0</code> is non-basic. Of course, we can just say that automatic methods are guaranteed to work only for exact rings and otherwise users should decide for themselves where small numbers are actually zeros and treat them appropriately. My worksheet will get broken, but can be recreated with manual steps.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=671e58947e62a0fe1812e2b61fa26b5071c1da1c"><span class="icon"></span>671e589</a></td><td><code>Add run_simplex_method to dictionaries.</code>
</td></tr></table>
TicketmkoeppeTue, 20 Oct 2015 02:34:05 GMT
https://trac.sagemath.org/ticket/19097#comment:6
https://trac.sagemath.org/ticket/19097#comment:6
<p>
Thanks a lot, we'll take a look.
</p>
<p>
For working with floating point (which is unavoidable for our "backend dictionaries" in <a class="closed ticket" href="https://trac.sagemath.org/ticket/18804" title="enhancement: LPBackendDictionary - a debugging view of a MIP backend connected to ... (closed: wontfix)">#18804</a>),
we are working on a solution that should work without any changes to the interactive_simplex_method code.
Take a look at "LPCleanDictionary" in the (preliminary) patch for <a class="closed ticket" href="https://trac.sagemath.org/ticket/18804" title="enhancement: LPBackendDictionary - a debugging view of a MIP backend connected to ... (closed: wontfix)">#18804</a> at <a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?h=u/zwang/temp&id=440ed874635c88940bc0f06c6ed1e913c29d9042"><span class="icon"></span>http://git.sagemath.org/sage.git/commit/?h=u/zwang/temp&id=440ed874635c88940bc0f06c6ed1e913c29d9042</a>
Discussion very welcome.
</p>
TicketgitWed, 21 Oct 2015 00:05:36 GMTcommit changed
https://trac.sagemath.org/ticket/19097#comment:7
https://trac.sagemath.org/ticket/19097#comment:7
<ul>
<li><strong>commit</strong>
changed from <em>671e58947e62a0fe1812e2b61fa26b5071c1da1c</em> to <em>7383d6793332774248e9934b6aad7110c0a99ad5</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=7383d6793332774248e9934b6aad7110c0a99ad5"><span class="icon"></span>7383d67</a></td><td><code>Refactor run_simplex_method to dictionaries and LP problems.</code>
</td></tr></table>
TicketnovoseltWed, 21 Oct 2015 00:11:20 GMT
https://trac.sagemath.org/ticket/19097#comment:8
https://trac.sagemath.org/ticket/19097#comment:8
<p>
OK, let's just drop floating workarounds here. I've made some more changes, but still didn't test it extensively.
</p>
<p>
By the way - which frontend are you working with? Ideally it should not matter, of course. In this version I got rid of "notruncate" in HTML comments (necessary for SageNB) - it is still present as LaTeX comment inside of environments for dictionaries.
</p>
TicketgitThu, 22 Oct 2015 16:56:22 GMTcommit changed
https://trac.sagemath.org/ticket/19097#comment:9
https://trac.sagemath.org/ticket/19097#comment:9
<ul>
<li><strong>commit</strong>
changed from <em>7383d6793332774248e9934b6aad7110c0a99ad5</em> to <em>63fa3857f40d5944786ec69840c34eccc24a0e44</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=dc702601f55531cc6b60d4fe8a84fc6499c5a008"><span class="icon"></span>dc70260</a></td><td><code>Add run_dual_simplex_method to dictionaries.</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=63fa3857f40d5944786ec69840c34eccc24a0e44"><span class="icon"></span>63fa385</a></td><td><code>Fix handling of unbounded/infeasible problems and add tests.</code>
</td></tr></table>
TicketnovoseltThu, 22 Oct 2015 16:59:37 GMT
https://trac.sagemath.org/ticket/19097#comment:10
https://trac.sagemath.org/ticket/19097#comment:10
<p>
After refactoring adding dual method was almost trivial, so I've done it, ran some tests, and fixed a mistake in handling unbounded/infeasible problems in dictionaries. Ready for review apart from the fact that SageNB support is not there yet.
</p>
TicketnovoseltThu, 22 Oct 2015 17:07:43 GMT
https://trac.sagemath.org/ticket/19097#comment:11
https://trac.sagemath.org/ticket/19097#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19097#comment:3" title="Comment 3">mkoeppe</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19097#comment:2" title="Comment 2">novoselt</a>:
</p>
<blockquote class="citation">
<p>
As I have said before - <code>ELLUL</code> is not necessarily the best name in the first place and for revised dictionaries it just does not make sense.
</p>
</blockquote>
<p>
Agreed that ELLUL is not a good name. But there's value in a routine that does "one pivot + output" as a subroutine of the simplex method with output.
</p>
</blockquote>
<p>
What value? In what concrete situation? In the code it does not simplify your work much since it is not a problem to do enter-leave-update with a snapshot at necessary places. For interactive work, as I have pointed out, it does not make sense for revised dictionaries, because it is <strong>impossible</strong> to pick leaving without looking at the extra stuff computed only after picking entering. I am very much tempted to deprecate the current <code>ELLUL</code> even for regular dictionaries to cease discussions about it once and for all.
</p>
<p>
Note also that the new implementation of <code>run_simplex_method</code> does not rely on it. This makes it possible to use generic method for dictionaries, cuts length of formulas in half (useful both for not wasting paper and for speedy response in browsers), and contains just as much information as before.
</p>
TicketmkoeppeThu, 22 Oct 2015 17:22:03 GMT
https://trac.sagemath.org/ticket/19097#comment:12
https://trac.sagemath.org/ticket/19097#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19097#comment:11" title="Comment 11">novoselt</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19097#comment:3" title="Comment 3">mkoeppe</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19097#comment:2" title="Comment 2">novoselt</a>:
</p>
<blockquote class="citation">
<p>
As I have said before - <code>ELLUL</code> is not necessarily the best name in the first place and for revised dictionaries it just does not make sense.
</p>
</blockquote>
<p>
Agreed that ELLUL is not a good name. But there's value in a routine that does "one pivot + output" as a subroutine of the simplex method with output.
</p>
</blockquote>
<p>
What value? In what concrete situation? In the code it does not simplify your work much since it is not a problem to do enter-leave-update with a snapshot at necessary places. For interactive work, as I have pointed out, it does not make sense for revised dictionaries, because it is <strong>impossible</strong> to pick leaving without looking at the extra stuff computed only after picking entering. I am very much tempted to deprecate the current <code>ELLUL</code> even for regular dictionaries to cease discussions about it once and for all.
</p>
<p>
Note also that the new implementation of <code>run_simplex_method</code> does not rely on it. This makes it possible to use generic method for dictionaries, cuts length of formulas in half (useful both for not wasting paper and for speedy response in browsers), and contains just as much information as before.
</p>
</blockquote>
<p>
I retract my comment. I think your current design is very nice. We can work with it for the cutting plane method. 'll rebase our cutting plane work on top of this branch.
</p>
<p>
I agree that deprecating ELLUL would be a good idea, as it is specific to the primal tableau simplex.
</p>
<p>
Perhaps _preupdate_output should accept an argument whether it's in the primal or the dual, to avoid guessing.
</p>
TicketgitSun, 25 Oct 2015 21:40:19 GMTcommit changed
https://trac.sagemath.org/ticket/19097#comment:13
https://trac.sagemath.org/ticket/19097#comment:13
<ul>
<li><strong>commit</strong>
changed from <em>63fa3857f40d5944786ec69840c34eccc24a0e44</em> to <em>586d0fa61bc4dcb946558a16358d90e737d4960f</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=586d0fa61bc4dcb946558a16358d90e737d4960f"><span class="icon"></span>586d0fa</a></td><td><code>No guess in _preupdate_output, deprecate ELLUL, infeasibility message.</code>
</td></tr></table>
TicketnovoseltSun, 25 Oct 2015 21:41:32 GMT
https://trac.sagemath.org/ticket/19097#comment:14
https://trac.sagemath.org/ticket/19097#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19097#comment:12" title="Comment 12">mkoeppe</a>:
</p>
<blockquote class="citation">
<p>
Perhaps _preupdate_output should accept an argument whether it's in the primal or the dual, to avoid guessing.
</p>
</blockquote>
<p>
I thought about it, but for some reason didn't want to. As I can no longer remember the reason, I've changed it to an argument.
</p>
<p>
Deprecated <code>ELLUL</code>.
</p>
<p>
Changed the message for infeasible problems to indicate the problematic constraint/variable, mirroring "unbounded in x5 direction".
</p>
TicketpjxiaoSun, 01 Nov 2015 23:57:56 GMTauthor changed; owner, reviewer set
https://trac.sagemath.org/ticket/19097#comment:15
https://trac.sagemath.org/ticket/19097#comment:15
<ul>
<li><strong>owner</strong>
changed from <em>(none)</em> to <em>pjxiao</em>
</li>
<li><strong>reviewer</strong>
set to <em>pjxiao</em>
</li>
<li><strong>author</strong>
changed from <em>Peijun Xiao</em> to <em>Andrey Novoseltsev</em>
</li>
</ul>
TicketpjxiaoSun, 01 Nov 2015 23:58:25 GMTstatus changed
https://trac.sagemath.org/ticket/19097#comment:16
https://trac.sagemath.org/ticket/19097#comment:16
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketpjxiaoSun, 01 Nov 2015 23:58:37 GMTstatus changed
https://trac.sagemath.org/ticket/19097#comment:17
https://trac.sagemath.org/ticket/19097#comment:17
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketnovoseltMon, 02 Nov 2015 15:23:36 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/19097#comment:18
https://trac.sagemath.org/ticket/19097#comment:18
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>PR350 to SageNB</em>
</li>
</ul>
<p>
<strong>Do not merge this until SageNB shipped with Sage supports it! </strong>
</p>
TicketnovoseltFri, 27 Nov 2015 00:09:56 GMTstatus changed; dependencies set; work_issues deleted
https://trac.sagemath.org/ticket/19097#comment:19
https://trac.sagemath.org/ticket/19097#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>dependencies</strong>
set to <em>#19616</em>
</li>
<li><strong>work_issues</strong>
<em>PR350 to SageNB</em> deleted
</li>
</ul>
TicketjdemeyerThu, 10 Dec 2015 08:35:26 GMTstatus, milestone changed
https://trac.sagemath.org/ticket/19097#comment:20
https://trac.sagemath.org/ticket/19097#comment:20
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_info</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.9</em> to <em>sage-6.11</em>
</li>
</ul>
<p>
Reviewer name please...
</p>
TicketmkoeppeWed, 16 Dec 2015 00:06:32 GMTstatus, reviewer changed
https://trac.sagemath.org/ticket/19097#comment:21
https://trac.sagemath.org/ticket/19097#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
changed from <em>pjxiao</em> to <em>Peijun Xiao</em>
</li>
</ul>
TicketvbraunTue, 22 Dec 2015 19:49:49 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/19097#comment:22
https://trac.sagemath.org/ticket/19097#comment:22
<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>branch</strong>
changed from <em>u/novoselt/dual_simplex_method</em> to <em>586d0fa61bc4dcb946558a16358d90e737d4960f</em>
</li>
</ul>
Ticket