Opened 4 years ago

Closed 4 years ago

#18742 closed task (fixed)

interactive_simplex_method: Support several styles corresponding to major textbooks

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, Andrey Novoseltsev Reviewers: Andrey Novoseltsev, Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: 8ce0dee (Commits) Commit: 8ce0dee91782d7676b40556792f5a9351efccfb2
Dependencies: Stopgaps:

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 (29)

comment:1 Changed 4 years ago by mkoeppe

  • Cc pjxiao added

comment:2 follow-up: Changed 4 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 4 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 4 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 4 years ago by mkoeppe

  • Branch set to u/mkoeppe/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks

comment:6 Changed 4 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 4 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 4 years ago by mkoeppe

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

comment:9 follow-up: Changed 4 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 4 years ago by mkoeppe

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

comment:11 Changed 4 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 4 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 4 years ago by mkoeppe

  • Status changed from needs_work to needs_review

comment:14 Changed 4 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 4 years ago by mkoeppe

  • Description modified (diff)

comment:16 Changed 4 years ago by novoselt

Sorry for delay - the new version looks good to me! I'll now go over changes carefully to fix some typos and change "my" style a little, e.g. it was on my list to add minus for the objective of "negative maximization" dictionaries, as otherwise it is confusing.

comment:17 Changed 4 years ago by novoselt

OK, there is a problem: there was already objective parameter for problems in standard form. Renaming it to objective_variable and changing its place is a backward-incompatible change which is not worth the effort, I think. How about I revert to objective where it was in place, and change objective_variable to objective where it is new for consistency?

comment:18 follow-up: Changed 4 years ago by novoselt

Also I am not sure if you have noticed, but there are 4 types of problems: "max", "min", and "-max", "-min". Do you want to always set up dictionaries for maximization and put minus sign in front of its objective depending on whether the constant term of the "objective expression" is the actual value or not? Then it should be (say) "z" for "max" and "-min" and "-z" for "-max" and "min". If this sounds reasonable, I'll make this change for both styles, so that only actual naming of the variable is different.

Follow up to the previous - if you are unhappy with plain objective, how about dictionary_objective or objective_name instead? Calling expressions potentially including negative signs objective_variable seems confusing. Also, not insisting on plain names allows for adding constant terms to objective in the future.

comment:19 in reply to: ↑ 18 Changed 4 years ago by mkoeppe

Replying to novoselt:

Also I am not sure if you have noticed, but there are 4 types of problems: "max", "min", and "-max", "-min". Do you want to always set up dictionaries for maximization and put minus sign in front of its objective depending on whether the constant term of the "objective expression" is the actual value or not? Then it should be (say) "z" for "max" and "-min" and "-z" for "-max" and "min". If this sounds reasonable, I'll make this change for both styles, so that only actual naming of the variable is different.

In Vanderbei, primal dictionaries are always "max zeta", and dual dictionaries are always "-max -xi". The other cases do not appear; so any decision what to do with those will be consistent and fine with me.

Follow up to the previous - if you are unhappy with plain objective, how about dictionary_objective or objective_name instead? Calling expressions potentially including negative signs objective_variable seems confusing. Also, not insisting on plain names allows for adding constant terms to objective in the future.

"objective_name" sounds fine to me. With "objective", I think there is a risk of confusion with the objective coefficients.

In comment 17, you wrote:

there was already objective parameter for problems in standard form. Renaming it to objective_variable and changing its place is a backward-incompatible change which is not worth the effort, I think. How about I revert to objective where it was in place, and change objective_variable to objective where it is new for consistency?

If you are really concerned about backwards incompatibility for this code, then this solution as you propose would seem fine.

Last edited 4 years ago by mkoeppe (previous) (diff)

comment:20 Changed 4 years ago by novoselt

  • Status changed from needs_review to needs_work
  • Work issues set to clean up default names logic

Old naming system relied a lot on prefix that has unclear meaning in presence of style, working on resolving the issues...

comment:21 Changed 4 years ago by novoselt

  • Branch changed from u/mkoeppe/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks to u/novoselt/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks

comment:22 follow-up: Changed 4 years ago by novoselt

  • Commit changed from 3fdf390c77a726cbbdcc899150823780348ac1f2 to 8f5c7a43f2109a30f7e0dd95df1218a66c96e836

Nitpicks:

  • Every function has to have input/output blocks if there is any input/output.
  • Copy-pasting is bad in general and lead to some mistakes in dictionary code and documentation.

More substantial:

  • The point of style is to affect output and automatic choice of names which also really matter only when displayed. Therefore LPAbstractDictionary has nothing to do with the style and since there was no customization for LPRevisedDictionary let's not through in extra arguments there.
  • I still feel like overall logic will be cleaner if there was a single style rather than separate for each problem - no need to drug style arguments around and pass it along to every newly constructed instance, or engage in aforementioned copy-pasting. I just don't see under what circumstances someone will want to actively work with different styles at once. Can I rewrite things without style argument to problems/dictionaries?
  • As I have not heard about others using this module before, perhaps we can be somewhat relaxed about backward compatibility. In fact, I'd like to break it even more since with your changes prefix argument has unclear meaning and gets in the way. (This change is done in my commit.)
  • I am thinking about collecting all name choices into a dictionary which is then referred to in appropriate places, otherwise things are difficult to keep in sync. With dictionaries adding another style would mean: add a new dictionary with desired default names and tweak output methods as appropriate. No need to go through all functions that can construct a problem or dictionary. (So far the only output differences were presence of frame and position of the objective. In general things can be more different, but just in the latex method.) The use for the dictionary would be something like
    if slack_variable is None:
        slack_variable = _default_name[style]["slack variable"]
    

  • Is there any default auxiliary variable name in Vanderbei?

