Opened 6 years ago
Closed 6 years ago
#20311 closed enhancement (fixed)
interactive_simplex_method enhancements
Reported by:  novoselt  Owned by:  

Priority:  major  Milestone:  sage7.2 
Component:  numerical  Keywords:  lp 
Cc:  mkoeppe  Merged in:  
Authors:  Andrey Novoseltsev  Reviewers:  Matthias Koeppe 
Report Upstream:  N/A  Work issues:  
Branch:  7145f7d (Commits, GitHub, GitLab)  Commit:  7145f7d14ada975e9025efddb5852af6fa79eed8 
Dependencies:  Stopgaps: 
Description
Allow constant terms in the objective, check solutions for feasibility and optimality, transformation map from standard form to the original one.
Change History (40)
comment:1 Changed 6 years ago by
 Branch set to u/novoselt/ISM_enchancements
comment:2 Changed 6 years ago by
 Branch u/novoselt/ISM_enchancements deleted
 Cc mkoeppe added
 Status changed from new to needs_review
comment:3 Changed 6 years ago by
 Branch set to u/novoselt/ISM_enchancements
 Commit set to f2e52f8f613d423f83ee9806b23b3aacefae2156
comment:4 Changed 6 years ago by
The standardform transformation works well with #20296. Thanks very much! (I'll update the branch of #20296 when this ticket is merged.)
Some issues:
 I think the constant term should appear in the latex representation of the problem when nonzero.
 And it also needs to be passed through to
InteractiveLPProblemStandardForm
instandard_form
. I have added a (failing) doctest.
 And then
InteractiveLPProblemStandardForm
needs to pass it on to the dictionaries...
 I think there should be a doctest that illustrates how the constant term interacts with
is_negative
.
 Passing
slack_variables
as a keyword argument tostandard_form
is a bit of an awkward interface, though, becausestandard_form
may split equations and so the user would have to anticipate this. Perhaps it would be better to provide a list of "row_names" instead and modify that somehow when equations are split.
comment:5 Changed 6 years ago by
 Status changed from needs_review to needs_work
comment:6 Changed 6 years ago by
 Reviewers set to Matthias Koeppe
comment:7 Changed 6 years ago by
 Branch changed from u/novoselt/ISM_enchancements to u/mkoeppe/ISM_enchancements
comment:8 Changed 6 years ago by
 Commit changed from f2e52f8f613d423f83ee9806b23b3aacefae2156 to ec31ed65e3624affa79298d2bb8d414600b85e47
I'll probably work on it next weekend. For the record  it is not a good idea to edit old comments as apparently there are no notifications sent about it and it was a bit of an accident that I looked up.
Also, bloody trac does not let me post reply comments for no reason, but:
 I think problems should be typeset as
10 + max 5 x1  7 x2
, i.e. with constant term first and out of max/min as it makes it easier to "get rid of it" when desirable.  I was not sure about the standard form, but probably it should include the constant term as well. And the dual problem has to be adjusted to make sure that optimal values still agree.
 For dictionaries convenient typesetting is probably in the objective as a part of its "name", as in
5  z = 10 x1 + 9 x2
 Interaction with negativity should also clearly documented.
 For "row_names"  I'd rather not introduce even more concepts and logic. If a user cares about slack names, he better know what they are and how they are formed. Also, if the only issue is the base name clash (without index), then the number of constraints does not matter, just pass that base name and indices will be taken care of.
New commits:
ec31ed6  InteractiveLPProblem.standard_form: Add doctest for objective_constant_term

comment:9 Changed 6 years ago by
Thanks! Sounds good.
comment:10 Changed 6 years ago by
 Branch changed from u/mkoeppe/ISM_enchancements to u/novoselt/ISM_enchancements
comment:11 Changed 6 years ago by
 Commit changed from ec31ed65e3624affa79298d2bb8d414600b85e47 to 992c5ea1d2bcab0898dac5751a850d5ec7c053f9
 Status changed from needs_work to needs_review
New commits:
992c5ea  Typeset constant term and clarify negativity interaction.

