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仅作为Oracle可用。 这个建议的一个目标是提高我们对Fredman-Khachiyan算法在理论和实践上的理解。 这包括识别对于联合生成算法特别容易或困难的MBF的类别。然后，可以使用这种分类来改进实现。 一个更雄心勃勃的目标是确定是否存在一个输出敏感的多项式时间算法的MBF生成。 MBF是一种隐藏在各种复杂系统下的数学结构，我们相信有许多应用程序可以通过了解这种结构来提高理解力。 我们的动机，特别是在代谢网络中的应用。要使用这些网络，了解它们的最小功能子系统（称为基本模式）以及它们的最小阻塞（或淘汰）集是有帮助的。