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 提出了一种算法，即使 MBF 只能作为预言机使用，该算法也可以在增量拟多项式时间内生成所有此类极值点。 该提案的目标是提高我们对 Fredman-Khachiyan 算法在理论和实践上的理解。 这包括识别对于联合生成算法来说特别容易或特别困难的 MBF 类别。然后可以使用这种分类来改进实现。 一个更雄心勃勃的目标是确定是否存在用于 MBF 生成的输出敏感多项式时间算法。 MBF 是各种复杂系统背后隐藏的数学结构，我们相信在许多应用中，通过了解这种结构可以提高理解力。 我们特别受到代谢网络中应用的激励。为了使用这些网络，了解它们的最小功能子系统（称为基本模式）以及它们的最小阻塞（或淘汰）集会很有帮助。