Ask Your Question
1

Linear Programming: float solving and exact verification

asked 2019-09-22 16:33:46 -0600

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, Manfred

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
0

answered 2019-09-23 07:36:29 -0600

Emmanuel Charpentier gravatar image

This is not really a question but a suggestion, which should have been addressed to the sage-devel mailing list.

It should be noted that not all linear programming problems can be addressed by this tactic...

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2019-09-22 16:33:46 -0600

Seen: 80 times

Last updated: Sep 23 '19