Opened 5 years ago
Closed 5 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, GitHub, GitLab) | Commit: | c8fa4b0a9a706f79786f8ee94e0c955e3cabae51 |
Dependencies: | #20296, #20311, #20301 | Stopgaps: |
Description (last modified by )
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 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 5 years ago by
- Branch set to u/mkoeppe/fx_with_new_interactive_simplex_objshift
comment:2 Changed 5 years ago by
- Commit set to bd1424bb2a56cabdc38d8162a9af8c66663bec58
comment:3 Changed 5 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 5 years ago by
- Status changed from new to needs_review
comment:5 Changed 5 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 5 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 5 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 5 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 5 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 5 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 5 years ago by
- 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 5 years ago by
- 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 5 years ago by
Corrected the title/description -- this ticket is about the *MIP backend* using the interactive simplex method.
comment:14 Changed 5 years ago by
- Reviewers set to Dima Pasechnik
- Status changed from needs_review to positive_review
looks good.
comment:15 Changed 5 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