SHF: Small: Efficient, Deterministic and Formally Certified Methods for Solving Low-dimensional Linear Programs with Floating-point Precision

SHF:小型:用于以浮点精度求解低维线性程序的高效、确定性且经过正式认证的方法

基本信息

  • 批准号:
    2312220
  • 负责人:
  • 金额:
    $ 54万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2023
  • 资助国家:
    美国
  • 起止时间:
    2023-07-01 至 2026-06-30
  • 项目状态:
    未结题

项目摘要

Linear programs (LPs) are widely used in numerous domains, such as computer arithmetic, robotics, machine learning, computer vision and databases. Existing LP solvers, which have been steadily improved after decades of research, can solve several tens of thousands of constraints. These solvers focus on linear programs where the number of constraints is of the same order of magnitude as the number of variables (i.e., high-dimensional linear programs). However, in many domains, linear programs with billions of constraints but a small number of variables are common. Such linear programs are called "low-dimensional linear programs" (LDLPs). Unfortunately, existing LP solvers cannot solve them. This project aims to develop efficient and deterministic methods to solve low-dimensional linear programs that can be formally verified to produce the correct solution with floating-point precision. In contrast to existing solvers for LP problems that generate real coefficients using rational arithmetic, this project's novelty lies in generating solutions with floating-point (FP) precision using ideas from computational geometry. The project's impacts are in designing scalable LDLP solvers that can handle both linear programs that are full-rank (i.e., there exists a single solution that satisfies all constraints) and those that are not full-rank, with potentially billions of constraints. In the latter case, this project will generate a solution that satisfies the maximum number of constraints. This project will rigorously evaluate the efficacy of the LDLP solver in various domains and has the potential of expanding the use of formal methods to a wider class of applications. It will also educate practitioners, graduate and undergraduate students on foundational abstractions in computing.This project makes the following foundational advances in designing LDLP solvers: (a) It will develop an algorithm to solve LDLPs that are full rank while also identifying the key constraints. A solution that satisfies these key constraints also satisfies all the other constraints. (b) It will develop a novel method for identifying the key constraints by constructing the convex hull in high dimensions using the geometric duality between hyperplanes and points. (c) It will develop a new LP formulation using the key constraints whose solution satisfies the maximum number of constraints in the original non-full-rank LDLP. (d) It will develop an approach to formally verify the construction of the convex hull in high dimensions, especially to handle the degenerate cases that may arise in the presence of numerical and rounding errors, and (e) it will evaluate the LDLP solver in two practical applications: (1) generating correctly rounded math libraries for elementary functions, and (2) fast training of support vector machines for machine learning.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
线性规划(LP)被广泛应用于许多领域,如计算机算术,机器人,机器学习,计算机视觉和数据库。经过几十年的研究,现有的LP求解器已经得到了稳步的改进,可以解决数万个约束。这些求解器集中于约束数量与变量数量具有相同数量级的线性规划(即,高维线性规划)。然而,在许多领域中,具有数十亿个约束但变量数量很少的线性规划是常见的。这种线性规划被称为“低维线性规划”(LDLP)。不幸的是,现有的LP求解器无法解决这些问题。 该项目旨在开发高效和确定性的方法来解决低维线性规划,可以正式验证以产生具有浮点精度的正确解决方案。与现有的使用有理运算生成真实的系数的LP问题求解器相比,该项目的新奇在于使用计算几何的思想生成具有浮点(FP)精度的解决方案。 该项目的影响是设计可扩展的LDLP求解器,可以处理满秩的线性规划(即,存在满足所有约束的单个解决方案)和具有潜在数十亿约束的非满秩解决方案。在后一种情况下,该项目将生成满足最大数量约束的解决方案。该项目将严格评估LDLP求解器在各个领域的有效性,并有可能将形式方法的使用扩展到更广泛的应用领域。该项目在设计LDLP求解器方面取得了以下基本进展:(a)它将开发一种算法来求解满秩的LDLP,同时还将识别关键约束。满足这些关键约束的解决方案也满足所有其他约束。(b)利用超平面与点的几何对偶性,通过构造高维凸船体,提出了一种识别关键约束的新方法。(c)它将开发一个新的LP制定使用的关键约束,其解决方案满足最大数量的约束,在原来的非满秩LDLP。(d)它将开发一种方法来正式验证高维凸船体的构造,特别是处理在存在数值和舍入误差的情况下可能出现的退化情况,以及(e)它将在两个实际应用中评估LDLP求解器:(1)为初等函数生成正确舍入的数学库,以及(2)机器学习支持向量机的快速训练。该奖项反映了NSF的法定使命,并通过使用基金会的知识价值和更广泛的影响审查标准进行评估,被认为值得支持。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Mridul Aanjaneya其他文献

