在大规模线性规划中，如何使用内点法得到具有最优objective值的极值点？
How to use interior point method to get an extreme point with optimal objective value in large scale linear programming?
我需要求解一个约束很少但变量很多的线性规划：
A 是 mxn。 m约为15，但n大于100万。我使用具有不同算法（对偶单纯形、内点、内点遗留）的 Matlab linprog。下面是他们花费的时间。
对偶单纯形法需要将近一天的时间。
内点法需要一天多时间
Interior-point-legacy 只需要 5 分钟。
据我所知，在大规模线性规划中，内点法比单纯形法更快。但是上面的结果1和2是出乎意料的
只讨论对偶单纯形法(1)和内点遗留法(3)。他们得到不同的答案。 (1) 得到一个只有 12 个非零项的答案，而 (3) 得到一个所有项都非零的答案。两个答案具有相同的 objective 值。
（1）的答案是我想要的（只有几个非零项），但是（1）很费时。 (3) 的答案是一个内点，因此所有项都非零。但几乎 99% 的项都非常小（小于 0.001）。那不是我想要的。但是 (3) 很快。
我要的是让(3)的答案走到极点。 （令非零项的个数至多为约束的个数。）我用'large scale'、'interior point method'、'linear programming'等关键字在网上搜索过，没找到我还想要什么。有什么方向或建议吗？
抱歉，有一件事我忘了说。我在 A 和 b 中的系数都是正的。而c中的系数都是"-1"。
对于您的情况，筛选方法可能最适合：
- https://www.ibm.com/support/knowledgecenter/en/SS9UKU_12.7.0/com.ibm.cplex.zos.help/CPLEX/UsrMan/topics/cont_optim/simplex/10_sifting.html
- http://www.gurobi.com/documentation/7.5/refman/sifting.html#parameter:Sifting
筛选迭代地解决仅包含一些变量的子问题，并检查其余变量的最优性。这可以工作，因为正如您已经建议的那样，基本解决方案中的大多数变量都将为零。
CPLEX 或 Gurobi 等大多数商业求解器都会自动使用此方法来解决您的问题。
我认为您想从内点解转到基本解（角点）。这叫做“crossover”。像 Cplex 和 Gurobi 这样的求解器有这个 built-in。请注意，交叉可能很昂贵（我见过模型，其中障碍方法可以快速解决 LP，但交叉需要很长时间）。我相信Matlab优化工具箱没有交叉算法。
我需要求解一个约束很少但变量很多的线性规划：
A 是 mxn。 m约为15，但n大于100万。我使用具有不同算法（对偶单纯形、内点、内点遗留）的 Matlab linprog。下面是他们花费的时间。
对偶单纯形法需要将近一天的时间。
内点法需要一天多时间
Interior-point-legacy 只需要 5 分钟。
据我所知，在大规模线性规划中，内点法比单纯形法更快。但是上面的结果1和2是出乎意料的
只讨论对偶单纯形法(1)和内点遗留法(3)。他们得到不同的答案。 (1) 得到一个只有 12 个非零项的答案，而 (3) 得到一个所有项都非零的答案。两个答案具有相同的 objective 值。
（1）的答案是我想要的（只有几个非零项），但是（1）很费时。 (3) 的答案是一个内点，因此所有项都非零。但几乎 99% 的项都非常小（小于 0.001）。那不是我想要的。但是 (3) 很快。
我要的是让(3)的答案走到极点。 （令非零项的个数至多为约束的个数。）我用'large scale'、'interior point method'、'linear programming'等关键字在网上搜索过，没找到我还想要什么。有什么方向或建议吗？
抱歉，有一件事我忘了说。我在 A 和 b 中的系数都是正的。而c中的系数都是"-1"。
对于您的情况，筛选方法可能最适合：
- https://www.ibm.com/support/knowledgecenter/en/SS9UKU_12.7.0/com.ibm.cplex.zos.help/CPLEX/UsrMan/topics/cont_optim/simplex/10_sifting.html
- http://www.gurobi.com/documentation/7.5/refman/sifting.html#parameter:Sifting
筛选迭代地解决仅包含一些变量的子问题，并检查其余变量的最优性。这可以工作，因为正如您已经建议的那样，基本解决方案中的大多数变量都将为零。
CPLEX 或 Gurobi 等大多数商业求解器都会自动使用此方法来解决您的问题。
我认为您想从内点解转到基本解（角点）。这叫做“crossover”。像 Cplex 和 Gurobi 这样的求解器有这个 built-in。请注意，交叉可能很昂贵（我见过模型，其中障碍方法可以快速解决 LP，但交叉需要很长时间）。我相信Matlab优化工具箱没有交叉算法。