我正在寻找为
具有许多顶点的单纯形法线性规划求解器（A x <= b，x >= 0）生成测试问题的方法，因此（我相信）会产生困难的测试问题。
有很多看起来相关的理论，例如 凸多面体可以有多少个顶点？ 但是我不知道如何将其转换为 A b 的代码——我不需要所有顶点，而且顶点枚举 无论如何都会爆炸内存。
例如，一个 1000 x 1000 的分配问题给出了一个稀疏的 2k x 1m A 矩阵，其中有 2m 个非零。GLPK simplex 在 34 秒内解决了这个问题——这不是一个测试用例。
问问题
96 次
1 回答
0
扩展拉丁方格给出 LP 矩阵，其中 4n^3 行（约束）、n^4 列（变量）和每列 4 个非零。例如，n=16 -- 2^14 行、2^16 列、2^18 个非零 --在我的 2.7 GHz iMac 上的开源GLPK单纯形求解器中运行 10 小时。
（ Klee-Minty 立方体，曾经是单纯形方法的一个困难测试用例，在 GLPK 单纯形中运行时间小于 1 秒，d=200。欢迎对为什么某些 LP 问题很难的一些直觉。）
于 2019-10-08T14:05:15.860 回答