Row-Polar LP-Newton for Linear Programming with Corral Repair

DOI10.48550/arXiv.2609.13755MaRDI QIDQ7345505arXivFDO

Authors Jianming Shi, Yanfei Li, Yuki Matsuno

Publication date 12 September 2026

Published in arXiv

Tldr We present a row-polar linear programming solver with corral repair that improves performance over our prior polar LP-Newton for dense and large-scale problems in exact arithmetic. Repair preserves P-LPN's projections and LP conclusions while reducing the number of outer iterations in a quadratic bound, often by reusing the terminal corral from the previous iteration.

Full work available at URL https://doi.org/10.48550/arXiv.2609.13755

arXiv classification

cs.MSmath.NAmath.OC

Cites work

• A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES
• A DUAL ALGORITHM FOR FINDING THE MINIMUM-NORM POINT IN A POLYTOPE
• A simple projection algorithm for linear programming problems
• An algorithm for finding the minimum-norm point in the intersection of a convex polyhedron and a hyperplane
• An update-and-stabilize framework for the minimum-norm-point problem
• Combining precision boosting with LP iterative refinement for exact linear optimization
• Extension of the LP-Newton method to conic programming problems via semi-infinite representation
• Finding the nearest point in A polytope
• Iterative refinement for linear programming
• Parallelizing the dual revised simplex method
• Projective Cutting-Planes for Robust Linear Programming and Cutting Stock Problems
• The LP-Newton method for standard form linear programming problems
• The minimum Euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential
• Zonotopes and the LP-Newton method

This page was built for publication: Row-Polar LP-Newton for Linear Programming with Corral Repair

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7345505)