Opened 10 years ago

Closed 8 years ago

# Add interactive simplex method module

Reported by: Owned by: Andrey Novoseltsev Nathann Cohen major sage-6.3 linear programming sd58 Dima Pasechnik, Nathann Cohen Andrey Novoseltsev Travis Scrimshaw N/A 65cb842

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.

### comment:1 Changed 10 years ago by Andrey Novoseltsev

Cc: Dima Pasechnik Nathann Cohen added modified (diff) new → 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 10 years ago by Dima Pasechnik

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.

### comment:3 follow-up:  4 Changed 10 years ago by Andrey Novoseltsev

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 10 years ago by Dima Pasechnik

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:  6 Changed 10 years ago by Andrey Novoseltsev

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 10 years ago by Dima Pasechnik

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 10 years ago by Andrey Novoseltsev

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 Jeroen Demeyer

Milestone: sage-5.11 → sage-5.12

### comment:9 Changed 9 years ago by Andrey Novoseltsev

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 9 years ago by Andrey Novoseltsev

Description: modified (diff)

### comment:11 Changed 9 years ago by For batch modifications

Milestone: sage-6.1 → sage-6.2

### comment:12 Changed 9 years ago by Frédéric Chapoton

Status: needs_review → needs_work

needs a git branch

### comment:14 Changed 9 years ago by Andrey Novoseltsev

Commit: → b9180099a2ec0af8ceb3c5a05c1a9e7af868b9bf 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 git

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 git

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 For batch modifications

Milestone: sage-6.2 → sage-6.3

### comment:18 Changed 9 years ago by git

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 git

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 git

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 git

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 Frédéric Chapoton

Branch: u/novoselt/add_interactive_simplex_method_module → public/ticket/14288 8394df4bdcba536e8645d6c36a21344e4580f462 → f1b82be958b1d4d1653a57113b087ca349818788

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`

### comment:23 Changed 8 years ago by git

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 Andrey Novoseltsev

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 Andrey Novoseltsev

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 Travis Scrimshaw

Reviewers: → Travis Scrimshaw needs_review → positive_review

Then positive review. Thanks for implementing this!

### comment:28 Changed 8 years ago by Volker Braun

Status: positive_review → 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 8 years ago by git

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 Travis Scrimshaw

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] 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] 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 Volker Braun

Branch: public/ticket/14288 → 65cb842d67549494f3a6b1c71f193a4dca328fae → fixed positive_review → closed

### comment:32 Changed 8 years ago by Nathann Cohen

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

Note: See TracTickets for help on using tickets.