InteractiveLPBackend: Use standard-form transformation, objective_constant_term, change default base_ring to QQ

[mkoeppe]

Follow-up on #20296, #20311, #20301. Updating InteractiveLPBackend to:

• use the standard-form transformation,
• simplify its code slightly by making use of the new objective_constant_term handling in InteractiveLPProblem
• make the example of optimizing over the dodecahedron more natural and remove use of backend methods.
• change default base_ring to QQ -- a much saner default because it's so much faster

[mkoeppe]

Branch is on top of #20311

---

Last 10 new commits:

​b5f5f91	Infeasible problems are bounded!
​5fd3547	Add checks for feasible/optimal solutions of InteractiveLPProblem
​f2e52f8	Return coordinate transformation for problems in standard form.
​ec31ed6	InteractiveLPProblem.standard_form: Add doctest for objective_constant_term
​992c5ea	Typeset constant term and clarify negativity interaction.
​580b57f	Merge 7.2.beta3 into t/20311/ISM_enchancements
​4d7afca	Fixes to the objective constant term treatment.
​07b1b62	Merge branch 't/20311/ISM_enchancements' into t/20413/interactivelpproblem__use_standard_form_transformation__objective_constant_term
​14e133a	InteractiveLPBackend: Use standard form transformation on optimal solution
​bd1424b	InteractiveLPBackend: Use InteractiveLPProblem's objective_constant_term

[git]

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

​78d0e78	InteractiveLPProblem.standard_form: Add doctest for minimization with objective_constant_term
​7145f7d	Flip the constant term sign when converting min problems to standard form.
​05af303	Merge branch 't/20311/ISM_enchancements' into t/20413/interactivelpproblem__use_standard_form_transformation__objective_constant_term

[novoselt]

Out of curiosity - how does timing of interactive backend compares with "normal solvers" on "interesting problems"?-) Presumably most of the time is spent on typesetting, but other solvers may have some setup overhead which is significant in small cases. Also you have used revised dictionaries - are there any benefits to them in this implementation? (It seemed to me that no, the first problem of ​https://sage373.math.ualberta.ca/home/pub/32/ )

[git]

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

​c071f9a

InteractiveLPBackend.objective_constant_term: New

[mkoeppe]

I have not done any benchmarking, neither with real solvers, nor between your two dictionary implementations. This could be a nice class project. I have chosen the revised dictionary because that's what one "should" do. I suppose if one does the benchmarking, one will see the expected result that the revised method is faster when the number of nonbasics is large enough.

I wrote InteractiveLPBackend because I needed a solver for some very small LPs with irrational algebraic data (unrelated to the example in the doctest!), for which there is simply no alternative solver available.

[mkoeppe]

At the moment, InteractiveLPBackend chooses AA as the default base ring, that's probably a bad idea (I'll change it). If I change it to QQ, I get the following comparison:

sage: %time delsarte_bound_additive_hamming_space(19,15,7,solver='ppl')
CPU times: user 153 ms, sys: 13.4 ms, total: 167 ms
Wall time: 163 ms
3
sage: %time delsarte_bound_additive_hamming_space(19,15,7,solver='glpk')
CPU times: user 84.9 ms, sys: 14.7 ms, total: 99.6 ms
Wall time: 109 ms
3
sage: %time delsarte_bound_additive_hamming_space(19,15,7,solver='coin')
CPU times: user 87.9 ms, sys: 16.1 ms, total: 104 ms
Wall time: 160 ms
3
sage: %time delsarte_bound_additive_hamming_space(19,15,7,solver='interactivelp')
CPU times: user 10.6 s, sys: 91.1 ms, total: 10.7 s
Wall time: 10.8 s
3

[mkoeppe]

(The change of the default base ring will be on a different ticket; because first #20415 needs to be done.) So the present ticket is ready for review.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​de898ac	InteractiveLPBackend: Use standard form transformation on optimal solution
​b8ea5a2	InteractiveLPBackend: Use InteractiveLPProblem's objective_constant_term
​d84b5bd	InteractiveLPBackend.objective_constant_term: New
​c8fa4b0	InteractiveLPBackend: Change default base_ring to QQ

[mkoeppe]

Rebased on top of 7.2.beta4, which merged #20415.

Made the change to a better (much faster) default base_ring QQ.

Needs review.

[mkoeppe]

Corrected the title/description -- this ticket is about the *MIP backend* using the interactive simplex method.

[dimpase]

looks good.