一句话：提出以凸包为中间表示求解不可行低维线性规划，生成满足最多约束的浮点解，加速正确舍入数学库多项式生成。
该论文面向 RLIBM 项目生成正确舍入数学库时出现的不可行低维线性规划：约束数可达数十亿、未知变量很少，且所有约束无法同时满足，目标是在浮点下满足尽可能多的约束。现有方法难以在如此大规模上给出浮点解。作者利用线性规划与凸包的几何对偶，提出将凸包作为中间表示，把约束集拆成可行约束集 X 和不可行约束超集 V；先通过二维凸包识别不可行约束，再在 X 中提取基约束，并构造新的线性规划来最大化 V 中可满足的约束。评估表明，该求解器显著加快相应线性规划的求解，并改善最终 RLIBM 多项式的性能。
This paper proposes a novel method to efficiently solve infeasible low-dimensional linear programs (LDLPs) with billions of constraints and a small number of unknown variables, where all the constraints cannot be satisfied simultaneously. We focus on infeasible linear programs generated in the RL ibm project for creating correctly rounded math libraries. Specifically, we are interested in generating a floating point solution that satisfies the maximum number of constraints. None of the existing methods can solve such large linear programs while producing floating point solutions. We observe that the convex hull can serve as an intermediate representation (IR) for solving infeasible LDLPs using the geometric duality between linear programs and convex hulls. Specifically, some of the constraints that correspond to points on the convex hull are precisely those constraints that make the linear program infeasible. Our key idea is to split the entire set of constraints into two subsets using the convex hull IR: (a) a set X of feasible constraints and (b) a superset V of infeasible constraints. Using the special structure of the RL ibm constraints and the presence of a method to check whether a system is feasible or not. we identify a superset of infeasible constraints by computing the convex hull in 2-dimensions. Subsequently, we identify the key constraints (i.e., basis constraints) in the set of feasible constraints X and use them to create a new linear program whose solution identifies the maximum set of constraints satisfiable in V while satisfying all the constraints in X . This new solver enabled us to improve the performance of the resulting RL ibm polynomials while solving the corresponding linear programs significantly faster.
@article{AanjaneyaN24,
title = {Maximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear Programs with Convex Hull as the Intermediate Representation},
author = {Mridul Aanjaneya and Santosh Nagarakatte},
journal = {Proceedings of the ACM on Programming Languages},
volume = {8},
number = {PLDI},
year = {2024},
doi = {10.1145/3656427}
}