An Efficient Solver for Two‐way Coupling Rigid Bodies with Incompressible Flow
  • DOI:
    10.1111/cgf.13512
  • 发表时间:
    2018-09
  • 期刊:
  • 影响因子:
    2.5
  • 作者:
    Mridul Aanjaneya
  • 通讯作者:
    Mridul Aanjaneya
A Recurrent Differentiable Physics Engine for Tensegrity Robots
张拉整体机器人的循环可微物理引擎
  • DOI:
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Kun Wang;Mridul Aanjaneya;Kostas E. Bekris
  • 通讯作者:
    Kostas E. Bekris
Diffuse reflection diameter and radius for convex-quadrilateralizable polygons
  • DOI:
    10.1016/j.dam.2012.12.020
  • 发表时间:
    2013-07-01
  • 期刊:
  • 影响因子:
  • 作者:
    Arindam Khan;Sudebkumar P. Pal;Mridul Aanjaneya;Arijit Bishnu;Subhas C. Nandy
  • 通讯作者:
    Subhas C. Nandy
Triangulating the Real Projective Plane
对实投影平面进行三角测量
  • DOI:
  • 发表时间:
    2007
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Mridul Aanjaneya;M. Teillaud
  • 通讯作者:
    M. Teillaud
Maximum Consensus Floating Point Solutions for Infeasible Low-Dimensional Linear Programs with Convex Hull as the Intermediate Representation
以凸包为中间表示的不可行低维线性规划的最大一致浮点解
  • DOI:
  • 发表时间:
    2024
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Mridul Aanjaneya;Santosh Nagarakatte
  • 通讯作者:
    Santosh Nagarakatte

Mridul Aanjaneya的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Mridul Aanjaneya', 18)}}的其他基金

CAREER: Modeling and Simulating Generalized Diffusion for Computer Graphics and Computational Science
职业:计算机图形学和计算科学的广义扩散建模和仿真
  • 批准号:
    2238955
  • 财政年份:
    2023
  • 资助金额:
    $ 54万
  • 项目类别:
    Continuing Grant

相似国自然基金

昼夜节律性small RNA在血斑形成时间推断中的法医学应用研究
  • 批准号:
  • 批准年份:
    2024
  • 资助金额:
    0.0 万元
  • 项目类别:
    省市级项目
tRNA-derived small RNA上调YBX1/CCL5通路参与硼替佐米诱导慢性疼痛的机制研究
  • 批准号:
    n/a
  • 批准年份:
    2022
  • 资助金额:
    10.0 万元
  • 项目类别:
    省市级项目
Small RNA调控I-F型CRISPR-Cas适应性免疫性的应答及分子机制
  • 批准号:
    32000033
  • 批准年份:
    2020
  • 资助金额:
    24.0 万元
  • 项目类别:
    青年科学基金项目
Small RNAs调控解淀粉芽胞杆菌FZB42生防功能的机制研究
  • 批准号:
    31972324
  • 批准年份:
    2019
  • 资助金额:
    58.0 万元
  • 项目类别:
    面上项目
变异链球菌small RNAs连接LuxS密度感应与生物膜形成的机制研究
  • 批准号:
    81900988
  • 批准年份:
    2019
  • 资助金额:
    21.0 万元
  • 项目类别:
    青年科学基金项目
肠道细菌关键small RNAs在克罗恩病发生发展中的功能和作用机制
  • 批准号:
    31870821
  • 批准年份:
    2018
  • 资助金额:
    56.0 万元
  • 项目类别:
    面上项目
基于small RNA 测序技术解析鸽分泌鸽乳的分子机制
  • 批准号:
    31802058
  • 批准年份:
    2018
  • 资助金额:
    26.0 万元
  • 项目类别:
    青年科学基金项目
