Add interactive simplex method module

[novoselt]

Add a module allowing step-by-step 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.

CC: @dimpase @nathanncohen

Component: linear programming

Keywords: sd58

Author: Andrey Novoseltsev

Branch: 65cb842

Reviewer: Travis Scrimshaw

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

[novoselt]

comment:1

Attachment: trac_14288_link_ism.patch.gz

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 ;-)

[dimpase]

comment:2

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.

[novoselt]

Attachment: trac_14288_interactive_simplex_method.patch.gz

[novoselt]

comment:3

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.

[dimpase]

comment:4

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 sage-devel, I think.

[novoselt]

comment:5

I have started a discussion regarding module/package http://groups.google.com/group/sage-devel/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.

[dimpase]

comment:6

Replying to @novoselt:

I have started a discussion regarding module/package http://groups.google.com/group/sage-devel/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 6-10 months, thanks mainly to Volker.

[novoselt]

comment:7

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.)

[novoselt]

Attachment: trac_14288_later_changes.patch.gz

[novoselt]

comment:9

Update on my thinking: after looking closer into backends I am quite convinced that I don't want to do it - the standard front-end 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.

[fchapoton]

comment:12

needs a git branch

[novoselt]

Branch: u/novoselt/add_interactive_simplex_method_module

[novoselt]

Commit: b918009

[novoselt]

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.

[sagetrac-git]

Changed commit from 916f590 to 601d39a

[sagetrac-git]

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

601d39a

Construct vectors in base_ring, not ZZ

[sagetrac-git]

Changed commit from 601d39a to 8394df4

[sagetrac-git]

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

8394df4

Improve LaTeXing again.

[fchapoton]

Changed commit from 8394df4 to f1b82be

[fchapoton]

Changed branch from u/novoselt/add_interactive_simplex_method_module to public/ticket/14288

[fchapoton]

comment:22

I have changed the doctest continuations from ... to ....:

This should allow the patchbot to give a green light.

---

New commits:

6575677	Merge branch 'u/novoselt/add_interactive_simplex_method_module' of ssh://trac.sagemath.org:22/sage into 14288
f1b82be	trac #14288 correct doctest continuations

[sagetrac-git]

Changed commit from f1b82be to b541f0e

[sagetrac-git]

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.

[novoselt]

comment:24

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.

[novoselt]

comment:25

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 ;-)

[tscrim]

comment:26

Then positive review. Thanks for implementing this!

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

Changed keywords from none to sd58

[vbraun]

comment:28

[numerical] /home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/numerical/interactive_simplex_method.py:docstring of sage.numerical.interactive_simplex_method:30: ERROR: Unexpected indentation.
[numerical] /home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/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/buildslave-sage/slave/sage_git/build/src/doc/common/builder.py", line 1490, in <module>
    getattr(get_builder(name), type)()
  File "/home/buildslave-sage/slave/sage_git/build/src/doc/common/builder.py", line 291, in _wrapper
    getattr(get_builder(document), 'inventory')(*args, **kwds)
  File "/home/buildslave-sage/slave/sage_git/build/src/doc/common/builder.py", line 502, in _wrapper
    x.get(99999)
  File "/home/buildslave-sage/slave/sage_git/build/local/lib/python/multiprocessing/pool.py", line 558, in get
    raise self._value
OSError: [numerical] /home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/numerical/interactive_simplex_method.py:docstring of sage.numerical.interactive_simplex_method:30: ERROR: Unexpected indentation.

[sagetrac-git]

Changed commit from b541f0e to 65cb842

[sagetrac-git]

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

65cb842

Added space where it was not suppose to be. Fixed this.

[tscrim]

comment:30

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 py-modindex 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

[vbraun]

Changed branch from public/ticket/14288 to 65cb842

[nathanncohen]

Changed commit from 65cb842 to none

[nathanncohen]

comment:32

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