Opened 6 years ago
Last modified 3 months ago
#18735 needs_review enhancement
MixedIntegerLinearProgram: Reconstruct exact rational basic solution — at Version 4
Reported by: | mkoeppe | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.5 |
Component: | numerical | Keywords: | lp |
Cc: | yzh, ncohen, dimpase | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #18685, #18688 | Stopgaps: |
Description (last modified by )
Sometimes one can use a fast numerical LP solver to solve a problem to "optimality",
then reconstruct the primal and dual solution in rational arithmetic (or over whatever base_ring was used...) and in this way prove that this basis is indeed optimal.
MixedIntegerLinearProgram
should support this mode of operation.
This would be particularly interesting in conjunction with #18764. (But see #18765 for a different approach.)
#18685 provides the necessary basis-status functions (for the GLPK backend). #18688 provides a solver-independent interface to these functions.
Change History (4)
comment:1 Changed 6 years ago by
- Cc dimpase added
comment:2 Changed 6 years ago by
comment:3 Changed 6 years ago by
- Description modified (diff)
On the other hand, a solver-independent way to get an optimal dual solution is very much welcome, as this is lacking currently, and often needed.
comment:4 Changed 6 years ago by
- Description modified (diff)
Is
ppl
(ppl
LP backend, which works with exact arithmetic) too slow for you?