Small RNA介导的DNA甲基化调控的水稻草矮病毒致病机制
  • 批准号:
    31772128
  • 批准年份:
    2017
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
基于small RNA-seq的针灸治疗桥本甲状腺炎的免疫调控机制研究
  • 批准号:
    81704176
  • 批准年份:
    2017
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
水稻OsSGS3与OsHEN1调控small RNAs合成及其对抗病性的调节
  • 批准号:
    91640114
  • 批准年份:
    2016
  • 资助金额:
    85.0 万元
  • 项目类别:
    重大研究计划

相似海外基金

Collaborative Research: SHF: Small: Efficient and Scalable Privacy-Preserving Neural Network Inference based on Ciphertext-Ciphertext Fully Homomorphic Encryption
合作研究:SHF:小型:基于密文-密文全同态加密的高效、可扩展的隐私保护神经网络推理
  • 批准号:
    2412357
  • 财政年份:
    2024
  • 资助金额:
    $ 54万
  • 项目类别:
    Standard Grant
Collaborative Research: SHF: Small: Quasi Weightless Neural Networks for Energy-Efficient Machine Learning on the Edge
合作研究:SHF:小型:用于边缘节能机器学习的准失重神经网络
  • 批准号:
    2326895
  • 财政年份:
    2023
  • 资助金额:
    $ 54万
  • 项目类别:
    Standard Grant
Collaborative Research: SHF: Small: Enabling Efficient 3D Perception: An Architecture-Algorithm Co-Design Approach
协作研究:SHF:小型:实现高效的 3D 感知:架构-算法协同设计方法
  • 批准号:
    2334624
  • 财政年份:
    2023
  • 资助金额:
    $ 54万
  • 项目类别:
    Standard Grant
SHF: Core: Small: Real-time and Energy-Efficient Machine Learning for Robotics Applications
SHF:核心:小型:用于机器人应用的实时且节能的机器学习
  • 批准号:
    2341183
  • 财政年份:
    2023
  • 资助金额:
    $ 54万
  • 项目类别:
    Standard Grant
Collaborative Research: SHF: Small: Quasi Weightless Neural Networks for Energy-Efficient Machine Learning on the Edge
合作研究:SHF:小型:用于边缘节能机器学习的准失重神经网络
  • 批准号:
    2326894
  • 财政年份:
    2023
  • 资助金额:
    $ 54万
  • 项目类别:
    Standard Grant
Collaborative Research: SHF: Small: Efficient and Scalable Privacy-Preserving Neural Network Inference based on Ciphertext-Ciphertext Fully Homomorphic Encryption
合作研究:SHF:小型:基于密文-密文全同态加密的高效、可扩展的隐私保护神经网络推理
  • 批准号:
    2243053
  • 财政年份:
    2023
  • 资助金额:
    $ 54万
  • 项目类别:
    Standard Grant
Collaborative Research: SHF: Small: Efficient and Scalable Privacy-Preserving Neural Network Inference based on Ciphertext-Ciphertext Fully Homomorphic Encryption
合作研究:SHF:小型:基于密文-密文全同态加密的高效、可扩展的隐私保护神经网络推理
  • 批准号:
    2243052
  • 财政年份:
    2023
  • 资助金额:
    $ 54万
  • 项目类别:
    Standard Grant
SHF: Small: Rethinking Virtualization at the Edge to Support Highly-efficient and Low-power Applications
SHF:小型:重新思考边缘虚拟化以支持高效和低功耗应用
  • 批准号:
    2210744
  • 财政年份:
    2022
  • 资助金额:
    $ 54万
  • 项目类别:
    Standard Grant
CCF: SHF: Small: Self-Adaptive Interference-Avoiding Wireless Receiver Hardware through Real-Time Learning-Based Automatic Optimization of Power-Efficient Integrated Circuits
CCF:SHF:小型:通过基于实时学习的高能效集成电路自动优化实现自适应干扰避免无线接收器硬件
  • 批准号:
    2218845
  • 财政年份:
    2022
  • 资助金额:
    $ 54万
  • 项目类别:
    Standard Grant
SHF: Small: Energy and Computational Efficient Deep Generative AI Models via Emerging Devices, Circuits, and Architectures
SHF:小型:通过新兴设备、电路和架构实现能源和计算高效的深度生成人工智能模型
  • 批准号:
    2219753
  • 财政年份:
    2022
  • 资助金额:
    $ 54万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了