comment:12 Changed 6 years ago by
 Status changed from needs_review to needs_work
I think the constant term also needs to be reflected in run_simplex_method
and run_revised_simplex_method
.
(Maybe the support for constant terms is a bit too complicated for the interactive simplex method after all?)
comment:13 followup: ↓ 14 Changed 6 years ago by
Well, it definitely adds very little from the didactic point of view, mostly just annoying thing to remember ;) But since we have started and for the sake of being able to convert other problems to this type let's finish the job. What exactly is the problem with the simplex method? My hope was that things will take care of themselves there but I guess they don't.
comment:14 in reply to: ↑ 13 Changed 6 years ago by
Replying to novoselt:
What exactly is the problem with the simplex method? My hope was that things will take care of themselves there but I guess they don't.
It prints the nonshifted objective value. I suppose things would take care of themselves if the objective constant term were put in the constant (on the right hand side) of the dictionary, rather than into the objective name.
comment:15 Changed 6 years ago by
That will complicate alignment for typesetting and in general it seemed fitting to put it on the left where the negative sign goes as well for minimization problems. I'll think some more about it.
comment:16 Changed 6 years ago by
Well, the dictionary already typesets a constant for the objective function  that's the value of the dictionary. There's no need to distinguish these two constants from each other  it's quite natural; the simplex method manipulates a dictionary of affinelinear functions.
comment:17 followup: ↓ 18 Changed 6 years ago by
You are right of course, and this will eliminate different meanings for objective_value
. Although it would be better then to typeset objective with constant inside of min/max, which is probably more natural anyway.
comment:18 in reply to: ↑ 17 Changed 6 years ago by
Replying to novoselt:
Although it would be better then to typeset objective with constant inside of min/max, which is probably more natural anyway.
I agree.
comment:19 Changed 6 years ago by
 Commit changed from 992c5ea1d2bcab0898dac5751a850d5ec7c053f9 to 580b57f5af4ec143c031eae2926cb8b83333b13f
Branch pushed to git repo; I updated commit sha1. New commits:
580b57f  Merge 7.2.beta3 into t/20311/ISM_enchancements

comment:20 Changed 6 years ago by
 Commit changed from 580b57f5af4ec143c031eae2926cb8b83333b13f to 4d7afcab44af70dfa5063624d02c1b8ddd2b2b64
Branch pushed to git repo; I updated commit sha1. New commits:
4d7afca  Fixes to the objective constant term treatment.

comment:21 Changed 6 years ago by
 Status changed from needs_work to needs_review
