ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 23 Sep 2019 14:36:29 +0200Linear Programming: float solving and exact verificationhttps://ask.sagemath.org/question/48034/linear-programming-float-solving-and-exact-verification/Hi there,
the glpsol tool (GLPK) provides an option "--xcheck": the solver compute the optimal solution uses floating points, and then checks the correctness using exact arithmetics (i guess implicitly they re-check the basis variables, so this only requires one matrix inversation on exact arithmetics)
1. the MILP interface of sage provides the possibility to set, however, it appears that there is no option to activate "xcheck"?
[not allowed to post links but here are the references for the sage documentation] doc.sagemath.org/html/en/reference/numerical/sage/numerical/mip.html#sage.numerical.mip.MixedIntegerLinearProgram.solver_parameter
doc.sagemath.org/html/en/reference/numerical/sage/numerical/backends/glpk_backend.html#sage.numerical.backends.glpk_backend.GLPKBackend.solver_parameter
2. I know that it is easy to extract the basis variables and to recheck the correctness of a floating-point-solution just within sage, however, I really think **this should be added as a basic functionality** for the SAGE MILP interface to ANY solver, not only GLPK (so this verification-code should also verify solutions of cplex,gurobi,etc.) .
So, does anyone have already an implementation for such a verification?
Best,
ManfredSun, 22 Sep 2019 23:33:46 +0200https://ask.sagemath.org/question/48034/linear-programming-float-solving-and-exact-verification/Answer by Emmanuel Charpentier for <p>Hi there,</p>
<p>the glpsol tool (GLPK) provides an option "--xcheck": the solver compute the optimal solution uses floating points, and then checks the correctness using exact arithmetics (i guess implicitly they re-check the basis variables, so this only requires one matrix inversation on exact arithmetics)</p>
<ol>
<li><p>the MILP interface of sage provides the possibility to set, however, it appears that there is no option to activate "xcheck"?
[not allowed to post links but here are the references for the sage documentation] doc.sagemath.org/html/en/reference/numerical/sage/numerical/mip.html#sage.numerical.mip.MixedIntegerLinearProgram.solver_parameter
doc.sagemath.org/html/en/reference/numerical/sage/numerical/backends/glpk_backend.html#sage.numerical.backends.glpk_backend.GLPKBackend.solver_parameter </p></li>
<li><p>I know that it is easy to extract the basis variables and to recheck the correctness of a floating-point-solution just within sage, however, I really think <strong>this should be added as a basic functionality</strong> for the SAGE MILP interface to ANY solver, not only GLPK (so this verification-code should also verify solutions of cplex,gurobi,etc.) . </p></li>
</ol>
<p>So, does anyone have already an implementation for such a verification?</p>
<p>Best,
Manfred</p>
https://ask.sagemath.org/question/48034/linear-programming-float-solving-and-exact-verification/?answer=48038#post-id-48038This is not really a question but a suggestion, which should have been addressed to the [sage-devel mailing list](https://groups.google.com/forum/#!forum/sage-devel).
It should be noted that not all linear programming problems can be addressed by this tactic...Mon, 23 Sep 2019 14:36:29 +0200https://ask.sagemath.org/question/48034/linear-programming-float-solving-and-exact-verification/?answer=48038#post-id-48038