Exploring Polyhedra Representing Large-Scale Data Sets

探索表示大规模数据集的多面体

基本信息

  • 批准号:
    RGPIN-2019-07134
  • 负责人:
  • 金额:
    $ 1.89万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2020
  • 资助国家:
    加拿大
  • 起止时间:
    2020-01-01 至 2021-12-31
  • 项目状态:
    已结题

项目摘要

Linear programming models are valuable because they can be solved quickly, even for very large-scale problems, via either pivoting-based strategies, such as the simplex method, or by interior-point methods. Both of these are effective, but also have drawbacks: the pivoting algorithms do not have good worst-case complexity guarantees, while interior point methods are vulnerable to numerical issues. An intriguing idea is to move towards a hybrid procedure that retains a pivoting structure, as thus is effectively combinatorial, but also includes moves that pass through the interior of the polyhedron. The most natural implementation of this is to expand the set of available directions to contain all circuit (or elementary) directions, with moves in a direction continuing until a constraint is reached. These additional circuit directions give shorter routes through polytopes, in terms of the number of pivots. One aim of this research is to use circuit and other hybrid augmentation algorithms effectively in optimization. A strong incentive to do this is the possibility of expanding to discrete and non-linear contexts. In these contexts, it will already be interesting to produce results that do not necessarily always attain the optimal solution, but provide approximation guarantees or simply work well on practical problems. In some applications, rather than working with a fixed objective, which may not be known in advance, it is better to develop a menu of potentially (or Pareto) optimal solutions. An important special case is when the polyhedron represents a monotone Boolean function (MBF). Here the extreme points correspond to the minimal true settings of the function. Fredman and Khachiyan proposed an algorithm which generates all such extreme points in incremental quasi-polynomial time even when the MBF is only available as an oracle. A goal of this proposal is to improve our understanding of the Fredman-Khachiyan algorithm both in theory and in practice. This includes identifyng classes of MBFs that are particularly easy or difficult for the joint generation algorithm. This classification can then be used to improve implementations. A more ambitious target is determining if an output sensitive polynomial time algorithm exists for MBF generation. MBFs are a hidden mathematical structure underlying diverse complex systems, and we believe there are many applications where understanding could improve through awareness of this structure. We are motivated in particular by applications in metabolic networks. To work with these networks, it is helpful to understand their minimal functional subsystems, known as elementary modes as well as their minimal blocking (or knockout) sets.
线性规划模型很有价值,因为它们可以通过基于枢轴的策略(例如单纯形法)或通过内点法快速解决,即使对于非常大规模的问题也是如此。这两种方法都很有效,但也有缺点:旋转算法没有良好的最坏情况复杂性保证,而内点方法容易受到数值问题的影响。一个有趣的想法是转向保留旋转结构的混合程序,因此是有效的组合,但也包括穿过多面体内部的移动。 最自然的实现是扩展可用方向集以包含所有电路(或基本)方向,并继续沿某个方向移动直到达到约束。 就枢轴数量而言,这些附加的电路方向提供了通过多面体的更短的路线。 这项研究的目的之一是在优化中有效地使用电路和其他混合增强算法。 这样做的一个强烈动机是扩展到离散和非线性环境的可能性。 在这些情况下,产生不一定总是获得最佳解决方案但提供近似保证或只是在实际问题上表现良好的结果已经很有趣了。 在某些应用中,与其使用可能无法提前知道的固定目标,不如开发一个潜在(或帕累托)最优解决方案的菜单。 一个重要的特殊情况是多面体表示单调布尔函数 (MBF)。 这里的极值点对应于函数的最小真实设置。 Fredman 和 Khachiyan 提出了一种算法,即使 MBF 只能作为预言机使用,该算法也可以在增量拟多项式时间内生成所有此类极值点。 该提案的目标是提高我们对 Fredman-Khachiyan 算法在理论和实践上的理解。 这包括识别对于联合生成算法来说特别容易或特别困难的 MBF 类别。然后可以使用这种分类来改进实现。 一个更雄心勃勃的目标是确定是否存在用于 MBF 生成的输出敏感多项式时间算法。 MBF 是各种复杂系统背后隐藏的数学结构,我们相信在许多应用中,通过了解这种结构可以提高理解力。 我们特别受到代谢网络中应用的激励。为了使用这些网络,了解它们的最小功能子系统(称为基本模式)以及它们的最小阻塞(或淘汰)集会很有帮助。

项目成果

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

Stephen, Tamon其他文献