OK, how about this one? I've also renamed value(x)
to objective_value(x)
to be more clear.
comment:22 followup: ↓ 24 Changed 6 years ago by
I think it would be better to keep the notions of [in]feasible problem and [in]feasible solution separate.
Don't overload is_feasible
with both meanings. Better have a new method is_solution_feasible
and likewise rename is_optimal
to is_solution_optimal
.
comment:23 Changed 6 years ago by
@@ 1914,6 +2134,7 @@ class InteractiveLPProblemStandardForm(InteractiveLPProblem): A = A.matrix_from_columns(range(k) + range(k + 1, n)) b = copy(b) c = vector(self.base_ring(), n  1) + v = self._constant_term for cj, xj in zip(*self.Abcx()[2:]): if xj in N: c[N.index(xj)] += cj
This v
doesn't seem to get used
comment:24 in reply to: ↑ 22 Changed 6 years ago by
Replying to mkoeppe:
I think it would be better to keep the notions of [in]feasible problem and [in]feasible solution separate. Don't overload
is_feasible
with both meanings. Better have a new methodis_solution_feasible
and likewise renameis_optimal
tois_solution_optimal
.
No confusion is possible in use and I planned to do it for a long time without any second thoughts  several students have actually asked for exactly this ;)
comment:25 Changed 6 years ago by
v
propagates to the dictionary constructor. It happened to be initialized with 0 before.
comment:26 Changed 6 years ago by
In my experience, the persistent confusion of students about the notions of feasible problems, feasible solutions, and feasible dictionaries is the number 1 frustration in teaching the simplex method
comment:27 followup: ↓ 28 Changed 6 years ago by
If you are looking at commits in a browser, there is a handy selector in topright for the number of context lines, which allows to see such changes in context.
comment:28 in reply to: ↑ 27 Changed 6 years ago by
Replying to novoselt:
If you are looking at commits in a browser, there is a handy selector in topright for the number of context lines, which allows to see such changes in context.
Thanks! Yes, I was only reading the diff at this point
comment:29 Changed 6 years ago by
Agreed about confusion, but the questions in human language are:
A) Is this problem feasible? B) Is this solution for this problem feasible?
which I want to translate in code to
A) problem.is_feasible()
B) problem.is_feasible(solution)
and find very natural and not adding any confusion at all.
Most students also feel no difference between
C) problem.optimal_value()
D) optimal_dictionary.objective_value()
since they do give the same values. Yet
C') problem.work_hard_to_find_optimal_value()
D') optimal_dictionary.just_read_off_the_objective_value_you_store()
are not the right way to teach them the difference.
comment:30 Changed 6 years ago by
I think my concern regarding A and B is in part because of Python defaulting semantics.
If the solution
argument is missing, people could assume that is_feasible
somehow talks about the feasibility of some "default" solution (perhaps some "current" solution).
I don't have a concern regarding the naming of C and D in the code.
comment:31 followup: ↓ 32 Changed 6 years ago by
What is default/current solution for a problem???
My point with C and D was that it is again just direct translation of "the human language" into code with neither solves nor adds confusion.
How about going with the current addition and seeing how (and with what degree of confusion) it will be received? Overloading methods is a common practice and we can always deprecate the use of arguments if it turns out to be bad.
comment:32 in reply to: ↑ 31 Changed 6 years ago by
Replying to novoselt:
What is default/current solution for a problem???
Well, *I* know that in your design the problem is immutable, but a user might think that if he goes pivoting in "the" dictionary obtained from initial_dictionary
, this has some effect on the problem.
How about going with the current addition and seeing how (and with what degree of confusion) it will be received? Overloading methods is a common practice and we can always deprecate the use of arguments if it turns out to be bad.
OK, fine.
comment:33 Changed 6 years ago by
It seems the constant terms don't work the right way for minimization problems. Probably in the standard_form
method the sign needs to be flipped.
(I have a test for this in InteractiveLPBackend.)
comment:34 Changed 6 years ago by
See #20413.
comment:35 Changed 6 years ago by
 Branch changed from u/novoselt/ISM_enchancements to u/mkoeppe/ISM_enchancements
comment:36 Changed 6 years ago by
 Commit changed from 4d7afcab44af70dfa5063624d02c1b8ddd2b2b64 to 78d0e784dfd4bb497c1b179f8fa8f645d334fdaa
I have added a testcase.
New commits:
78d0e78  InteractiveLPProblem.standard_form: Add doctest for minimization with objective_constant_term

comment:37 Changed 6 years ago by
 Branch changed from u/mkoeppe/ISM_enchancements to u/novoselt/ISM_enchancements
comment:38 Changed 6 years ago by
 Commit changed from 78d0e784dfd4bb497c1b179f8fa8f645d334fdaa to 7145f7d14ada975e9025efddb5852af6fa79eed8
Yes, of course  thanks for thorough testing!
New commits:
7145f7d  Flip the constant term sign when converting min problems to standard form.

comment:39 Changed 6 years ago by
 Keywords lp added
 Status changed from needs_review to positive_review
Thanks a lot for your work on this ticket!
comment:40 Changed 6 years ago by
 Branch changed from u/novoselt/ISM_enchancements to 7145f7d14ada975e9025efddb5852af6fa79eed8
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
Pass arguments through InteractiveLPProblem.standard_form.
Allow objective constant terms for InteractiveLPProblem.
Infeasible problems are bounded!
Add checks for feasible/optimal solutions of InteractiveLPProblem
Return coordinate transformation for problems in standard form.