Shrinkwrapping Linear Programs

提出了一种新的线性规划（更一般地说，双曲规划）算法族，在计算和理论两方面得到进一步发展。设想是一个完整的数学发展的新算法框架，隔离那些看起来可能是有关的构建真正实用的算法，和实现的免费可用性（部分是为了鼓励其他研究人员参与和改进的努力）。与现有的线性规划算法不同，新框架采用分层组合结构。算法按顺序遍历层，从最不复杂的层开始，一直到获得最优解，这通常发生在到达最后一层之前很久，也就是说，在明确计算完整组合结构之前很久。通过初等对称多项式及其双曲锥和离散快速傅立叶变换（dFFT），使分层的新思想在计算上易于处理。线性规划作为一种建模工具在日常应用中无处不在，在各种运输调度中，在一系列综合财务管理活动中，以及在任何需要最有效地部署有限资源的地方，都依赖于线性规划。更广泛地使用线性程序的主要瓶颈，特别是在数据经常变化的环境中，是求解线性程序所需的计算时间。因此，通过创建能够比以前更快地获得线性规划解决方案的算法，开发像这里展示的这样的新框架具有对社会产生更广泛影响的潜力，从而扩展了线性规划作为建模工具的有用性。该提案的智力价值来自于新框架的潜力，它通过向研究领域注入鼓舞人心的新概念，为线性规划（及其扩展）的算法研究注入活力。自内点方法引起轰动以来，这个领域在20年内基本上变得僵化了。知识价值也来自框架带来的凝聚力，框架从工程（例如，线性规划，dFFT）延伸到经典数学（例如，对称函数，黎曼几何）。

It is proposed that a new family of algorithms for linear programming (moregenerally, for hyperbolic programming) be further developed, both computationallyand theoretically. Envisioned is a full mathematical development of the newalgorithmic framework, isolation of those ideas that appear likely to be pertinentfor constructing truly practical algorithms, and the free availability of implementations(partly to encourage other researchers to participate and improve on theefforts).Unlike existing algorithms for linear programming, the new framework layerscombinatorial structure. The algorithms work through the layers sequentially,beginning with the least complex one, and continuing until an optimal solu-tionis attained, which generally occurs long before reaching the final layer, i.e.,long before explicitly calculating with the full combinatorial structure. The newidea of layering is made computationally tractable via the elementary symmetricpolynomials, their hyperbolicity cones, and the discrete Fast Fourier Transform(dFFT).Linear programming as a modeling tool is pervasive in daily applications, beingrelied upon in all kinds of transportation scheduling, in an array of integrativefinancial management activities, and more generally, anywhere that limited resourcesneed to be deployed most efficiently. A primary bottleneck to even moreextensive use of linear programs, especially in settings where data change oftenis the computational time required to solve linear programs. Consequently,development of a novel framework such as the one presented here has the poten-tialof broader impact on society through the creation of algorithms capableof attaining linear program solutions faster than before, thereby extending theusefulness of linear programming as a modeling tool.Intellectual merit for the proposal comes from the new framework's po-tentialto invigorate algorithmic investigations into linear programming (and itsextensions) by infusing inspiring new concepts into the research area, an area thathas largely become staid in the 20 years since interior-point methods created stir.Intellectual merit also comes from the cohesion brought by the framework, aframework that stretches from engineering (e.g., linear programming, dFFT) toclassical mathematics (e.g., symmetric functions, Riemannian geometry).