Opened 6 years ago
Closed 6 years ago
#19097 closed enhancement (fixed)
Refactor run_[revised]_simplex_method; add run_dual_[revised]_simplex_method
Reported by:  mkoeppe  Owned by:  pjxiao 

Priority:  major  Milestone:  sage7.0 
Component:  numerical  Keywords:  lp 
Cc:  novoselt, yzh, zwang, pjxiao  Merged in:  
Authors:  Andrey Novoseltsev  Reviewers:  Peijun Xiao 
Report Upstream:  N/A  Work issues:  
Branch:  586d0fa (Commits, GitHub, GitLab)  Commit:  586d0fa61bc4dcb946558a16358d90e737d4960f 
Dependencies:  #19616  Stopgaps: 
Description
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.
Attachments (1)
Change History (23)
comment:1 Changed 6 years ago by
 Branch set to u/mkoeppe/dual_simplex_method
comment:2 followup: ↓ 3 Changed 6 years ago by
 Commit set to 528c8d3451b2d2bc63f8967e5846f5d5dc18dde5
comment:3 in reply to: ↑ 2 ; followup: ↓ 11 Changed 6 years ago by
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
andrun_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.
comment:4 Changed 6 years ago by
 Branch changed from u/mkoeppe/dual_simplex_method to u/novoselt/dual_simplex_method
Changed 6 years ago by
comment:5 Changed 6 years ago by
 Commit changed from 528c8d3451b2d2bc63f8967e5846f5d5dc18dde5 to 671e58947e62a0fe1812e2b61fa26b5071c1da1c
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 nonbasic. 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.

comment:6 Changed 6 years ago by
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 http://git.sagemath.org/sage.git/commit/?h=u/zwang/temp&id=440ed874635c88940bc0f06c6ed1e913c29d9042 Discussion very welcome.
comment:7 Changed 6 years ago by
 Commit changed from 671e58947e62a0fe1812e2b61fa26b5071c1da1c to 7383d6793332774248e9934b6aad7110c0a99ad5
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.

comment:8 Changed 6 years ago by
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.
comment:9 Changed 6 years ago by
 Commit changed from 7383d6793332774248e9934b6aad7110c0a99ad5 to 63fa3857f40d5944786ec69840c34eccc24a0e44
comment:10 Changed 6 years ago by
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.
comment:11 in reply to: ↑ 3 ; followup: ↓ 12 Changed 6 years ago by
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 enterleaveupdate 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.
comment:12 in reply to: ↑ 11 ; followup: ↓ 14 Changed 6 years ago by
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 enterleaveupdate 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.
comment:13 Changed 6 years ago by
 Commit changed from 63fa3857f40d5944786ec69840c34eccc24a0e44 to 586d0fa61bc4dcb946558a16358d90e737d4960f
Branch pushed to git repo; I updated commit sha1. New commits:
586d0fa  No guess in _preupdate_output, deprecate ELLUL, infeasibility message.

comment:14 in reply to: ↑ 12 Changed 6 years ago by
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".
comment:15 Changed 6 years ago by
 Owner changed from (none) to pjxiao
 Reviewers set to pjxiao
comment:16 Changed 6 years ago by
 Status changed from new to needs_review
comment:17 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:18 Changed 6 years ago by
 Status changed from positive_review to needs_work
 Work issues set to PR350 to SageNB
Do not merge this until SageNB shipped with Sage supports it!
comment:19 Changed 6 years ago by
 Dependencies set to #19616
 Status changed from needs_work to positive_review
 Work issues PR350 to SageNB deleted
comment:20 Changed 6 years ago by
 Milestone changed from sage6.9 to sage6.11
 Status changed from positive_review to needs_info
Reviewer name please...
comment:21 Changed 6 years ago by
 Reviewers changed from pjxiao to Peijun Xiao
 Status changed from needs_info to positive_review
comment:22 Changed 6 years ago by
 Branch changed from u/novoselt/dual_simplex_method to 586d0fa61bc4dcb946558a16358d90e737d4960f
 Resolution set to fixed
 Status changed from positive_review to closed
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 enteringand 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
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:
ELLUL
stupid since I've invented it ;))run_simplex_method
andrun_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 likerun_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 iswhich 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:
New: run_dual_simplex_method