interactive_simplex_method enhancements #20311

novoselt · 2016-03-27T23:32:53Z

Allow constant terms in the objective, check solutions for feasibility and optimality, transformation map from standard form to the original one.

CC: @mkoeppe

Component: numerical

Author: Andrey Novoseltsev

Branch/Commit: 7145f7d

Reviewer: Matthias Koeppe

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

The text was updated successfully, but these errors were encountered:

novoselt · 2016-03-27T23:33:42Z

Branch: u/novoselt/ISM_enchancements

novoselt · 2016-03-27T23:34:34Z

Changed branch from u/novoselt/ISM_enchancements to none

novoselt · 2016-03-27T23:35:26Z

New commits:

`62ddb03`	`Pass arguments through InteractiveLPProblem.standard_form.`
`5777ef9`	`Allow objective constant terms for InteractiveLPProblem.`
`b5f5f91`	`Infeasible problems are bounded!`
`5fd3547`	`Add checks for feasible/optimal solutions of InteractiveLPProblem`
`f2e52f8`	`Return coordinate transformation for problems in standard form.`

novoselt · 2016-03-27T23:35:26Z

Commit: f2e52f8

novoselt · 2016-03-27T23:35:26Z

Branch: u/novoselt/ISM_enchancements

mkoeppe · 2016-03-27T23:49:16Z

comment:4

The standard-form 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 in standard_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 to standard_form is a bit of an awkward interface, though, because standard_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.

mkoeppe · 2016-03-29T04:33:08Z

Reviewer: Matthias Koeppe

mkoeppe · 2016-03-30T03:56:46Z

Changed branch from u/novoselt/ISM_enchancements to u/mkoeppe/ISM_enchancements

novoselt · 2016-03-31T01:50:15Z

Changed commit from f2e52f8 to ec31ed6

novoselt · 2016-03-31T01:50:15Z

