將遺傳算法(或其他啟發式方法)與CPLEX集成


9

[討論GA和CPLEX的主題]

我已經看到一些論文試圖將遺傳算法與CPLEX集成在一起,例如herehere。儘管他們將兩者集成在一起,但是它分兩個不同的步驟完成;也就是說,他們第一步使用CPLEX,獲得的結果將用作第二步的輸入,在第二步中使用GA(反之亦然)。

但是,我想知道是否有可能在同一步驟中將CPLEX集成到GA中以解決大量問題。考慮到GA方法和CPLEX是求解器這一事實,最初,我會對這個問題說不。但是,我想打開有關啟發式方法與CPLEX集成的討論,以了解其他觀點和觀點。

如果已經有人將啟發式和CPLEX集成在一起,並且可以分享一些技巧,我將非常感激。

7

I am aware of two ways of combining a (meta-)heuristic with a solver (like cplex).

1) Warm start: use a heuristic to quickly find a good solution and give it to the solver as a starting solution. This can help pruning the branch and bound tree considerably. (e.g. "Designing sustainable energy regions using genetic algorithms and location-allocation approach").

Advice:

  • The warm start method is useful, if cplex struggles to find a legal solution but is quick to improve it, once found; or cplex struggles to find a good solution, but once given it, is quick to make the optimality gap small; Or a good initial solution helps prune the branch and bound tree significantly.

  • Sometimes improving the model or solution method, s.t. the solver is faster on its own (e.g. by making the relaxation tighter or using local branching) is better when you need the optimal solution. If you don't need any guaranties on the optimization gap and the model is incredibly hard to solve, more runtime for the heuristic and no second phase is sometimes the better bet.

2) Decompose: part your model in a "master model" that doesn't contain all variables or all constraints. Put the rest in a "slave model" that based on the solution to the master model computes a solution to a different model and returns the information to the master model (e.g. adding variables in column generation, adding constraints in (combinatorial) benders decomposition, "A distribution network optimization problem for third party logistics service providers"). Or the slave model combines the solution of the master model with its own solution to a solution to the entire problem. In this case you could also consider multi-stage techniques (e.g. fix and optimize or hierarchical planing).

Advice:

  • Decomposition is hard. The idea is to find a subproblem, that is easier to solve than the original problem. Easier could mean it is solvable in polynomial time, or that it can be solved very fast in practice (e.g. set covering).

  • Think about the communication between the different levels of models. How does the solution to the master model influence the slave model(s)? How is the solution to the slave model communicated to the master model?

  • If the master model is heuristic, it is typically because you need to solve a practically easily solvable problem to get the objective value for the solution of the heuristic. Therefore you use an exact solver to get that objective value in the slave model.

  • If the master model is an exact MIP-model and the slave model is a heuristic, you typically generate variables and cuts with it. This usually means that the whole process is a heuristic.

  • If the master model is an exact MIP-model, the information communicated to the subproblem are typically the dual prices, if you want to generate variables; and the solution, if you want to generate cuts.