Limits of Linear Programming

线性规划的局限性

基本信息

  • 批准号:
    1300144
  • 负责人:
  • 金额:
    $ 20万
  • 依托单位:
  • 依托单位国家:
    美国
  • 项目类别:
    Standard Grant
  • 财政年份:
    2013
  • 资助国家:
    美国
  • 起止时间:
    2013-04-15 至 2016-03-31
  • 项目状态:
    已结题

项目摘要

The research objective of this award is to tremendously enhance our understanding of the fundamental limits of linear programs. This includes the improvement of known lower bounding techniques for the size of extended formulations, research of problem specific, alternative lower bounding techniques as well as the investigation of the limits of approximating combinatorial and nonlinear problems by LPs. Extended formulations are an important tool in (mixed-integer) linear programming for obtaining small descriptions for the feasible region of linear optimization problems. In many cases, the use of extended formulations can lead to an exponential saving in terms of the number of inequalities. In the context of lower bounding techniques where communication complexity methods are of high relevance alternative methods that rely more on the actual nature of polytopes will be explored. For approximate extended formulations a generalization of known methods will be required to capture the trade-off between combinatorial exactness and geometric approximation. The main objects of study will be the matching polytope and the max-cut polytope (and variants of those), both of which play a crucial role in terms of complexity. If successful, the insights gained from this project will lead to a significantly improved understanding of the ultimate limits of linear programming. It will also provide a new set of tools to analyze and lower bound the extension complexity of families of polytopes while not solely relying on combinatorial invariants. The primary goal of this work is to identify conditions under which linear programs fail to provide sufficiently fine formulations. Identifying these conditions will help in the design and construction of new optimization paradigm that might be able to keep crucial properties of linear programs (which made them so succesful) while still surpassing the inherent limitations.
该奖项的研究目标是极大地增强我们对线性程序基本限制的理解。这包括改进扩展公式大小的已知下界技术、研究特定问题、替代下界技术以及对线性规划逼近组合和非线性问题的极限的研究。扩展公式是(混合整数)线性规划中的重要工具,用于获取线性优化问题的可行区域的小描述。在许多情况下,使用扩展公式可以导致不等式数量呈指数级节省。在通信复杂性方法具有高度相关性的下界技术的背景下,将探索更多依赖于多胞体实际性质的替代方法。对于近似扩展公式,需要对已知方法进行概括,以捕获组合精确性和几何近似之间的权衡。研究的主要对象将是匹配多胞体和最大切割多胞体(及其变体),两者在复杂性方面都起着至关重要的作用。如果成功,从该项目中获得的见解将显着提高对线性规划最终极限的理解。它还将提供一套新的工具来分析和降低多胞体族的扩展复杂性,而不仅仅是依赖组合不变量。这项工作的主要目标是确定线性程序无法提供足够精细的公式的条件。识别这些条件将有助于设计和构建新的优化范式,该范式可能能够保留线性程序的关键属性(这使得它们如此成功),同时仍然超越固有的限制。

项目成果

期刊论文数量(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 }}

Sebastian Pokutta其他文献

Sebastian Pokutta的其他文献

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

{{ truncateString('Sebastian Pokutta', 18)}}的其他基金

EAGER: SC2: PHY-Layer-Integrated Collaborative Learning in Spectrum Coordination
EAGER:SC2:频谱协调中的 PHY 层集成协作学习
  • 批准号:
    1737842
  • 财政年份:
    2017
  • 资助金额:
    $ 20万
  • 项目类别:
    Standard Grant
CAREER: Semidefinite Programming (SDP) Extended Formulations
职业:半定规划 (SDP) 扩展公式
  • 批准号:
    1452463
  • 财政年份:
    2015
  • 资助金额:
    $ 20万
  • 项目类别:
    Continuing Grant
Collaborative Research: Almost Symmetric Integer Programs
合作研究:几乎对称整数规划
  • 批准号:
    1333789
  • 财政年份:
    2013
  • 资助金额:
    $ 20万
  • 项目类别:
    Standard Grant

相似国自然基金

非线性的可编程超表面衍射神经网络
  • 批准号:
    62301147
  • 批准年份:
    2023
  • 资助金额:
    30 万元
  • 项目类别:
    青年科学基金项目
基于多信道最小项的扩展型可编程逻辑阵列芯片研究
  • 批准号:
    61905083
  • 批准年份:
    2019
  • 资助金额:
    23.0 万元
  • 项目类别:
    青年科学基金项目
可编程超材料的动力学及调控机理
  • 批准号:
    11672187
  • 批准年份:
    2016
  • 资助金额:
    60.0 万元
  • 项目类别:
    面上项目
高阶广义k-对角线性系统的异构协同并行求解算法研究与探索
  • 批准号:
    61572175
  • 批准年份:
    2015
  • 资助金额:
    66.0 万元
  • 项目类别:
    面上项目
基于可编程光纤激光器与有机非线性晶体的光纤太赫兹融合系统研究
  • 批准号:
    61107087
  • 批准年份:
    2011
  • 资助金额:
    30.0 万元
  • 项目类别:
    青年科学基金项目

相似海外基金

CAREER: Theoretical and Computational Advances for Enabling Robust Numerical Guarantees in Linear and Mixed Integer Programming Solvers
职业:在线性和混合整数规划求解器中实现鲁棒数值保证的理论和计算进展
  • 批准号:
    2340527
  • 财政年份:
    2024
  • 资助金额:
    $ 20万
  • 项目类别:
    Continuing Grant
The Helicase and Nucleic Acid-based Machines Conference: Structure, Mechanism, Regulation and Roles in Human Diseases
解旋酶和核酸机器会议:结构、机制、调节和在人类疾病中的作用
  • 批准号:
    10753877
  • 财政年份:
    2023
  • 资助金额:
    $ 20万
  • 项目类别:
Transcriptional basis of stereotyped neural architectures
刻板神经结构的转录基础
  • 批准号:
    10672300
  • 财政年份:
    2022
  • 资助金额:
    $ 20万
  • 项目类别:
Transcriptional basis of stereotyped neural architectures
刻板神经结构的转录基础
  • 批准号:
    10525865
  • 财政年份:
    2022
  • 资助金额:
    $ 20万
  • 项目类别:
Culturally Tailored Nutrition Therapy To Improve Dietary Adherence of Type 2 Diabetes Patients in Benin, Africa
根据文化量身定制的营养疗法可提高非洲贝宁 2 型糖尿病患者的饮食依从性
  • 批准号:
    10706336
  • 财政年份:
    2022
  • 资助金额:
    $ 20万
  • 项目类别:
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了