comment:8

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`

mkoeppe · 2016-03-31T01:53:22Z

comment:9

Thanks! Sounds good.

novoselt · 2016-04-02T19:53:45Z

Changed branch from u/mkoeppe/ISM_enchancements to u/novoselt/ISM_enchancements

novoselt · 2016-04-02T19:54:15Z

Changed commit from ec31ed6 to 992c5ea

novoselt · 2016-04-02T19:54:15Z

New commits:

`992c5ea`	`Typeset constant term and clarify negativity interaction.`

mkoeppe · 2016-04-04T04:05:45Z

comment:12

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

novoselt · 2016-04-04T04:24:30Z

comment:13

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.

mkoeppe · 2016-04-04T04:44:35Z

comment:14

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 non-shifted 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.

novoselt · 2016-04-04T04:57:22Z

comment:15

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.

mkoeppe · 2016-04-04T05:33:59Z

comment:16

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 affine-linear functions.

sagetrac-git · 2016-04-10T21:30:36Z

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

`4d7afca`	`Fixes to the objective constant term treatment.`

novoselt · 2016-04-10T21:35:24Z

comment:21

OK, how about this one? I've also renamed value(x) to objective_value(x) to be more clear.

mkoeppe · 2016-04-10T22:27:08Z

comment:22

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.

mkoeppe · 2016-04-10T22:31:53Z

comment:23

@@ -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

novoselt · 2016-04-10T22:34:35Z

comment:24

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 method is_solution_feasible and likewise rename is_optimal to is_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 ;-)

novoselt · 2016-04-10T22:36:11Z

comment:25

v propagates to the dictionary constructor. It happened to be initialized with 0 before.

mkoeppe · 2016-04-10T22:37:13Z

comment:26

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

novoselt · 2016-04-10T22:37:55Z

comment:27

If you are looking at commits in a browser, there is a handy selector in top-right for the number of context lines, which allows to see such changes in context.

mkoeppe · 2016-04-10T22:38:39Z

comment:28

Replying to @novoselt:

If you are looking at commits in a browser, there is a handy selector in top-right 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

novoselt · 2016-04-10T22:46:02Z

comment:29

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.

mkoeppe · 2016-04-10T22:59:18Z

comment:30

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.

novoselt · 2016-04-10T23:05:27Z

comment:31

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.

mkoeppe · 2016-04-10T23:22:33Z

comment:32

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.

mkoeppe · 2016-04-11T00:22:46Z

comment:33

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

mkoeppe · 2016-04-11T00:36:27Z

comment:34

See #20413.

mkoeppe · 2016-04-11T00:51:51Z

Changed branch from u/novoselt/ISM_enchancements to u/mkoeppe/ISM_enchancements

mkoeppe · 2016-04-11T00:52:16Z

Changed commit from 4d7afca to 78d0e78

mkoeppe · 2016-04-11T00:52:16Z

comment:36

I have added a testcase.

New commits:

`78d0e78`	`InteractiveLPProblem.standard_form: Add doctest for minimization with objective_constant_term`

novoselt · 2016-04-11T02:44:07Z

Changed branch from u/mkoeppe/ISM_enchancements to u/novoselt/ISM_enchancements

novoselt · 2016-04-11T02:46:08Z

comment:38

Yes, of course - thanks for thorough testing!

New commits:

`7145f7d`	`Flip the constant term sign when converting min problems to standard form.`

novoselt · 2016-04-11T02:46:08Z

Changed commit from 78d0e78 to 7145f7d

mkoeppe · 2016-04-11T02:55:11Z

comment:39

Thanks a lot for your work on this ticket!

vbraun · 2016-04-12T16:30:38Z

Changed branch from u/novoselt/ISM_enchancements to 7145f7d

novoselt added this to the sage-7.2 milestone Mar 27, 2016

novoselt added c: numerical labels Mar 27, 2016

novoselt added the s: needs review label Mar 27, 2016

mkoeppe added s: needs work and removed s: needs review labels Mar 28, 2016

novoselt added s: needs review and removed s: needs work labels Apr 2, 2016

mkoeppe added s: needs work and removed s: needs review labels Apr 4, 2016

novoselt added s: needs review and removed s: needs work labels Apr 10, 2016

mkoeppe added s: positive review and removed s: needs review labels Apr 11, 2016

vbraun removed the s: positive review label Apr 12, 2016

vbraun closed this as completed in abbb433 Apr 12, 2016

interactive_simplex_method enhancements #20311

interactive_simplex_method enhancements #20311

Comments

novoselt commented Mar 27, 2016

novoselt commented Mar 27, 2016

novoselt commented Mar 27, 2016

novoselt commented Mar 27, 2016

novoselt commented Mar 27, 2016

novoselt commented Mar 27, 2016

mkoeppe commented Mar 27, 2016

mkoeppe commented Mar 29, 2016

mkoeppe commented Mar 30, 2016

novoselt commented Mar 31, 2016

novoselt commented Mar 31, 2016

mkoeppe commented Mar 31, 2016

novoselt commented Apr 2, 2016

novoselt commented Apr 2, 2016

novoselt commented Apr 2, 2016

mkoeppe commented Apr 4, 2016

novoselt commented Apr 4, 2016

mkoeppe commented Apr 4, 2016

novoselt commented Apr 4, 2016

mkoeppe commented Apr 4, 2016

sagetrac-git mannequin commented Apr 10, 2016

novoselt commented Apr 10, 2016

mkoeppe commented Apr 10, 2016

mkoeppe commented Apr 10, 2016

novoselt commented Apr 10, 2016

novoselt commented Apr 10, 2016

mkoeppe commented Apr 10, 2016

novoselt commented Apr 10, 2016

mkoeppe commented Apr 10, 2016

novoselt commented Apr 10, 2016

mkoeppe commented Apr 10, 2016

novoselt commented Apr 10, 2016

mkoeppe commented Apr 10, 2016

mkoeppe commented Apr 11, 2016

mkoeppe commented Apr 11, 2016

mkoeppe commented Apr 11, 2016

mkoeppe commented Apr 11, 2016

mkoeppe commented Apr 11, 2016

novoselt commented Apr 11, 2016

novoselt commented Apr 11, 2016

novoselt commented Apr 11, 2016

mkoeppe commented Apr 11, 2016

vbraun commented Apr 12, 2016