#19097: Refactor run_[revised]_simplex_method; add
run_dual_[revised]_simplex_method
-------------------------------------+-------------------------------------
Reporter: mkoeppe | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.9
Component: numerical | Resolution:
Keywords: lp | Merged in:
Authors: Peijun Xiao | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/mkoeppe/dual_simplex_method | 528c8d3451b2d2bc63f8967e5846f5d5dc18dde5
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by novoselt):
* commit: => 528c8d3451b2d2bc63f8967e5846f5d5dc18dde5
Comment:
I would very much appreciate more discussion and planning before charging
in with changes to the existing code.
As I have said before - `ELLUL` 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
{{{
D.enter(1)
D.leave(2)
show(D)
D.update()
show(D)
}}}
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.
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
{{{
D.enter(1)
show(D)
D.leave(2)
show(D)
D.update()
show(D)
}}}
where the intermediate show may be dropped since it does not add anything
but colours.
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.
So how about:
- do not add new stupidly named methods (I am allowed to call `ELLUL`
stupid since I've invented it ;-))
- add `run_simplex_method` and `run_dual_simplex_method` to abstract
dictionaries with implementation relying on abstract methods only and
something like `_preupdate_output` (empty string or None by default) to
allow stuff like inversion of matrices in the revised case, we'll get
something like
{{{
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
}}}
- simplify `run_simplex_method` etc in the problems that will now build a
bigger HTMLFragment based on the stuff returned from dictionaries.
In 6.9 it is possible to create `HTMLFragments` and my thinking here is
{{{
\begin{array} %dictionary
...
\end{array}
Entering $x_1$. Leaving $x_2$.
\begin{array}
...
\end{array}
...
}}}
which will work both as HTML code (with MathJax 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: https://github.com/sagemath/sagenb/pull/350 and work is under
way to fit rich output system into cloud.
How does this sound? I am happy to implement the above for current
dictionaries and leave you the dual ones.
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=528c8d3451b2d2bc63f8967e5846f5d5dc18dde5
528c8d3]||{{{New: run_dual_simplex_method}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19097#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
