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

Question

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

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

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

Answer 1

Is it really possible to use the open-source/commercial solvers, available in the market, to solve it ?

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

理论

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

如果 IP 公式 ( Ax = b )，则矩阵 A 为 totally unimodular ，并且所有系数都是整数，那么 LP 松弛的解也是 IP 的解，因此问题的复杂度是多项式。

如果不是，那么您应该预期该问题在一般情况下是 NP 困难的。根据经验，变量越多、约束越多，问题就越难。

练习

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

There is no fixed size limit — the Gurobi Optimizer routinely solves models with millions of variables and constraints, even on standard laptop and desktop computers. More importantly, you can see the results in Gurobi's performance, particularly on larger, more difficult models. In fact, Gurobi recently solved 11 models in the MIPLIB2010 library that had not previously been solved by any other solver.

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

特殊 MIP 问题

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

• Cutting stock problem
• bin packing problem :切削料问题的特殊情况。

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