#14288 closed enhancement (fixed)
Add interactive simplex method module
Reported by:  Andrey Novoseltsev  Owned by:  Nathann Cohen 

Priority:  major  Milestone:  sage6.3 
Component:  linear programming  Keywords:  sd58 
Cc:  Dima Pasechnik, Nathann Cohen  Merged in:  
Authors:  Andrey Novoseltsev  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  65cb842 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
Add a module allowing stepbystep use of the simplex method and its variants.
It is likely to be much slower than "real solvers"  no comparison was made as the point of this module is to facilitate teaching and learning of the simplex method. (The most complicated parts of the module are _latex_
methods of problems and dictionaries!)
Some worksheets showing it in action can be usually seen at https://sage373.math.ualberta.ca/pub/ and I can provide more upon request to interested people.
Attachments (3)
Change History (35)
Changed 10 years ago by
Attachment:  trac_14288_link_ism.patch added 

comment:1 Changed 10 years ago by
Cc:  Dima Pasechnik Nathann Cohen added 

Description:  modified (diff) 
Status:  new → needs_review 
comment:2 Changed 10 years ago by
IMHO this should be an optional package. It's quite different from the rest of Sage library, as I cannot recall any place where an effort is made to "deconstruct" an algorithm, preparing it for undergraduate teaching.
I started to look at the patch. There seems to be a numeric discrepancy in the 1st example. Indeed, on line 38 A = ([1, 1], [3, 1])
corresponds to 1 kg per acre needed for barley, not 5.
Then, "regular LP solvers"
on line 7 reads strangely. I'd have written "regular" LP solvers
.
Also, "the final answer"
on line 8 looks weird. This reads too fatalistic, and brings in "the final solution"
, something that one should avoid due to its damned German translation. I'd have just written the result
, without quotes.
Changed 10 years ago by
Attachment:  trac_14288_interactive_simplex_method.patch added 

comment:3 followup: 4 Changed 10 years ago by
I've fixed The Example (thanks for catching it, I would always read it with the numbers I have in mind after so many hours of discussing it!) and rephrased the quoted bits.
Regarding "final"  I also used "final dictionary" to refer to the dictionary where the simplex method stops. It does not have to be optimal and can be for the auxiliary problem, so final seemed like a suitable choice to me, but perhaps there are better alternatives.
As for a module or an optional package, a module definitely has more visibility (and testing!) and there are efforts to make Sage better for undergraduate teaching, so it didn't seem to me that this one will be inappropriate. Of course, I am biased, so I'll be happy to repackage if necessary.
comment:4 Changed 10 years ago by
Replying to novoselt:
I've fixed The Example (thanks for catching it, I would always read it with the numbers I have in mind after so many hours of discussing it!) and rephrased the quoted bits.
Regarding "final"  I also used "final dictionary" to refer to the dictionary where the simplex method stops. It does not have to be optimal and can be for the auxiliary problem, so final seemed like a suitable choice to me, but perhaps there are better alternatives.
yes, certainly "final dictionary" (without quotes) is an established terminology in simplex method, but you really do not want to use Final Solution, and "final answer" is too close to the latter, and is not established terminology anyway.
As for a module or an optional package, a module definitely has more visibility (and testing!) and there are efforts to make Sage better for undergraduate teaching, so it didn't seem to me that this one will be inappropriate. Of course, I am biased, so I'll be happy to repackage if necessary.
As a module, it would not belong to sage/numerical/
(redesigning it as a backend to Sage LP functionality seems to be like way too much work for little gain, although I'm not 100% sure). Perhaps one can create sage/teaching/
or something like this, for this kind of material, but this should be discussed and voted upon in sagedevel, I think.
comment:5 followup: 6 Changed 10 years ago by
I have started a discussion regarding module/package http://groups.google.com/group/sagedevel/browse_thread/thread/ba43be235367db60
I am pretty sure that there is no point in redesigning it as a backend, as it was written to be the frontend. A year and a half ago I tried to use Sage for this class and found that: a) entering problems is somewhat involved and can confuse students with interface details; b) showing constructed problems was far from good; and mainly c) there was no way to deal with and nicely display dictionaries. This is not to say that Sage LP functionality was/is bad, it is just made for other things.
comment:6 Changed 10 years ago by
Replying to novoselt:
I have started a discussion regarding module/package http://groups.google.com/group/sagedevel/browse_thread/thread/ba43be235367db60
I am pretty sure that there is no point in redesigning it as a backend, as it was written to be the frontend. A year and a half ago I tried to use Sage for this class and found that:
a) entering problems is somewhat involved and can confuse students with interface details;
a simplified way can be added to Sage LP frontend, e.g. allowing to enter matrices of constraints is very easy, I gather.
b) showing constructed problems was far from good;
again, this could be worked on...
and mainly c) there was no way to deal with and nicely display dictionaries.
I suppose one can make things supported by your (not yet) backend interact nicely with Sage's frontend.
E.g., for a LP p
do something like p.do_one_pivot(...)
, and e.g. p.show_current_solution()
.
The advantage would be that then it could become a part of sage/numerical/
. But perhaps this is not worth the trouble, and this code just should go elsewhere.
In fact, the frontend has improved quite a bit in the past 610 months, thanks mainly to Volker.
comment:7 Changed 10 years ago by
OK, it seems that overall happiness lies in the direction of modifying it as a backend, so I'll look closer into it. (Meanwhile, posted patches are fully functional and documented, so it still makes sense for interested people to look over them.)
comment:8 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

