linear-programming - 混合整数规划可以解决多少个决策变量？

Question

我有一个混合整数规划问题（二进制整数变量），我可以解决多少个变量，即上限以及需要多少时间？

该问题将具有最大 5 个约束和最小化成本函数，但变量采用 m*n 矩阵的形式。所以，问题是 m 和 n 的最大值是多少，以及完成计算所需的时间？

使用标准软件/库，如 COIN CBC、GLPK、CPLEX、GUROBI。

Answer 1

是否真的可以使用市场上可用的开源/商业求解器来解决它？

简短回答：是的，可以使用数百万个决策变量来解决 MIP。

理论

一般来说，MIP 是NP-hard 问题，不能在多项式时间 O(n^k) 内求解。此外，确定 MIP 问题中输入“n”的内容并不简单。是不是。行、列或它们的乘积，矩阵A的性质，决策变量的性质，MIP 和宽松 LP 之间的差距？

如果 IP 公式（ Ax = b ），矩阵 A 是完全单模的，并且所有系数都是整数，那么 LP 松弛的解也是 IP 的解，因此您的问题的复杂性是多项式的。

如果不是，那么您应该预计问题在一般情况下是 NP 难的。作为一个经验法则，变量越多，约束越多，问题就越难。

实践

MIP/LP 求解器可以使用各种技术/算法在合理的时间内（以小时为单位）解决任何问题，特别是如果您不是在寻找“最佳”整数解决方案并且愿意接受接近最优的解决方案。

没有固定的大小限制——Gurobi 优化器通常会求解具有数百万个变量和约束的模型，即使在标准笔记本电脑和台式电脑上也是如此。更重要的是，您可以在 Gurobi 的性能中看到结果，尤其是在更大、更困难的模型上。事实上，Gurobi 最近求解了 MIPLIB2010 库中的 11 个模型，这些模型以前没有被任何其他求解器求解过。

资料来源：http ://www.gurobi.com/products/gurobi-optimizer

特殊 MIP 问题

特殊技术可用于解决 MIP 的特殊实例。

• 切割库存问题
• 装箱问题：切割库存问题的特殊情况。

我编写了简单的列生成算法来解决库存问题。见https://github.com/vcphub/cspsol