Combining Incremental Precision Boosting and Iterative Refinement for Exact Linear Programming
Jules Nicolas-Thouvenin  1, 2@  
1 : Zuse Institute Berlin
2 : Nantes université - UFR des Sciences et des Techniques
Nantes Université - pôle Sciences et technologie

Two methods exist for solving large-scale linear programs exactly, i.e. without roundoff-errors or numerical tolerances: precision boosting and iterative refinement. The former, implemented in the exact LP solver QSopt_ex, dynamically increases the precision of the underlying floating-point solve. The latter, implemented in the LP solver SoPlex, iteratively scales the LP around increasingly accurate solutions. Although the iterative refinement method of SoPlex is faster than the precision boosting method of QSopt_ex on a majority of instances, it fails on several numerically challenging LPs. In order to increase the number of numerically challenging instances that SoPlex can solve exactly, we combine the iterative refinement method with a precision boosting framework. With this method, we succeed in solving 45% more LPs in a test set of 269 numerically challenging instances, without any loss in performance on numerically easy instances.


Personnes connectées : 31 Vie privée
Chargement...