組合優化:元啟發法,CP,IP-"與"還是"與"?


18

"最近" someone asked on Twitter是否"人們仍然對整數程序使用遺傳算法"。"多數答案",即1中的1:"是"

因此, my 的後續問題是:一方面,隨著(A)計算機硬件的所有進步,求解器的改進和IP的分解技術,(B)"精巧的"框架各種搜索策略(TS,SA,GA,VNS等),以及位於兩者之間的(C)約束(編程)求解器...

... 如何確定問題A,B或/和C是否需要解決問題[當問題約束適合於(或:可以捕獲在這些"範式"中的任何一個中] –例如,當解決方案的"質量"超過可用性"接近"時間結果的方面時,給定JSPFSP的多階段版本?

適用的標準/經驗法則/ ...是什麼?會考慮/執行哪些步驟以找出最有效的方法?

20

Here, in approximate order, are my criteria.

  1. Do I need a provably optimal solution (which rules out metaheuristics, other than to generate an initial feasible solution)?
  2. Is this something CPLEX can handle (since I have a license for CPLEX and I'm familiar with it)?
  3. If CPLEX can handle it, should I consider a heuristic, metaheuristic or constraint solver to generate a first feasible solution? (This gets determined empirically in most cases, by running CPLEX and seeing how long it takes to a get a "good" incumbent.)
  4. Assuming that I'm still shopping for an approach at this point, does the problem have a structure that might favor a constraint solver? In my case, given that I have CP Optimizer but am not nearly as familiar with it as with CPLEX, that usually means there's a scheduling aspect to the problem.
  5. If I'm looking for heuristics, is there something in the problem that suggests a likely problem-specific heuristic? If so, go that route. If not, I'll likely go with a GA, since I have experience with GAs and not so much with other metaheuristics.

One other consideration that does not fit neatly into that list: am I doing this for myself or for someone else? If it's for someone else, and they don't have moderately deep pockets (to pay for a solver license), I'll probably switch to a heuristic/metaheuristic and code it myself. I know about the COIN-OR solvers, but they're mainly for C/C++/Python programmers, and I have not kept tabs with progress (if any) adding Java APIs.