混合整数编程可以解决多少个决策变量？
我有一个混合整数编程问题（二进制整数变量），我可以解决多少个变量，即上限和将花费多少时间？
该问题将具有最大限度的约束和最小化成本函数，但变量是以m * n矩阵的形式。 所以，问题是可能是m和n的最大值，也是完成计算所需的时间？
使用COIN CBC，GLPK，CPLEX，GUROBI等标准软件/库。
真的有可能使用市场上可用的开源/商业解决方案来解决它吗？
简而言之：是的，可以用数百万个决策变量解决MIP问题。
理论
一般而言，MIP是NP难题，不能用多项式时间O（n ^ k）求解。 此外，确定MIP问题的输入“n”是不直接的 。 不是。 行，列或其产品，矩阵A性质，决策变量的性质，MIP和宽松LP之间的差距？
如果IP公式（Ax = b），矩阵A是完全单模的，并且所有系数都是整数，那么LP松弛的解也是IP的解，因此问题的复杂性是多项式 。
如果不是的话，那么你应该期望在一般情况下这个问题是NP-hard。 作为一个拇指规则，变量越多，约束越多，问题越难。
实践
MIP / LP求解器可以使用各种技术/算法在合理的时间内（以小时为单位）解决任何问题，特别是如果您不寻找“最优整数解决方案”并愿意接受解决方案来关闭最优解。
没有固定的尺寸限制 - 即使在标准的笔记本电脑和台式电脑上，Gurobi Optimizer也可以定期解决具有数百万变量和约束条件的模型。 更重要的是，您可以在Gurobi的表现中看到结果，尤其是在更大，更难的模型上。 事实上，Gurobi最近解决了MIPLIB2010库中的11个模型，这些模型以前没有被其他解算器解决过。
来源：http://www.gurobi.com/products/gurobi-optimizer
特殊的MIP问题
特殊技术可用于解决MIP的特殊情况。
我写了简单的列生成算法来解决切割库存问题。 请参阅https://github.com/vcphub/cspsol
链接地址: http://www.djcxy.com/p/39987.html上一篇: How many decision variables can be solved for Mixed Integer Programming?