Exploring Polyhedra Representing Large-Scale Data Sets

线性规划模型是有价值的，因为它们可以通过基于pivot的策略（如单纯形方法）或内点方法快速解决，甚至对于非常大规模的问题。这两种方法都是有效的，但也有缺点：旋转算法没有很好的最坏情况复杂度保证，而内点法容易受到数值问题的影响。一个有趣的想法是朝着保留旋转结构的混合过程移动，因此是有效的组合，但也包括通过多面体内部的移动。最自然的实现是扩展可用方向集以包含所有电路（或基本）方向，并在一个方向上持续移动直到达到约束。这些额外的电路方向提供了通过多面体的更短路线，就枢轴的数量而言。本研究的目的之一是有效地利用电路和其他混合增强算法进行优化。这样做的一个强烈动机是扩展到离散和非线性环境的可能性。在这些情况下，产生不一定总是获得最优解，但提供近似保证或仅仅在实际问题上工作良好的结果已经很有趣了。在一些应用程序中，与其使用一个固定的目标（可能事先不知道），不如开发一个潜在（或帕累托）最优解决方案的菜单。一个重要的特殊情况是多面体表示单调布尔函数（MBF）。这里的极值点对应于函数的最小真值。Fredman和kachiyan提出了一种算法，即使MBF仅作为一个oracle可用，也能在增量拟多项式时间内生成所有这些极值点。本提案的目标是提高我们对fredman - kachiyan算法在理论和实践中的理解。这包括识别对联合生成算法来说特别容易或困难的mbf类别。然后可以使用这种分类来改进实现。一个更远大的目标是确定是否存在输出敏感的多项式时间算法来生成MBF。mbf是一种隐藏在各种复杂系统之下的数学结构，我们相信，通过对这种结构的认识，我们可以在许多应用中提高对它的理解。我们特别受到代谢网络应用的激励。为了处理这些网络，理解它们的最小功能子系统（称为基本模式）以及它们的最小阻塞（或淘汰）集是有帮助的。

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.