Certifying and Repairing Solutions to Large LPs \\ How Good
are LP-solvers?
Marcel Dhiflaoui, Stefan Funke, Carsten Kwappik, Kurt Mehlhorn, Michael Seel, Elmar Schoemer, Ralph Schulte, Dennis Weber
State-of-the-art linear programming (LP) solvers give solutions without any
warranty. Solutions are not guaranteed to be optimal or even close to optimal.
Of course, it is generally believed that the solvers produce optimal or at
least close to optimal solutions.
We have implemented a system LPex which allows us to check this belief. More
precisely, given an LP and a basis B, it determines whether the basis is primal
feasible and/or dual feasible. It can also find the optimum starting from an
arbitrary basis (or from scratch). It uses exact
arithmetic to guarantee correctness of the results. The system is
efficient enough to be applied to medium- to large-scale LPs. We present
results from the netlib benchmark suite.
PDF