Exploring Polyhedra Representing Large-Scale Data Sets

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

• 批准号: RGPIN-2019-07134
• 负责人: Stephen, Tamon
• 金额: $ 1.89万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=716277
• 关键词: Exploring; Polyhedra; Representing; Large; Scale

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）提出了一种算法，即使仅作为甲骨文（Oracle）可用，即使MBF仅可用，即使MBF仅可用。 该提议的一个目的是提高我们对理论和实践中弗雷德曼 - 卡奇扬扬算法的理解。 这包括识别类别的MBF类，这些类别对于联合一代算法特别容易或困难。然后可以使用此分类来改善实现。 更雄心勃勃的目标是确定MBF生成的输出敏感多项式时间算法是否存在。 MBF是多元化复杂系统的隐藏数学结构，我们认为在许多应用程序中，理解可以通过对这种结构的认识来提高理解。 我们特别受代谢网络中的应用程序的动力。要与这些网络一起使用，了解其最小功能子系统（称为基本模式以及最小的阻塞（或淘汰）集，这很有帮助。