$10^{13}$在当今最大的超级计算机上难以处理，主要是由于内存限制。我见过实际解决的最大问题大约有行和列，但最重要的因素往往是非零的数量，我们只是在解决非零的问题。请参阅Mittelman 的并行基准测试页面，了解最好的免费和商业求解器可以在这种规模的一系列问题上做些什么。$10^5$$10^6$

大量的不等式约束通常可以通过约束生成技术处理，每次只处理有限数量的约束，并将在当前解中违反的约束添加到约束集（同时删除强烈满足的约束）。但是在我看到的情况下，这也要求非松弛变量的数量也是有限的。

所以问题是你是否可以重新表述你的问题，使问题本身或其对偶的变量比约束少得多。

编辑：另见 Nesterov 最近关于“大规模优化问题的次梯度方法”的工作， http ://dial.academielouvain.be/vital/access/services/Download/boreal:107876/PDF_01 。如果精度要求适中，他的技术在复杂度为$O(n\log n)$

我对 Aron 回答的评论太长了，但我想补充一下他的回答：

我喜欢提出并行基准测试的例子。在这里添加几条评论。测试的所有四个求解器都是商业的，但有免费的学术许可证可用。此外，该测试在 25000 秒或约 8 小时时切断了运行时间，这是任意的，并且严重依赖于外部资源限制（即，在公司中，人们可能不愿意等待超过一天的结果；在学术界，有些人可以运行几个月的模拟）。该测试是在单台四核机器上运行的，对我来说，这并不代表最先进的性能。

当我四处寻找数据来回答这个问题时，我发现 10 多年前的论文解决了大致相同规模的问题，这表明我们现在可以利用现有的基础设施做得更好。当然不是变量，而是基于内点方法缩放，如果线性代数和并行性实现得很好，并且你有时间和一个中等大小的集群，我看不到为什么你不能尝试用或者10$10^{13}$$n^{3.5}$$10^{7}$ $10^{8}$变量（只有当你有特殊的结构时，你才能利用分解方法，如 Benders 分解或 Dantzig-Wolfe，以及切割平面生成算法）。（我要补充一点，我忽略了约束的影响，这取决于存储了多少位，这会使事情变得复杂；这种影响只会使下面的估计更加悲观。）

我相信 GAMS 有一个并行实现，并且由于它使用像 CPLEX、Gurobi、MOSEK 和 Xpress 之类的求解器（即 Aron 引用的基准测试中的四个求解器），我不明白为什么不能运行这些的并行实例求解器（事实上，我知道这对于 CPLEX 和 Gurobi 是可能的）。限制因素将是内存（因为内存很昂贵）和通信而不是处理能力，因为线性程序最终会减少重复构建和求解线性方程组（是的，这是一个巨大的过度简化，但线性代数是我们知道如何并行化）。

但是变量太多了。假设内存和通信不是对象，您需要解决基准测试中最大的问题，并将该机器上的运行时间扩展大约倍，然后才能利用您的特定问题可能的特殊结构有。这并不是说你不能尝试使用 Neumaier 教授建议的方法来近似解决它，但是如果不等待很长时间、使用大型计算机并具有可扩展的实现LP 求解器针对那台巨大的计算机进行了调整。$10^{13}$$10^{24}$

作为一个非常粗略的数量级估计，Aron 引用的基准测试中使用的 Intel Core 2 Quad 可以以 40 gigaflops 的峰值速度运行。假设您要使用橡树岭国家实验室的超级计算机 Jaguar，并且可以使用整台机器（极不可能，但让我们梦想成真），您将有大约 2 petaflops 触手可及（基于此处的 TOP 500 数字，或者大约是计算能力的 50000 倍，这还不包括由于通信、内存限制或没有人以最高速度运行（甚至是 LINPACK 基准测试）这一事实造成的损失。

从到变量意味着大约增加了 10,000 倍，您可以想象将其分成 50-100 台机器的集群，并等待一个月（假设您愿意等待，您拥有机器，再一次，内存和通信不受限制，所有这些都是很大的“如果”）。从到变量意味着从您的桌面到使用所有 Jaguar，并等待大约到年。（同样，这些影响也忽略了你将有更多约束的事实！）$10^{6}$$10^{7}$$10^{6}$$10^{13}$$10^{17}$$10^{18}$

这是一个老问题，但是，嘿，25 多年前，有人已经可以在 PC 集群上在 3 小时内解决 1.1M 约束、2.6M 变量问题。http://www.maths.ed.ac.uk/~gondzio/CV/finance.pdf

我想看看生成方程，也许在你把这个问题扔给算法之前做一些认真的分解是聪明的，我想说作为一个从业者，在给硬件喂食之前咀嚼它也许是聪明的。在计算机内存和精度有限的情况下，这听起来也像是会导致公式中的数值错误的大小。