Opened 7 years ago

Closed 5 years ago

Last modified 5 years ago

#14288 closed enhancement (fixed)

Add interactive simplex method module

Reported by: novoselt Owned by: ncohen
Priority: major Milestone: sage-6.3
Component: linear programming Keywords: sd58
Cc: dimpase, ncohen Merged in:
Authors: Andrey Novoseltsev Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 65cb842 (Commits) Commit:
Dependencies: Stopgaps:

Description (last modified by 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.

Attachments (3)

trac_14288_link_ism.patch (1.1 KB) - added by novoselt 7 years ago.
trac_14288_interactive_simplex_method.patch (132.7 KB) - added by novoselt 7 years ago.
trac_14288_later_changes.patch (8.3 KB) - added by novoselt 6 years ago.

Download all attachments as: .zip

Change History (35)

Changed 7 years ago by novoselt

comment:1 Changed 7 years ago by novoselt

  • Cc dimpase ncohen added
  • Description modified (diff)
  • Status changed from new to needs_review

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

comment:2 Changed 7 years ago by dimpase

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 7 years ago by novoselt

comment:3 follow-up: Changed 7 years ago by 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.

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 in reply to: ↑ 3 Changed 7 years ago by dimpase

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.

comment:5 follow-up: Changed 7 years ago by 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; 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 in reply to: ↑ 5 Changed 7 years ago by dimpase

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.

comment:7 Changed 7 years ago by novoselt

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 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

Changed 6 years ago by novoselt

comment:9 Changed 6 years ago by novoselt

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

comment:10 Changed 6 years ago by novoselt

  • Description modified (diff)

comment:11 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:12 Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

needs a git branch

comment:13 Changed 5 years ago by novoselt

  • Branch set to u/novoselt/add_interactive_simplex_method_module

comment:14 Changed 5 years ago by novoselt

  • Commit set to b9180099a2ec0af8ceb3c5a05c1a9e7af868b9bf
  • Status changed from needs_work to needs_review

New commits:

2516209Add a module for interactive simplex method exploration.
edaa6d8Bind interactive simplex method module into documentation and global namespace.
33ce200Adjustments to the new interactive simplex method module.
a70ceddMake it work with current Sage.
b918009Change default variables to free to match #15521.

comment:15 Changed 5 years ago by git

  • Commit changed from b9180099a2ec0af8ceb3c5a05c1a9e7af868b9bf to e6570d87b077ba9682dd55e5f563006ab98f8f5e

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

e6570d8Don't rely on LPProblem defaults in LPProblemStandardForm.

comment:16 Changed 5 years ago by git

  • Commit changed from e6570d87b077ba9682dd55e5f563006ab98f8f5e to 8eda6c6b3bbdf693a878122dc431e66ff4679e6b

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

8eda6c6Be more careful with detecting "negative" coefficients for LaTeX.

comment:17 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:18 Changed 5 years ago by git

  • Commit changed from 8eda6c6b3bbdf693a878122dc431e66ff4679e6b to 0d7a8564c5c9467739562ea05e1c07c0331e56e7

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

def8ae4Add a module for interactive simplex method exploration.
e4aaa9fBind interactive simplex method module into documentation and global namespace.
1a5d3d5Adjustments to the new interactive simplex method module.
a413b46Make it work with current Sage.
477529eChange default variables to free to match #15521.
af649c1Don't rely on LPProblem defaults in LPProblemStandardForm.
916f590Be more careful with detecting "negative" coefficients for LaTeX.
0d7a856Merge branch 'u/novoselt/add_interactive_simplex_method_module' of trac.sagemath.org:sage into t/14288/add_interactive_simplex_method_module

comment:19 Changed 5 years ago by git

  • Commit changed from 0d7a8564c5c9467739562ea05e1c07c0331e56e7 to 916f5909ddacc40557e4120d9969628502482c8e

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

comment:20 Changed 5 years ago by git

  • Commit changed from 916f5909ddacc40557e4120d9969628502482c8e to 601d39acde0fd78f497e945c3a3e941d39a48150

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

601d39aConstruct vectors in base_ring, not ZZ

comment:21 Changed 5 years ago by git

  • Commit changed from 601d39acde0fd78f497e945c3a3e941d39a48150 to 8394df4bdcba536e8645d6c36a21344e4580f462

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

8394df4Improve LaTeXing again.

comment:22 Changed 5 years ago by chapoton

  • Branch changed from u/novoselt/add_interactive_simplex_method_module to public/ticket/14288
  • Commit changed from 8394df4bdcba536e8645d6c36a21344e4580f462 to f1b82be958b1d4d1653a57113b087ca349818788

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

This should allow the patchbot to give a green light.


New commits:

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

comment:23 Changed 5 years ago by git

  • Commit changed from f1b82be958b1d4d1653a57113b087ca349818788 to b541f0e0b737e378ebd92f167aed38242ce6a8ed

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

dba9b70Merge branch 'u/novoselt/add_interactive_simplex_method_module' of trac.sagemath.org:sage into u/novoselt/add_interactive_simplex_method_module
29c331dMerge branch 'public/ticket/14288' of trac.sagemath.org:sage into u/novoselt/add_interactive_simplex_method_module
aa1fdf0First pass: documentation formatting.
21ce795Some more formatting and minor tweaks.
b541f0eLast review tweaks.

comment:24 Changed 5 years ago by novoselt

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 5 years ago by novoselt

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 5 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

Then positive review. Thanks for implementing this!

comment:27 Changed 5 years ago by tscrim

  • Keywords sd58 added

comment:28 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work
[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.

comment:29 Changed 5 years ago by git

  • Commit changed from b541f0e0b737e378ebd92f167aed38242ce6a8ed to 65cb842d67549494f3a6b1c71f193a4dca328fae

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

65cb842Added space where it was not suppose to be. Fixed this.

comment:30 Changed 5 years ago by tscrim

  • Status changed from needs_work to 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 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

comment:31 Changed 5 years ago by vbraun

  • Branch changed from public/ticket/14288 to 65cb842d67549494f3a6b1c71f193a4dca328fae
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:32 Changed 5 years ago by ncohen

  • Commit 65cb842d67549494f3a6b1c71f193a4dca328fae deleted

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

Note: See TracTickets for help on using tickets.