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.
Year of publication: |
2009
|
---|---|
Authors: | Poojari, C.A. ; Beasley, J.E. |
Published in: |
European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 199.2009, 1, p. 89-97
|
Publisher: |
Elsevier |
Keywords: | Genetic algorithm Benders decomposition Mixed-integer linear programs |
Saved in:
Saved in favorites
Similar items by person
-
Improving benders decomposition using a genetic algorithm
Poojari, C.A., (2009)
-
A tabu search algorithm for the single vehicle routing allocation problem
Vogt, L., (2007)
-
Lucas, C., (2001)
- More ...