Integrating genetic algorithm (or other heuristic methods) with CPLEX

Question

[Topic to discuss GA and CPLEX]

I've seen some papers trying to integrate genetic algorithm with CPLEX, such as here and here. Although they integrated both, it is done in 2 different steps; that means, they use CPLEX in one step and the results obtained are used as input for the second step, in which GA is used (or vice-versa).

However, I am wondering if it would be possible to integrate CPLEX in GA on the same step to solve large instances of problems. Considering the GA methodology and the fact that CPLEX is a solver, initially, I would say no to this question. But I would like to open this discussion about the integration of heuristic methods with CPLEX to know other opinions and perspectives.

If someone already worked with both, heuristic and CPLEX integrated, and can share some tips, I would be really grateful.

Answer 1

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.