Opened 6 years ago

Last modified 6 years ago

#18742 closed task

interactive_simplex_method: Support several styles corresponding to major textbooks — at Version 15

Reported by: mkoeppe Owned by:
Priority: minor Milestone: sage-6.8
Component: numerical Keywords: beginner, lp, teaching
Cc: novoselt, ncohen, yzh, pjxiao Merged in:
Authors: Peijun Xiao, Matthias Koeppe Reviewers: Andrey Novoseltsev
Report Upstream: N/A Work issues:
Branch: u/mkoeppe/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks (Commits, GitHub, GitLab) Commit: 3fdf390c77a726cbbdcc899150823780348ac1f2
Dependencies: Stopgaps:

Status badges

Description (last modified by mkoeppe)

I propose to extend the interactive_simplex_method classes so that they take an optional keyword argument "style", which controls several aspects of how the problems and their dictionaries are presented. The style can also be set globally.

For example, if style='Vanderbei' (which we are working on in this ticket), it would follow Robert Vanderbei's popular text. Compared to the current code (which textbook does it follow?), there are differences in the naming of slack variables, of the objective functions, and some subtle formatting differences.

Supporting the styles of some popular textbooks may help making Sage the tool of choice for teaching the simplex method.

Change History (15)

comment:1 Changed 6 years ago by mkoeppe

  • Cc pjxiao added

comment:2 follow-up: Changed 6 years ago by novoselt

It follows lecture notes (based on Chavatal, I think) that I have adapted and modified a bit.

Can you be more clear on what do you want to affect apart from printing out dictionaries and auto-generated names?

I would be against multiple Python attribute synonyms for different parts of the problem/dictionary - I think there has to be a meaningful name for everything (like basic_variables) accompanied perhaps by one short name (like x_B). Otherwise things will be too confusing, especially if different names of the same things are used internally.

Otherwise it would be fantastic to have different output styles, perhaps there should be even an easy way to install user formatters (without altering Sage). Have you tried to use it in teaching, by the way?

There is also a question about "standard form" perhaps, but changing it is likely to require different classes or the code will get too messy, that's the point of any standard form after all - simplify notation by sticking to some convention.

comment:3 Changed 6 years ago by novoselt

By the way - definitely not for this ticket, but I had an idea of adding some parameter that will track operations used by each method and potentially print it out after each command. This would make it clear to students (I hope) that there is a huge difference between checking whether a dictionary is feasible and whether a problem is feasible, or between asking for the objective value corresponding to the basic solution of an optimal dictionary and asking for the optimal value of a problem directly. What do you think about it? While simple in nature it will require going carefully through all methods, so will take some work and make the code a bit less readable for beginners. (Not that I expect students to look at the code anyway.)

comment:4 in reply to: ↑ 2 Changed 6 years ago by mkoeppe

Replying to novoselt:

It follows lecture notes (based on Chavatal, I think) that I have adapted and modified a bit.

Should the style currently implemented be called 'chvatal' then? I don't have my copy at hand to check if it's the same.

Can you be more clear on what do you want to affect apart from printing out dictionaries and auto-generated names?

I think that's mostly it.

I would be against multiple Python attribute synonyms for different parts of the problem/dictionary - I think there has to be a meaningful name for everything (like basic_variables) accompanied perhaps by one short name (like x_B). Otherwise things will be too confusing, especially if different names of the same things are used internally.

I don't have plans to change the Python interface, except for adding these "style=..." parameters.

Maybe later some new methods for new functionality -- for example, Vanderbei has a "dual-based phase 1" method (in section 5.7).

Otherwise it would be fantastic to have different output styles, perhaps there should be even an easy way to install user formatters (without altering Sage).

OK, we should have the first version of the patch ready soon.

Have you tried to use it in teaching, by the way?

No, I discovered your code too late when I taught linear programming in Spring. Used Vanderbei's online pivot tool; but that's getting increasingly difficult to use because of Java security settings.

comment:5 Changed 6 years ago by mkoeppe

  • Branch set to u/mkoeppe/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks

comment:6 Changed 6 years ago by mkoeppe

  • Authors set to Peijun Xiao
  • Commit set to 3a539dce741428cd08b80a2eef028a9d60bcc106
  • Status changed from new to needs_review

New commits:

3a539dcSupport style='vanderbei' in all interactive_simplex_method classes.