Computing knock-out strategies in metabolic networks
  • DOI:
    10.1089/cmb.2007.0229
  • 发表时间:
    2008-04-01
  • 期刊:
  • 影响因子:
    1.7
  • 作者:
    Haus, Utz-Uwe;Klamt, Steffen;Stephen, Tamon
  • 通讯作者:
    Stephen, Tamon

Stephen, Tamon的其他文献

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

{{ truncateString('Stephen, Tamon', 18)}}的其他基金

Exploring Polyhedra Representing Large-Scale Data Sets
探索表示大规模数据集的多面体
  • 批准号:
    RGPIN-2019-07134
  • 财政年份:
    2022
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual
Exploring Polyhedra Representing Large-Scale Data Sets
探索表示大规模数据集的多面体
  • 批准号:
    RGPIN-2019-07134
  • 财政年份:
    2021
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual
Exploring Polyhedra Representing Large-Scale Data Sets
探索表示大规模数据集的多面体
  • 批准号:
    RGPIN-2019-07134
  • 财政年份:
    2019
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual
Pivoting Algorithms and Geometric Optimization Problems
旋转算法和几何优化问题
  • 批准号:
    RGPIN-2014-06371
  • 财政年份:
    2018
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual
Pivoting Algorithms and Geometric Optimization Problems
旋转算法和几何优化问题
  • 批准号:
    RGPIN-2014-06371
  • 财政年份:
    2017
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual
Pivoting Algorithms and Geometric Optimization Problems
旋转算法和几何优化问题
  • 批准号:
    RGPIN-2014-06371
  • 财政年份:
    2016
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual
Pivoting Algorithms and Geometric Optimization Problems
旋转算法和几何优化问题
  • 批准号:
    RGPIN-2014-06371
  • 财政年份:
    2015
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual
Pivoting Algorithms and Geometric Optimization Problems
旋转算法和几何优化问题
  • 批准号:
    RGPIN-2014-06371
  • 财政年份:
    2014
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithms for combinatorial optimization
组合优化算法
  • 批准号:
    341698-2007
  • 财政年份:
    2011
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual
Algorithms for combinatorial optimization
组合优化算法
  • 批准号:
    341698-2007
  • 财政年份:
    2010
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual

相似海外基金

Layered molecular two-dimensional materials based on metal-organic polyhedra
基于金属有机多面体的层状分子二维材料
  • 批准号:
    22KF0219
  • 财政年份:
    2023
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Grant-in-Aid for JSPS Fellows
Dynamic molecular capsule composed of metal–organic polyhedra
金属构成的动态分子胶囊
  • 批准号:
    23K13762
  • 财政年份:
    2023
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
Creation and functionalization of bio-composite systems using metal-organic polyhedra and enzymes
使用金属有机多面体和酶的生物复合系统的创建和功能化
  • 批准号:
    22K19052
  • 财政年份:
    2022
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Grant-in-Aid for Challenging Research (Exploratory)
Vertex Classification of Ball Polyhedra
球多面体的顶点分类
  • 批准号:
    575751-2022
  • 财政年份:
    2022
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Alexander Graham Bell Canada Graduate Scholarships - Master's
Exploring Polyhedra Representing Large-Scale Data Sets
探索表示大规模数据集的多面体
  • 批准号:
    RGPIN-2019-07134
  • 财政年份:
    2022
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual
Exploring Polyhedra Representing Large-Scale Data Sets
探索表示大规模数据集的多面体
  • 批准号:
    RGPIN-2019-07134
  • 财政年份:
    2021
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Discovery Grants Program - Individual
Direct Finite Elements on Convex Polygons and Polyhedra
凸多边形和多面体上的直接有限元
  • 批准号:
    2111159
  • 财政年份:
    2021
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Standard Grant
Compartmentalization of catalysts into metal-organic polyhedra gel for cascade reactions
将催化剂分隔成金属有机多面体凝胶以进行级联反应
  • 批准号:
    20K15366
  • 财政年份:
    2020
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Grant-in-Aid for Early-Career Scientists
Surface Functionalization and Materials Integration of Metal-organic Polyhedra
金属有机多面体的表面功能化与材料集成
  • 批准号:
    20K22554
  • 财政年份:
    2020
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Grant-in-Aid for Research Activity Start-up
Application of Newton polyhedra in various kinds of analysis
牛顿多面体在各类分析中的应用
  • 批准号:
    20K03656
  • 财政年份:
    2020
  • 资助金额:
    $ 1.89万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了