Changed 9 years ago by
Attachment:  trac_14288_later_changes.patch added 

comment:9 Changed 9 years ago by
Description:  modified (diff) 

Update on my thinking: after looking closer into backends I am quite convinced that I don't want to do it  the standard frontend for MILP in Sage is not what is need for learning the simplex method and having to always go to special backend features would be awkward and terrifying for a number of students.
So my plan it to keep the module as is now with gradual improvements to handling rounding errors for inexact fields and to latexing. The advantage of having it as a patch/branch as opposed to a completely separate module is that there is no need to have a load command in each worksheet and it is definitely important for me, so perhaps for some other people as well.
comment:10 Changed 9 years ago by
Description:  modified (diff) 

comment:11 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:13 Changed 9 years ago by
Branch:  → u/novoselt/add_interactive_simplex_method_module 

comment:14 Changed 9 years ago by
Commit:  → b9180099a2ec0af8ceb3c5a05c1a9e7af868b9bf 

Status:  needs_work → needs_review 
New commits:
2516209  Add a module for interactive simplex method exploration.

edaa6d8  Bind interactive simplex method module into documentation and global namespace.

33ce200  Adjustments to the new interactive simplex method module.

a70cedd  Make it work with current Sage.

b918009  Change default variables to free to match #15521.

comment:15 Changed 9 years ago by
Commit:  b9180099a2ec0af8ceb3c5a05c1a9e7af868b9bf → e6570d87b077ba9682dd55e5f563006ab98f8f5e 

Branch pushed to git repo; I updated commit sha1. New commits:
e6570d8  Don't rely on LPProblem defaults in LPProblemStandardForm.

comment:16 Changed 9 years ago by
Commit:  e6570d87b077ba9682dd55e5f563006ab98f8f5e → 8eda6c6b3bbdf693a878122dc431e66ff4679e6b 

Branch pushed to git repo; I updated commit sha1. New commits:
8eda6c6  Be more careful with detecting "negative" coefficients for LaTeX.

comment:17 Changed 9 years ago by
Milestone:  sage6.2 → sage6.3 

comment:18 Changed 9 years ago by
Commit:  8eda6c6b3bbdf693a878122dc431e66ff4679e6b → 0d7a8564c5c9467739562ea05e1c07c0331e56e7 

Branch pushed to git repo; I updated commit sha1. New commits:
def8ae4  Add a module for interactive simplex method exploration.

e4aaa9f  Bind interactive simplex method module into documentation and global namespace.

1a5d3d5  Adjustments to the new interactive simplex method module.

a413b46  Make it work with current Sage.

477529e  Change default variables to free to match #15521.

af649c1  Don't rely on LPProblem defaults in LPProblemStandardForm.

916f590  Be more careful with detecting "negative" coefficients for LaTeX.

0d7a856  Merge branch 'u/novoselt/add_interactive_simplex_method_module' of trac.sagemath.org:sage into t/14288/add_interactive_simplex_method_module

comment:19 Changed 9 years ago by
Commit:  0d7a8564c5c9467739562ea05e1c07c0331e56e7 → 916f5909ddacc40557e4120d9969628502482c8e 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
comment:20 Changed 8 years ago by
Commit:  916f5909ddacc40557e4120d9969628502482c8e → 601d39acde0fd78f497e945c3a3e941d39a48150 

Branch pushed to git repo; I updated commit sha1. New commits:
601d39a  Construct vectors in base_ring, not ZZ

comment:21 Changed 8 years ago by
Commit:  601d39acde0fd78f497e945c3a3e941d39a48150 → 8394df4bdcba536e8645d6c36a21344e4580f462 

Branch pushed to git repo; I updated commit sha1. New commits:
8394df4  Improve LaTeXing again.

comment:22 Changed 8 years ago by
Branch:  u/novoselt/add_interactive_simplex_method_module → public/ticket/14288 

Commit:  8394df4bdcba536e8645d6c36a21344e4580f462 → f1b82be958b1d4d1653a57113b087ca349818788 
comment:23 Changed 8 years ago by
Commit:  f1b82be958b1d4d1653a57113b087ca349818788 → b541f0e0b737e378ebd92f167aed38242ce6a8ed 

