Improving benders decomposition using a genetic algorithm

We develop and investigate the performance of a hybrid solution framework for solving mixed-integer linear programming problems. Benders decomposition and a genetic algorithm are combined to develop a framework to compute feasible solutions. We decompose the problem into a master problem and a subproblem. A genetic algorithm along with a heuristic are used to obtain feasible solutions to the master problem, whereas the subproblem is solved to optimality using a linear programming solver. Over successive iterations the master problem is refined by adding cutting planes that are implied by the subproblem. We compare the performance of the approach against a standard Benders decomposition approach as well as against a stand-alone solver (Cplex) on MIPLIB test problems.