comment:7 Changed 6 years ago by git

  • Commit changed from 3a539dce741428cd08b80a2eef028a9d60bcc106 to 1a2845ffc2768bde19a9e7a29e3d9131aa79e278

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

ba2059cMove method objective_variable to base class InteractiveLPProblem
36b00ceMove defaulting for style and objective_variable to base class InteractiveLPProblem, fix doctests
dada1cbAdd and use style() method for interactive lp problems
79297b7Move style argument handling to base class LPAbstractDictionary
21c72d8Add and use style() method for dictionaries
1a2845fImplement and use LPRevisedDictionary.objective_variable()

comment:8 Changed 6 years ago by mkoeppe

  • Authors changed from Peijun Xiao to Peijun Xiao, Matthias Koeppe

comment:9 follow-up: Changed 6 years ago by novoselt

  • Reviewers set to Andrey Novoseltsev
  • Status changed from needs_review to needs_work

Hmmm, that's not quite what I thought was going to happen.

  1. Are there use cases when it is convenient to work a lot with multiple style problems? It seems to me that you probably like one or the other and don't care about other styles at all. Then it would make sense to have a single global style variable (in the module, of course, not in the global user namespace) which the user can set once in the beginning of each session and not worry about it again.
  2. The naming "None" and "vanderbei" could be improved. How about using proper capitalization string for authors, i.e. "Vanderbei" and something more descriptive for the current style, say "UAlberta" since I am not bold enough to claim it under my own name ;-) It may be convenient to also support "default" which will equate to one of the named styles.
  3. The way how style differences are documented makes it a bit hard to follow and most definitely will be hard to expand in the future. How about: have a single function (rather than exposed variable) that changes the style or returns current one, whose docstring lists all possible styles and instead of comparing them to each other has a list of conventions for each (i.e. dictionaries are displayed like ..., default objective variable is ..., default dual variables are ..., etc.) Then adding another style means adding another block to this function without altering others. Functions whose default behaviour depends on the style can just point to that function for details instead of duplicating descriptions.

comment:10 Changed 6 years ago by mkoeppe

Thanks a lot for taking a look and for your comments. We'll work on it.

comment:11 Changed 6 years ago by git

  • Commit changed from 1a2845ffc2768bde19a9e7a29e3d9131aa79e278 to ae43611e6ba76e9b2d56ef46bce456adcc93370f

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

94156aeChange 'vanderbei' to 'Vanderbei'
682a910Revise handling of style arguments.
ae43611Update docstrings to remove duplication of discussion of style and objective_variable.

comment:12 in reply to: ↑ 9 Changed 6 years ago by mkoeppe

Replying to novoselt:

Hmmm, that's not quite what I thought was going to happen.

  1. Are there use cases when it is convenient to work a lot with multiple style problems? It seems to me that you probably like one or the other and don't care about other styles at all. Then it would make sense to have a single global style variable (in the module, of course, not in the global user namespace) which the user can set once in the beginning of each session and not worry about it again.

I have kept the style= keywords and ._style attributes, but now there's a way to get/set a default using the function default_style (not exported).

  1. The naming "None" and "vanderbei" could be improved. How about using proper capitalization string for authors, i.e. "Vanderbei" and something more descriptive for the current style, say "UAlberta" since I am not bold enough to claim it under my own name ;-) It may be convenient to also support "default" which will equate to one of the named styles.

Done.

  1. The way how style differences are documented makes it a bit hard to follow and most definitely will be hard to expand in the future. How about: have a single function (rather than exposed variable) that changes the style or returns current one, whose docstring lists all possible styles and instead of comparing them to each other has a list of conventions for each (i.e. dictionaries are displayed like ..., default objective variable is ..., default dual variables are ..., etc.) Then adding another style means adding another block to this function without altering others. Functions whose default behaviour depends on the style can just point to that function for details instead of duplicating descriptions.

Done. default_style does that.

Please take a look when you get a chance.

comment:13 Changed 6 years ago by mkoeppe

  • Status changed from needs_work to needs_review

comment:14 Changed 6 years ago by git

  • Commit changed from ae43611e6ba76e9b2d56ef46bce456adcc93370f to 3fdf390c77a726cbbdcc899150823780348ac1f2

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

3fdf390Reformat to fix error in make doc-html

comment:15 Changed 6 years ago by mkoeppe

  • Description modified (diff)
Note: See TracTickets for help on using tickets.