MIP求解器(例如CBC,Gurobi等)是否会自动分解可分离的问题?

huangapple go评论53阅读模式
英文:

Do MIP Solvers (e.g. CBC, Gurobi, ...) automatically decompose separable problems?

问题

我有许多优化问题,我用CBC逐个解决。

或者,我把所有这些问题合并成一个优化问题,只需一次求解。我的想法是为了减少开销,我假设CBC会自动识别这些部分是可以分开的。

结果是相同的,所以我做得没错。不幸的是,解决方案的时间要长得多。所以我的问题是:

  1. CBC无法识别它可以分开一个优化问题吗?
  2. 难道提前识别可分性不应该很容易吗?
  3. Gurobi能做到吗?

谢谢你的提示!

英文:

I have many optimization problems that I solve sequentially with CBC.

Alternatively, I throw all these problems into one optimization problem and just do one solve. The idea was to reduce overhead and I assumed that CBC automatically recognizes that the parts are separable.

The result was identical, so I did everything correct. Unfortunately, the solution time was much much higher. So my questions:

  1. CBC does not recognize that it can separate an optimization problem?
  2. Shouldn't it be easy to recognize separability in advance?
  3. Does Gurobi do that?

Thanks four your hints!

答案1

得分: 1

No. 求解器不会自动或默认进行分解。Cplex可以自动执行Benders(使用选项)。

所有子问题都完全独立的特殊情况并不常见。因此,求解器不会检测到这一点,因此会将其视为一个大问题来解决。如果子问题有关联,可能有不同的方法来实现更快的速度(例如通过更新问题)。

对于许多小的独立问题(例如DEA问题),将一些问题批量处理在一起可能是有意义的(例如,不是100个小问题,而是解决10批10个问题)。这可能会产生一些差异。

英文:

No. Solvers don't do decomposition automatically or by default. Cplex can do Benders automatically (using an option).

The special case where all subproblems are totally independent is not so common. So solvers don't detect this and thus ignore that and solve it as one big problem. If the subproblems are related there may be different ways to achieve better speed (e.g. by updating the problem).

For many small independent problems (like in DEA problems), it may make sense to batch a few problems together (e.g. instead of 100 tiny problems, solve 10 batches of 10). This can make some difference.

huangapple
  • 本文由 发表于 2023年4月20日 02:59:41
  • 转载请务必保留本文链接:https://go.coder-hub.com/76057994.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定