New commits:

5362dddMerge tag '6.8' into t/18742/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks
8f5c7a4Clean up style changes for interactive simplex method.

comment:23 in reply to: ↑ 22 ; follow-up: Changed 4 years ago by mkoeppe

Replying to novoselt:

Nitpicks:

  • Every function has to have input/output blocks if there is any input/output.

Do you want us to work on this, or do you plan to make more changes?

  • Copy-pasting is bad in general and lead to some mistakes in dictionary code and documentation.

More substantial:

  • The point of style is to affect output and automatic choice of names which also really matter only when displayed. Therefore LPAbstractDictionary has nothing to do with the style and since there was no customization for LPRevisedDictionary let's not through in extra arguments there.
  • I still feel like overall logic will be cleaner if there was a single style rather than separate for each problem - no need to drug style arguments around and pass it along to every newly constructed instance, or engage in aforementioned copy-pasting. I just don't see under what circumstances someone will want to actively work with different styles at once. Can I rewrite things without style argument to problems/dictionaries?

Since the style affects default names of primal and dual, I would be a bit concerned about what happens when a user creates a problem P, then changes the global style, then dualizes the problem. However, if this can be done consistently, I have no strong objections to having just a global style variable.

  • As I have not heard about others using this module before, perhaps we can be somewhat relaxed about backward compatibility. In fact, I'd like to break it even more since with your changes prefix argument has unclear meaning and gets in the way. (This change is done in my commit.)
  • I am thinking about collecting all name choices into a dictionary which is then referred to in appropriate places, otherwise things are difficult to keep in sync. With dictionaries adding another style would mean: add a new dictionary with desired default names and tweak output methods as appropriate. No need to go through all functions that can construct a problem or dictionary. (So far the only output differences were presence of frame and position of the objective. In general things can be more different, but just in the latex method.) The use for the dictionary would be something like
    if slack_variable is None:
        slack_variable = _default_name[style]["slack variable"]
    

I think this is a great idea.

  • Is there any default auxiliary variable name in Vanderbei?

What do you mean by auxiliary variable? The one in a primal phase I? That's x0.

comment:24 in reply to: ↑ 23 ; follow-up: Changed 4 years ago by novoselt

  • Work issues changed from clean up default names logic to switch to dictionaries of default names

Replying to mkoeppe:

Replying to novoselt:

  • Every function has to have input/output blocks if there is any input/output.

Do you want us to work on this, or do you plan to make more changes?

I've changed it in my commit ;-)

  • I still feel like overall logic will be cleaner if there was a single style rather than separate for each problem - no need to drug style arguments around and pass it along to every newly constructed instance, or engage in aforementioned copy-pasting. I just don't see under what circumstances someone will want to actively work with different styles at once. Can I rewrite things without style argument to problems/dictionaries?

Since the style affects default names of primal and dual, I would be a bit concerned about what happens when a user creates a problem P, then changes the global style, then dualizes the problem. However, if this can be done consistently, I have no strong objections to having just a global style variable.

There will be some mix of default naming schemes. But: 1) this should not affect correctness of anything, 2) there will still be an option to override names, 3) I don't see it as a use case. I think that the most likely situation is that users will use whatever style is the default one (so there is some sense in picking "the most common one" as the default). Those who do figure out the style option are most likely to use it in the beginning of a session and roll with it. Those who discover it midway will likely still put it into beginning and rerun all commands. I don't have any facts to support these speculations, of course, but I will be surprised if they are wrong.

  • Is there any default auxiliary variable name in Vanderbei?

What do you mean by auxiliary variable? The one in a primal phase I? That's x0.

Yes - that's the one. It should be x0 at the moment in both styles.

My plan for tomorrow is to implement the dictionary approach for the names. And get rid of style argument if I manage to convince you about it ;-)

comment:25 in reply to: ↑ 24 Changed 4 years ago by mkoeppe

Replying to novoselt:

Replying to mkoeppe:

Since the style affects default names of primal and dual, I would be a bit concerned about what happens when a user creates a problem P, then changes the global style, then dualizes the problem. However, if this can be done consistently, I have no strong objections to having just a global style variable.

There will be some mix of default naming schemes. But: 1) this should not affect correctness of anything, 2) there will still be an option to override names, 3) I don't see it as a use case. I think that the most likely situation is that users will use whatever style is the default one (so there is some sense in picking "the most common one" as the default). Those who do figure out the style option are most likely to use it in the beginning of a session and roll with it. Those who discover it midway will likely still put it into beginning and rerun all commands. I don't have any facts to support these speculations, of course, but I will be surprised if they are wrong. My plan for tomorrow is to implement the dictionary approach for the names. And get rid of style argument if I manage to convince you about it ;-)

OK, fine.

comment:26 Changed 4 years ago by git

  • Commit changed from 8f5c7a43f2109a30f7e0dd95df1218a66c96e836 to 8ce0dee91782d7676b40556792f5a9351efccfb2

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

64be135Use a dictionary for default names associated to the style.
8ce0deeUse only global style for problems and dictionaries.

comment:27 Changed 4 years ago by novoselt

  • Authors changed from Peijun Xiao, Matthias Koeppe to Peijun Xiao, Matthias Koeppe, Andrey Novoseltsev
  • Reviewers changed from Andrey Novoseltsev to Andrey Novoseltsev, Matthias Koeppe
  • Status changed from needs_work to needs_review
  • Work issues switch to dictionaries of default names deleted

If you are OK with the current state, please set to the positive review!

comment:28 Changed 4 years ago by mkoeppe

  • Status changed from needs_review to positive_review

comment:29 Changed 4 years ago by vbraun

  • Branch changed from u/novoselt/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks to 8ce0dee91782d7676b40556792f5a9351efccfb2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.