Refactor run_[revised]_simplex_method; add run_dual_[revised]_simplex_method

[mkoeppe]

This patch refactors the InteractiveLPProblemStandardForm methods run_simplex_method and run_revised_simplex_method by moving the bulk of their implementations to dictionary methods.

It also implements the dual simplex method, adding methods run_dual_simplex_method to both InteractiveLPProblemStandardForm and dictionary classes.

Depends on #19616

CC: @novoselt @yuan-zhou @uduse @pgxiao

Component: numerical

Author: Andrey Novoseltsev

Branch/Commit: 586d0fa

Reviewer: Peijun Xiao

Issue created by migration from https://trac.sagemath.org/ticket/19097

[mkoeppe]

Branch: u/mkoeppe/dual_simplex_method

[novoselt]

Commit: 528c8d3

[novoselt]

comment:2

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: sagemath/sagenb#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:

528c8d3

New: run_dual_simplex_method

[mkoeppe]

comment:3

Thanks for taking a look.

Replying to @novoselt:

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.

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.

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 [...]

Yes.

• simplify run_simplex_method etc in the problems that will now build a bigger HTMLFragment based on the stuff returned from dictionaries.

Agreed.

In 6.9 it is possible to create HTMLFragments [....]

This sounds like a good direction.

How does this sound? I am happy to implement the above for current dictionaries and leave you the dual ones.

Sounds good.

[novoselt]

Changed branch from u/mkoeppe/dual_simplex_method to u/novoselt/dual_simplex_method

[novoselt]

Attachment: 19097.pdf.gz

[novoselt]

comment:5

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.

Note nice pagination for P.run_simplex_method2() due to the fact that each dictionary is a separate formula and compare it to P.run_simplex_method() (old version, single formula) which occupies a separate page but gets truncated.

In SMC and perhaps Jupiter notebook you can try it right away, I guess.

The float problem is demonstrated here: https://sage373.math.ualberta.ca/home/pub/21/ where optimality of the auxiliary dictionary is detected because x0 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.

---

New commits:

671e589

Add run_simplex_method to dictionaries.

[novoselt]

Changed commit from 528c8d3 to 671e589

[mkoeppe]

comment:6

Thanks a lot, we'll take a look.

For working with floating point (which is unavoidable for our "backend dictionaries" in #18804),
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 #18804 at sagemath/sagetrac-mirror@440ed87
Discussion very welcome.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7383d67

Refactor run_simplex_method to dictionaries and LP problems.

[sagetrac-git]

Changed commit from 671e589 to 7383d67

[novoselt]

comment:8

OK, let's just drop floating workarounds here. I've made some more changes, but still didn't test it extensively.

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.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

dc70260	Add run_dual_simplex_method to dictionaries.
63fa385	Fix handling of unbounded/infeasible problems and add tests.

[sagetrac-git]

Changed commit from 7383d67 to 63fa385

[novoselt]

comment:10

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.

[novoselt]

comment:11

Replying to @mkoeppe:

Replying to @novoselt:

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.

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.

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 impossible to pick leaving without looking at the extra stuff computed only after picking entering. I am very much tempted to deprecate the current ELLUL even for regular dictionaries to cease discussions about it once and for all.

Note also that the new implementation of run_simplex_method 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.

[mkoeppe]

comment:12

Replying to @novoselt:

Replying to @mkoeppe:

Replying to @novoselt:

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.

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.

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 impossible to pick leaving without looking at the extra stuff computed only after picking entering. I am very much tempted to deprecate the current ELLUL even for regular dictionaries to cease discussions about it once and for all.

Note also that the new implementation of run_simplex_method 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.

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.

I agree that deprecating ELLUL would be a good idea, as it is specific to the primal tableau simplex.

Perhaps _preupdate_output should accept an argument whether it's in the primal or the dual, to avoid guessing.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

586d0fa

No guess in _preupdate_output, deprecate ELLUL, infeasibility message.

[sagetrac-git]

Changed commit from 63fa385 to 586d0fa

[novoselt]

comment:14

Replying to @mkoeppe:

Perhaps _preupdate_output should accept an argument whether it's in the primal or the dual, to avoid guessing.

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.

Deprecated ELLUL.

Changed the message for infeasible problems to indicate the problematic constraint/variable, mirroring "unbounded in x5 direction".

[pgxiao]

Reviewer: pjxiao

[pgxiao]

Changed author from Peijun Xiao to Andrey Novoseltsev

[novoselt]

comment:18

**Do not merge this until SageNB shipped with Sage supports it! **

[novoselt]

Work Issues: PR350 to SageNB

[novoselt]

Dependencies: #19616

[novoselt]

Changed work issues from PR350 to SageNB to none

[jdemeyer]

comment:20

Reviewer name please...

[mkoeppe]

Changed reviewer from pjxiao to Peijun Xiao

[vbraun]

Changed branch from u/novoselt/dual_simplex_method to 586d0fa