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

Depends on #20296
Depends on #20311
Depends on #20301

CC: @novoselt @dimpase @videlec

Component: numerical

Author: Matthias Koeppe

Branch/Commit: c8fa4b0

Reviewer: Dima Pasechnik

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

[mkoeppe]

Branch: u/mkoeppe/fx_with_new_interactive_simplex_objshift

[mkoeppe]

comment:2

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

[mkoeppe]

Commit: bd1424b

[sagetrac-git]

Changed commit from bd1424b to 05af303

[sagetrac-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]

comment:5

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

[sagetrac-git]

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

c071f9a

InteractiveLPBackend.objective_constant_term: New

[sagetrac-git]

Changed commit from 05af303 to c071f9a

[mkoeppe]

comment:7

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]

comment:8

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]

comment:9

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

[sagetrac-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

[sagetrac-git]

Changed commit from c071f9a to c8fa4b0

[mkoeppe]

comment:11

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]

comment:13

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

[dimpase]

comment:14

looks good.

[dimpase]

Reviewer: Dima Pasechnik

[vbraun]

Changed branch from u/mkoeppe/fx_with_new_interactive_simplex_objshift to c8fa4b0