interactive_simplex_method: Support several styles corresponding to major textbooks

[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.

CC: @novoselt @nathanncohen @yuan-zhou @pgxiao

Component: numerical

Keywords: teaching

Author: Peijun Xiao, Matthias Koeppe, Andrey Novoseltsev

Branch/Commit: 8ce0dee

Reviewer: Andrey Novoseltsev, Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/18742

[novoselt]

comment:2

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.

[novoselt]

comment:3

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.)

[mkoeppe]

comment:4

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.

[mkoeppe]

Branch: u/mkoeppe/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks

[mkoeppe]

Author: Peijun Xiao

[mkoeppe]

Commit: 3a539dc

[mkoeppe]

New commits:

3a539dc

Support style='vanderbei' in all interactive_simplex_method classes.

[sagetrac-git]

Changed commit from 3a539dc to 1a2845f

[sagetrac-git]

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

[mkoeppe]

Changed author from Peijun Xiao to Peijun Xiao, Matthias Koeppe

[novoselt]

comment:9

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.

[novoselt]

Reviewer: Andrey Novoseltsev

[mkoeppe]

comment:10

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

[sagetrac-git]

Changed commit from 1a2845f to ae43611

[sagetrac-git]

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

94156ae	Change 'vanderbei' to 'Vanderbei'
682a910	Revise handling of style arguments.
ae43611	Update docstrings to remove duplication of discussion of style and objective_variable.

[mkoeppe]

comment:12

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).

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.

Done.

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.

Done. default_style does that.

Please take a look when you get a chance.

[sagetrac-git]

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

3fdf390

Reformat to fix error in make doc-html

[sagetrac-git]

Changed commit from ae43611 to 3fdf390

[novoselt]

comment:16

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.

[novoselt]

comment:17

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?

[novoselt]

comment:18

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.

[mkoeppe]

comment:19

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.

[novoselt]

Work Issues: clean up default names logic

[novoselt]

comment:20

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

[novoselt]

Changed branch 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

[novoselt]

comment:22

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:

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.

[novoselt]

Changed commit from 3fdf390 to 8f5c7a4

[mkoeppe]

comment:23

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.

[novoselt]

Changed work issues from clean up default names logic to switch to dictionaries of default names

[novoselt]

comment:24

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 ;-)

[mkoeppe]

comment:25

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.

[sagetrac-git]

Changed commit from 8f5c7a4 to 8ce0dee

[sagetrac-git]

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

64be135	Use a dictionary for default names associated to the style.
8ce0dee	Use only global style for problems and dictionaries.

[novoselt]

Changed author from Peijun Xiao, Matthias Koeppe to Peijun Xiao, Matthias Koeppe, Andrey Novoseltsev

[novoselt]

comment:27

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

[novoselt]

Changed reviewer from Andrey Novoseltsev to Andrey Novoseltsev, Matthias Koeppe

[novoselt]

Changed work issues from switch to dictionaries of default names to none

[vbraun]

Changed branch from u/novoselt/interactive_simplex_method__support_several_styles_corresponding_to_major_textbooks to 8ce0dee