英文:
Do MIP Solvers (e.g. CBC, Gurobi, ...) automatically decompose separable problems?
问题
我有许多优化问题,我用CBC
逐个解决。
或者,我把所有这些问题合并成一个优化问题,只需一次求解。我的想法是为了减少开销,我假设CBC
会自动识别这些部分是可以分开的。
结果是相同的,所以我做得没错。不幸的是,解决方案的时间要长得多。所以我的问题是:
CBC
无法识别它可以分开一个优化问题吗?- 难道提前识别可分性不应该很容易吗?
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:
CBC
does not recognize that it can separate an optimization problem?- Shouldn't it be easy to recognize separability in advance?
- 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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论