A Hybrid Genetic-Benders' Algorithm with Applications to capacitated Plant Location Problems

摘要

Benders' decomposition algorithm has been successfully applied in many areas. A major difficulty with this decomposition lies in the solution of master problem, which is a "hard" problem, costly to compute. Our proposed algorithm, instead of using a costly branch-and-bound method, incorporates a genetic algorithm to obtain "good" suboptimal solutions to the master problem at a tremendous saving in the computational effort. A classical capacitated plant location problem is used as an example to illustrate the implementation of the hybrid Benders' algorithm.