Opened 3 years ago
Closed 3 years ago
#20413 closed enhancement (fixed)
InteractiveLPBackend: Use standardform transformation, objective_constant_term, change default base_ring to QQ
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage7.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 )
Followup on #20296, #20311, #20301.
Updating InteractiveLPBackend
to:
 use the standardform transformation,
 simplify its code slightly by making use of the new
objective_constant_term
handling inInteractiveLPProblem
 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
 Branch set to u/mkoeppe/fx_with_new_interactive_simplex_objshift
comment:2 Changed 3 years ago by
 Commit set to bd1424bb2a56cabdc38d8162a9af8c66663bec58
comment:3 Changed 3 years ago by
 Commit changed from bd1424bb2a56cabdc38d8162a9af8c66663bec58 to 05af303f24dcd7899de4639666293adde8defdb8
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

comment:4 Changed 3 years ago by
 Status changed from new to needs_review
comment:5 Changed 3 years ago by
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
 Commit changed from 05af303f24dcd7899de4639666293adde8defdb8 to c071f9a2a60f375c6b0fc731d73e5bcb89d5ea93
Branch pushed to git repo; I updated commit sha1. New commits:
c071f9a  InteractiveLPBackend.objective_constant_term: New

comment:7 Changed 3 years ago by
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
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
(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
 Commit changed from c071f9a2a60f375c6b0fc731d73e5bcb89d5ea93 to c8fa4b0a9a706f79786f8ee94e0c955e3cabae51
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

comment:11 Changed 3 years ago by
 Description modified (diff)
 Summary changed from InteractiveLPProblem: Use standardform transformation, objective_constant_term to InteractiveLPProblem: Use standardform 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
 Description modified (diff)
 Summary changed from InteractiveLPProblem: Use standardform transformation, objective_constant_term, change default base_ring to QQ to InteractiveLPBackend: Use standardform transformation, objective_constant_term, change default base_ring to QQ
comment:13 Changed 3 years ago by
Corrected the title/description  this ticket is about the *MIP backend* using the interactive simplex method.
comment:14 Changed 3 years ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
looks good.
comment:15 Changed 3 years ago by
 Branch changed from u/mkoeppe/fx_with_new_interactive_simplex_objshift to c8fa4b0a9a706f79786f8ee94e0c955e3cabae51
 Resolution set to fixed
 Status changed from positive_review to closed
Branch is on top of #20311
Last 10 new commits:
Infeasible problems are bounded!
Add checks for feasible/optimal solutions of InteractiveLPProblem
Return coordinate transformation for problems in standard form.
InteractiveLPProblem.standard_form: Add doctest for objective_constant_term
Typeset constant term and clarify negativity interaction.
Merge 7.2.beta3 into t/20311/ISM_enchancements
Fixes to the objective constant term treatment.
Merge branch 't/20311/ISM_enchancements' into t/20413/interactivelpproblem__use_standard_form_transformation__objective_constant_term
InteractiveLPBackend: Use standard form transformation on optimal solution
InteractiveLPBackend: Use InteractiveLPProblem's objective_constant_term