Opened 3 years ago

Closed 3 years ago

#20413 closed enhancement (fixed)

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

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-7.2
Component: numerical Keywords: lp
Cc: novoselt, dimpase, vdelecroix Merged in:
Authors: Matthias Koeppe Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: c8fa4b0 (Commits) Commit: c8fa4b0a9a706f79786f8ee94e0c955e3cabae51
Dependencies: #20296, #20311, #20301 Stopgaps:

Description (last modified by 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

Change History (15)

comment:1 Changed 3 years ago by mkoeppe

  • Branch set to u/mkoeppe/fx_with_new_interactive_simplex_objshift

comment:2 Changed 3 years ago by mkoeppe

  • Commit set to bd1424bb2a56cabdc38d8162a9af8c66663bec58

Branch is on top of #20311


Last 10 new commits:

b5f5f91Infeasible problems are bounded!
5fd3547Add checks for feasible/optimal solutions of InteractiveLPProblem
f2e52f8Return coordinate transformation for problems in standard form.
ec31ed6InteractiveLPProblem.standard_form: Add doctest for objective_constant_term
992c5eaTypeset constant term and clarify negativity interaction.
580b57fMerge 7.2.beta3 into t/20311/ISM_enchancements
4d7afcaFixes to the objective constant term treatment.
07b1b62Merge branch 't/20311/ISM_enchancements' into t/20413/interactivelpproblem__use_standard_form_transformation__objective_constant_term
14e133aInteractiveLPBackend: Use standard form transformation on optimal solution
bd1424bInteractiveLPBackend: Use InteractiveLPProblem's objective_constant_term

comment:3 Changed 3 years ago by git

  • Commit changed from bd1424bb2a56cabdc38d8162a9af8c66663bec58 to 05af303f24dcd7899de4639666293adde8defdb8

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

78d0e78InteractiveLPProblem.standard_form: Add doctest for minimization with objective_constant_term
7145f7dFlip the constant term sign when converting min problems to standard form.
05af303Merge branch 't/20311/ISM_enchancements' into t/20413/interactivelpproblem__use_standard_form_transformation__objective_constant_term

comment:4 Changed 3 years ago by mkoeppe

  • Status changed from new to needs_review

comment:5 Changed 3 years ago by 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/ )

comment:6 Changed 3 years ago by git

  • Commit changed from 05af303f24dcd7899de4639666293adde8defdb8 to c071f9a2a60f375c6b0fc731d73e5bcb89d5ea93

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

c071f9aInteractiveLPBackend.objective_constant_term: New

comment:7 Changed 3 years ago by 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.

comment:8 Changed 3 years ago by 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

comment:9 Changed 3 years ago by 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.

comment:10 Changed 3 years ago by git

  • Commit changed from c071f9a2a60f375c6b0fc731d73e5bcb89d5ea93 to c8fa4b0a9a706f79786f8ee94e0c955e3cabae51

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

de898acInteractiveLPBackend: Use standard form transformation on optimal solution
b8ea5a2InteractiveLPBackend: Use InteractiveLPProblem's objective_constant_term
d84b5bdInteractiveLPBackend.objective_constant_term: New
c8fa4b0InteractiveLPBackend: Change default base_ring to QQ

comment:11 Changed 3 years ago by mkoeppe

  • Description modified (diff)
  • Summary changed from InteractiveLPProblem: Use standard-form transformation, objective_constant_term to InteractiveLPProblem: Use standard-form transformation, objective_constant_term, change default base_ring to QQ

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

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

Needs review.

comment:12 Changed 3 years ago by mkoeppe

  • Description modified (diff)
  • Summary changed from InteractiveLPProblem: Use standard-form transformation, objective_constant_term, change default base_ring to QQ to InteractiveLPBackend: Use standard-form transformation, objective_constant_term, change default base_ring to QQ

comment:13 Changed 3 years ago by mkoeppe

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

comment:14 Changed 3 years ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from needs_review to positive_review

looks good.

comment:15 Changed 3 years ago by vbraun

  • Branch changed from u/mkoeppe/fx_with_new_interactive_simplex_objshift to c8fa4b0a9a706f79786f8ee94e0c955e3cabae51
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.