interactive_simplex_method enhancements

[novoselt]

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

[novoselt]

Branch: u/novoselt/ISM_enchancements

[novoselt]

Changed branch from u/novoselt/ISM_enchancements to none

[novoselt]

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]

Commit: f2e52f8

[novoselt]

Branch: u/novoselt/ISM_enchancements

[mkoeppe]

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]

Reviewer: Matthias Koeppe

[mkoeppe]

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

[novoselt]

Changed commit from f2e52f8 to ec31ed6

[novoselt]

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