Opened 6 years ago
Closed 6 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, GitHub, GitLab) | Commit: | 8ce0dee91782d7676b40556792f5a9351efccfb2 |
Dependencies: | Stopgaps: |
Description (last modified by )
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 6 years ago by
- Cc pjxiao added
comment:2 follow-up: ↓ 4 Changed 6 years ago by
comment:3 Changed 6 years ago by
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
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 (likex_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
- Branch set to u/mkoeppe/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks
comment:6 Changed 6 years ago by
- Commit set to 3a539dce741428cd08b80a2eef028a9d60bcc106
- Status changed from new to needs_review
New commits:
3a539dc | Support style='vanderbei' in all interactive_simplex_method classes.
|
comment:7 Changed 6 years ago by
- Commit changed from 3a539dce741428cd08b80a2eef028a9d60bcc106 to 1a2845ffc2768bde19a9e7a29e3d9131aa79e278
Branch pushed to git repo; I updated commit sha1. New commits:
ba2059c | Move method objective_variable to base class InteractiveLPProblem
|
36b00ce | Move defaulting for style and objective_variable to base class InteractiveLPProblem, fix doctests
|
dada1cb | Add and use style() method for interactive lp problems
|
79297b7 | Move style argument handling to base class LPAbstractDictionary
|
21c72d8 | Add and use style() method for dictionaries
|
1a2845f | Implement and use LPRevisedDictionary.objective_variable()
|
comment:8 Changed 6 years ago by
comment:9 follow-up: ↓ 12 Changed 6 years ago by
- 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.
- 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.
- 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.
- 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
Thanks a lot for taking a look and for your comments. We'll work on it.
comment:11 Changed 6 years ago by
- Commit changed from 1a2845ffc2768bde19a9e7a29e3d9131aa79e278 to ae43611e6ba76e9b2d56ef46bce456adcc93370f
comment:12 in reply to: ↑ 9 Changed 6 years ago by
Replying to novoselt:
Hmmm, that's not quite what I thought was going to happen.
- 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).
- 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.
- 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
- Status changed from needs_work to needs_review
comment:14 Changed 6 years ago by
- Commit changed from ae43611e6ba76e9b2d56ef46bce456adcc93370f to 3fdf390c77a726cbbdcc899150823780348ac1f2
Branch pushed to git repo; I updated commit sha1. New commits:
3fdf390 | Reformat to fix error in make doc-html
|
comment:15 Changed 6 years ago by
- Description modified (diff)
comment:16 Changed 6 years ago by
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 6 years ago by
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: ↓ 19 Changed 6 years ago by
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 6 years ago by
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 aboutdictionary_objective
orobjective_name
instead? Calling expressions potentially including negative signsobjective_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.
comment:20 Changed 6 years ago by
- 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 6 years ago by
- 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: ↓ 23 Changed 6 years ago by
- 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. ThereforeLPAbstractDictionary
has nothing to do with the style and since there was no customization forLPRevisedDictionary
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:
5362ddd | Merge tag '6.8' into t/18742/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks
|
8f5c7a4 | Clean up style changes for interactive simplex method.
|
comment:23 in reply to: ↑ 22 ; follow-up: ↓ 24 Changed 6 years ago by
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. ThereforeLPAbstractDictionary
has nothing to do with the style and since there was no customization forLPRevisedDictionary
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: ↓ 25 Changed 6 years ago by
- 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 6 years ago by
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 6 years ago by
- Commit changed from 8f5c7a43f2109a30f7e0dd95df1218a66c96e836 to 8ce0dee91782d7676b40556792f5a9351efccfb2
comment:27 Changed 6 years ago by
- 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 6 years ago by
- Status changed from needs_review to positive_review
comment:29 Changed 6 years ago by
- 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
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 (likex_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.