Exploring Polyhedra Representing Large-Scale Data Sets

线性规划模型很有价值，因为它们可以通过基于旋转的策略(如单纯形法)或内点法快速求解，即使是对于非常大规模的问题。这两种方法都是有效的，但也有缺点：旋转算法没有很好的最坏情况下的复杂性保证，而内点方法容易受到数值问题的影响。一个耐人寻味的想法是转向一种混合程序，它保留了旋转结构，因此是有效的组合，但也包括穿过多面体内部的移动。 最自然的实现方式是扩展可用方向集，以包含所有电路(或初级)方向，并继续沿某个方向移动，直到达到约束。就枢轴的数量而言，这些额外的电路方向提供了通过多面体的较短路线。这项研究的目的之一是有效地使用电路和其他混合增强算法进行优化。这样做的一个强烈动机是有可能扩展到离散和非线性环境。在这些情况下，产生的结果不一定总是达到最优解，但提供近似保证或只是在实际问题上很好地工作，这已经是很有趣的事情了。 在某些应用中，与其使用一个可能事先未知的固定目标，不如开发一个潜在(或帕累托)最优解的菜单。一个重要的特例是当多面体表示单调布尔函数(MBF)时。这里的极值点对应于函数的最小真实设置。Fredman和Khchiyan提出了一种算法，即使在MBF仅作为先知可用的情况下，也可以在增量拟多项式时间内生成所有这样的极点。这一建议的一个目的是提高我们在理论和实践中对Fredman-Khchiyan算法的理解。这包括识别对于联合生成算法特别容易或困难的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.