Opened 7 years ago

Closed 7 years ago

#18742 closed task (fixed)

interactive_simplex_method: Support several styles corresponding to major textbooks

Reported by: Matthias Köppe Owned by:
Priority: minor Milestone: sage-6.8
Component: numerical Keywords: beginner, lp, teaching
Cc: Andrey Novoseltsev, Nathann Cohen, Yuan Zhou, Peijun Xiao Merged in:
Authors: Peijun Xiao, Matthias Koeppe, Andrey Novoseltsev Reviewers: Andrey Novoseltsev, Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: 8ce0dee (Commits, GitHub, GitLab) Commit: 8ce0dee91782d7676b40556792f5a9351efccfb2
Dependencies: Stopgaps:

Status badges

Description (last modified by Matthias Köppe)

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 7 years ago by Matthias Köppe

Cc: Peijun Xiao added

comment:2 Changed 7 years ago by Andrey Novoseltsev

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

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 7 years ago by Matthias Köppe

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 7 years ago by Matthias Köppe

Branch: u/mkoeppe/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks

comment:6 Changed 7 years ago by Matthias Köppe

Authors: Peijun Xiao
Commit: 3a539dce741428cd08b80a2eef028a9d60bcc106
Status: newneeds_review

New commits:

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

comment:7 Changed 7 years ago by git

Commit: 3a539dce741428cd08b80a2eef028a9d60bcc1061a2845ffc2768bde19a9e7a29e3d9131aa79e278

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 7 years ago by Matthias Köppe

Authors: Peijun XiaoPeijun Xiao, Matthias Koeppe

comment:9 Changed 7 years ago by Andrey Novoseltsev

Reviewers: Andrey Novoseltsev
Status: needs_reviewneeds_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 7 years ago by Matthias Köppe

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

comment:11 Changed 7 years ago by git

Commit: 1a2845ffc2768bde19a9e7a29e3d9131aa79e278ae43611e6ba76e9b2d56ef46bce456adcc93370f

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 7 years ago by Matthias Köppe

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 7 years ago by Matthias Köppe

Status: needs_workneeds_review

comment:14 Changed 7 years ago by git

Commit: ae43611e6ba76e9b2d56ef46bce456adcc93370f3fdf390c77a726cbbdcc899150823780348ac1f2

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

3fdf390Reformat to fix error in make doc-html

comment:15 Changed 7 years ago by Matthias Köppe

Description: modified (diff)

comment:16 Changed 7 years ago by Andrey Novoseltsev

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

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

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 7 years ago by Matthias Köppe

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 7 years ago by Matthias Köppe (previous) (diff)

comment:20 Changed 7 years ago by Andrey Novoseltsev

Status: needs_reviewneeds_work
Work issues: 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 7 years ago by Andrey Novoseltsev

Branch: u/mkoeppe/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooksu/novoselt/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks

comment:22 Changed 7 years ago by Andrey Novoseltsev

Commit: 3fdf390c77a726cbbdcc899150823780348ac1f28f5c7a43f2109a30f7e0dd95df1218a66c96e836

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 ; Changed 7 years ago by Matthias Köppe

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

Work issues: clean up default names logicswitch 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 7 years ago by Matthias Köppe

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

Commit: 8f5c7a43f2109a30f7e0dd95df1218a66c96e8368ce0dee91782d7676b40556792f5a9351efccfb2

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

Authors: Peijun Xiao, Matthias KoeppePeijun Xiao, Matthias Koeppe, Andrey Novoseltsev
Reviewers: Andrey NovoseltsevAndrey Novoseltsev, Matthias Koeppe
Status: needs_workneeds_review
Work issues: switch to dictionaries of default names

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

comment:28 Changed 7 years ago by Matthias Köppe

Status: needs_reviewpositive_review

comment:29 Changed 7 years ago by Volker Braun

Branch: u/novoselt/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks8ce0dee91782d7676b40556792f5a9351efccfb2
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.