Branch pushed to git repo; I updated commit sha1. New commits:
dba9b70  Merge branch 'u/novoselt/add_interactive_simplex_method_module' of trac.sagemath.org:sage into u/novoselt/add_interactive_simplex_method_module

29c331d  Merge branch 'public/ticket/14288' of trac.sagemath.org:sage into u/novoselt/add_interactive_simplex_method_module

aa1fdf0  First pass: documentation formatting.

21ce795  Some more formatting and minor tweaks.

b541f0e  Last review tweaks.

comment:24 Changed 8 years ago by
Can we please not do overall whitespace changes so that it is possible to see what actually has been done? "First pass" commit is mostly about white space and touches half the file, yet there are some other changes in it as well.
comment:25 Changed 8 years ago by
Also, there are changes like replace " a" to " A" and remove dot in the end of output  what's the point? Do we have a fixed standard for such formatting or not? If yes, I'll be happy to comply. If it is left to the author, then I am pretty sure that I had consistent style at least for this file and now it is not.
Of course, if you are willing to set it to positive review, I'll be happy with whatever formatting changes ;)
comment:26 Changed 8 years ago by
Reviewers:  → Travis Scrimshaw 

Status:  needs_review → positive_review 
Then positive review. Thanks for implementing this!
comment:27 Changed 8 years ago by
Keywords:  sd58 added 

comment:28 Changed 8 years ago by
Status:  positive_review → needs_work 

[numerical] /home/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/numerical/interactive_simplex_method.py:docstring of sage.numerical.interactive_simplex_method:30: ERROR: Unexpected indentation. [numerical] /home/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/numerical/interactive_simplex_method.py:docstring of sage.numerical.interactive_simplex_method:31: WARNING: Block quote ends without a blank line; unexpected unindent. Error building the documentation. Traceback (most recent call last): File "/home/buildslavesage/slave/sage_git/build/src/doc/common/builder.py", line 1490, in <module> getattr(get_builder(name), type)() File "/home/buildslavesage/slave/sage_git/build/src/doc/common/builder.py", line 291, in _wrapper getattr(get_builder(document), 'inventory')(*args, **kwds) File "/home/buildslavesage/slave/sage_git/build/src/doc/common/builder.py", line 502, in _wrapper x.get(99999) File "/home/buildslavesage/slave/sage_git/build/local/lib/python/multiprocessing/pool.py", line 558, in get raise self._value OSError: [numerical] /home/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/numerical/interactive_simplex_method.py:docstring of sage.numerical.interactive_simplex_method:30: ERROR: Unexpected indentation.
comment:29 Changed 8 years ago by
Commit:  b541f0e0b737e378ebd92f167aed38242ce6a8ed → 65cb842d67549494f3a6b1c71f193a4dca328fae 

Branch pushed to git repo; I updated commit sha1. New commits:
65cb842  Added space where it was not suppose to be. Fixed this.

comment:30 Changed 8 years ago by
Status:  needs_work → positive_review 

My fault in keeping the lines to char 79 width. Fixed.
[numerical] building [html]: targets for 1 source files that are out of date [numerical] updating environment: 0 added, 1 changed, 0 removed [numerical] reading sources... [100%] sage/numerical/interactive_simplex_method loading cross citations... done (680 citations). [numerical] pickling environment... done [numerical] checking consistency... done [numerical] preparing documents... done [numerical] writing output... [ 50%] index writing output... [100%] sage/numerical/interactive_simplex_method [numerical] writing additional files... genindex pymodindex search [numerical] linking _static directory. [numerical] dumping search index... done [numerical] dumping object inventory... done [numerical] build succeeded. Build finished. The built documents can be found in /home/travis/sage/src/doc/output/html/en/reference/numerical
comment:31 Changed 8 years ago by
Branch:  public/ticket/14288 → 65cb842d67549494f3a6b1c71f193a4dca328fae 

Resolution:  → fixed 
Status:  positive_review → closed 
comment:32 Changed 8 years ago by
Commit:  65cb842d67549494f3a6b1c71f193a4dca328fae 

There is a serious risk of confusion here. This class, meant for educational purposes only, imports a class called LPProblem
in the global namespace.
People who just want to solve LP *WILL* run into a wall.
Nathann
Dear Dima and Nathan: as you have some interest in linear programming, perhaps you will find this ticket interesting for teaching and would be willing to glance over it?
Preliminary versions of the module were used to teach 2 sections of Math 373 Mathematical Programming and Optimization I at the University of Alberta, the current one is planned to be actively used during the Spring term (May 8  June 12) and it would be awesome to get some feedback before it, at least on whether someone else thinks that it should go into Sage ;)