Opened 4 years ago

Closed 4 years ago

#20311 closed enhancement (fixed)

interactive_simplex_method enhancements

Reported by: novoselt Owned by:
Priority: major Milestone: sage-7.2
Component: numerical Keywords: lp
Cc: mkoeppe Merged in:
Authors: Andrey Novoseltsev Reviewers: Matthias Koeppe
Report Upstream: N/A Work issues:
Branch: 7145f7d (Commits) 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 4 years ago by novoselt

  • Branch set to u/novoselt/ISM_enchancements

comment:2 Changed 4 years ago by novoselt

  • Branch u/novoselt/ISM_enchancements deleted
  • Cc mkoeppe added
  • Status changed from new to needs_review

comment:3 Changed 4 years ago by novoselt

  • Branch set to u/novoselt/ISM_enchancements
  • Commit set to f2e52f8f613d423f83ee9806b23b3aacefae2156

New commits:

62ddb03Pass arguments through InteractiveLPProblem.standard_form.
5777ef9Allow objective constant terms for InteractiveLPProblem.
b5f5f91Infeasible problems are bounded!
5fd3547Add checks for feasible/optimal solutions of InteractiveLPProblem
f2e52f8Return coordinate transformation for problems in standard form.

comment:4 Changed 4 years ago by mkoeppe

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.
Last edited 4 years ago by mkoeppe (previous) (diff)

comment:5 Changed 4 years ago by mkoeppe

  • Status changed from needs_review to needs_work

comment:6 Changed 4 years ago by mkoeppe

  • Reviewers set to Matthias Koeppe

comment:7 Changed 4 years ago by mkoeppe

  • Branch changed from u/novoselt/ISM_enchancements to u/mkoeppe/ISM_enchancements

comment:8 Changed 4 years ago by novoselt

  • 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:

ec31ed6InteractiveLPProblem.standard_form: Add doctest for objective_constant_term

comment:9 Changed 4 years ago by mkoeppe

Thanks! Sounds good.

comment:10 Changed 4 years ago by novoselt

  • Branch changed from u/mkoeppe/ISM_enchancements to u/novoselt/ISM_enchancements

comment:11 Changed 4 years ago by novoselt

  • Commit changed from ec31ed65e3624affa79298d2bb8d414600b85e47 to 992c5ea1d2bcab0898dac5751a850d5ec7c053f9
  • Status changed from needs_work to needs_review

New commits:

992c5eaTypeset constant term and clarify negativity interaction.

comment:12 Changed 4 years ago by mkoeppe

  • 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 follow-up: Changed 4 years ago by novoselt

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 4 years ago by mkoeppe

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.

comment:15 Changed 4 years ago by novoselt

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 4 years ago by mkoeppe

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.

comment:17 follow-up: Changed 4 years ago by novoselt

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 4 years ago by mkoeppe

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

  • Commit changed from 992c5ea1d2bcab0898dac5751a850d5ec7c053f9 to 580b57f5af4ec143c031eae2926cb8b83333b13f

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

580b57fMerge 7.2.beta3 into t/20311/ISM_enchancements

comment:20 Changed 4 years ago by git

  • Commit changed from 580b57f5af4ec143c031eae2926cb8b83333b13f to 4d7afcab44af70dfa5063624d02c1b8ddd2b2b64

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

4d7afcaFixes to the objective constant term treatment.

comment:21 Changed 4 years ago by novoselt

  • 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 follow-up: Changed 4 years ago by 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.

Last edited 4 years ago by mkoeppe (previous) (diff)

comment:23 Changed 4 years ago by mkoeppe

@@ -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 4 years ago by novoselt

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

comment:25 Changed 4 years ago by novoselt

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

comment:26 Changed 4 years ago by mkoeppe

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

Last edited 4 years ago by mkoeppe (previous) (diff)

comment:27 follow-up: Changed 4 years ago by 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.

comment:28 in reply to: ↑ 27 Changed 4 years ago by mkoeppe

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

comment:29 Changed 4 years ago by novoselt

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 4 years ago by mkoeppe

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 follow-up: Changed 4 years ago by novoselt

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 4 years ago by mkoeppe

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 4 years ago by mkoeppe

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 4 years ago by mkoeppe

See #20413.

comment:35 Changed 4 years ago by mkoeppe

  • Branch changed from u/novoselt/ISM_enchancements to u/mkoeppe/ISM_enchancements

comment:36 Changed 4 years ago by mkoeppe

  • Commit changed from 4d7afcab44af70dfa5063624d02c1b8ddd2b2b64 to 78d0e784dfd4bb497c1b179f8fa8f645d334fdaa

I have added a testcase.


New commits:

78d0e78InteractiveLPProblem.standard_form: Add doctest for minimization with objective_constant_term

comment:37 Changed 4 years ago by novoselt

  • Branch changed from u/mkoeppe/ISM_enchancements to u/novoselt/ISM_enchancements

comment:38 Changed 4 years ago by novoselt

  • Commit changed from 78d0e784dfd4bb497c1b179f8fa8f645d334fdaa to 7145f7d14ada975e9025efddb5852af6fa79eed8

Yes, of course - thanks for thorough testing!


New commits:

7145f7dFlip the constant term sign when converting min problems to standard form.

comment:39 Changed 4 years ago by mkoeppe

  • Keywords lp added
  • Status changed from needs_review to positive_review

Thanks a lot for your work on this ticket!

comment:40 Changed 4 years ago by vbraun

  • Branch changed from u/novoselt/ISM_enchancements to 7145f7d14ada975e9025efddb5852af6fa79eed8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.