Improving Benders decomposition using a genetic algorithm. (English) Zbl 1176.90428
Summary: 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.
References:
| [1] | Achterberg, T.; Berthold, T., Improving the feasibility pump, Discrete Optimization, 4, 77-86 (2007) · Zbl 1170.90443 |
| [2] | Barbosa, H. J.C.; Lemonge, A. C.C., A new adaptive penalty scheme for genetic algorithms, Information Sciences, 156, 3-4, 215-251 (2003) |
| [3] | Beasley, J. E., Population heuristics, (Pardalos, P. M.; Resende, M. G.C., Handbook of Applied Optimization (2002), Oxford University Press), 138-157 · Zbl 0996.90001 |
| [4] | Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 238-252 (1962) · Zbl 0109.38302 |
| [5] | Bertacco, L.; Fischetti, M.; Lodi, A., A feasibility pump heuristic for general mixed-integer problems, Discrete Optimization, 4, 63-76 (2007) · Zbl 1169.90415 |
| [6] | Chu, P. C.; Beasley, J. E., Constraint handling in genetic algorithms: the set partitioning problem, Journal of Heuristics, 4, 323-357 (1998) · Zbl 1071.90573 |
| [7] | Costa, L.; Oliveira, P., Evolutionary algorithms approach to the solution of mixed-integer non-linear programming problems, Computers & Chemical Engineering, 25, 2-3, 257-266 (2001) |
| [8] | Cote, G.; Laughton, M. A., Large-scale mixed integer programming: Benders-type heuristics, European Journal of Operational Research, 16, 3, 327-333 (1984) · Zbl 0532.90077 |
| [9] | Deb, K., An efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering, 186, 2-4, 311-338 (2000) · Zbl 1028.90533 |
| [10] | Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Mathematical Programming, 104, 1, 91-104 (2005) · Zbl 1077.90039 |
| [11] | Fischetti, M., Salvagnin, D., Zanette, A. Minimal Infeasible Subsystems and Benders Cuts. DEI, University of Padova (submitted to Mathematical Programming). <http://www.dei.unipd.it/ fisch/papers/Benders.pdf>; Fischetti, M., Salvagnin, D., Zanette, A. Minimal Infeasible Subsystems and Benders Cuts. DEI, University of Padova (submitted to Mathematical Programming). <http://www.dei.unipd.it/ fisch/papers/Benders.pdf> |
| [12] | Homaifar, A.; Qi, C. X.; Lai, S. H., Constrained optimization via genetic algorithm, Simulation, 62, 4, 242-253 (1994) |
| [13] | ILOG, 2006. <www.ilog.com>; ILOG, 2006. <www.ilog.com> |
| [14] | Michalewicz, Z., Attia, N., 1994. Evolutionary optimisation of constrained problems. In: Sebald, A.V., Fogel, L.J. (Eds.), Proceedings of the 3rd Annual Conference on Evolutionary Programming, World Scientific Publishing, River Edge, NJ, USA, pp. 98-108.; Michalewicz, Z., Attia, N., 1994. Evolutionary optimisation of constrained problems. In: Sebald, A.V., Fogel, L.J. (Eds.), Proceedings of the 3rd Annual Conference on Evolutionary Programming, World Scientific Publishing, River Edge, NJ, USA, pp. 98-108. |
| [15] | Nieminen, K., Ruuth, S., Maros, I., 2003, Genetic algorithm for finding a good first integer solution for MILP. Department of Computing, Imperial College, Departmental Technical Reports 2003/4. <http://www.doc.ic.ac.uk/research/technicalreports/2003/DTR03-4.pdf>; Nieminen, K., Ruuth, S., Maros, I., 2003, Genetic algorithm for finding a good first integer solution for MILP. Department of Computing, Imperial College, Departmental Technical Reports 2003/4. <http://www.doc.ic.ac.uk/research/technicalreports/2003/DTR03-4.pdf> |
| [16] | Poojari, C. A.; Varghese, B., Genetic algorithm based technique for solving chance constrained problems, European Journal of Operational Research, 185, 3, 1128-1154 (2008) · Zbl 1146.90536 |
| [17] | Puchinger, J., Raidl, G.R., 2005. Combining metaheuristics and exact algorithms in combinatorial optimization: a survey and classification. In: First International Work-Conference on the Interplay Between Natural and Artificial Computation. Lecture Notes in Computer Science, vol. 3562. Springer, pp. 41-53.; Puchinger, J., Raidl, G.R., 2005. Combining metaheuristics and exact algorithms in combinatorial optimization: a survey and classification. In: First International Work-Conference on the Interplay Between Natural and Artificial Computation. Lecture Notes in Computer Science, vol. 3562. Springer, pp. 41-53. |
| [18] | Raidl, G.R., Puchinger, J., 2008. Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization. In: Blum, C., Blesa Aguilera, M.J., Roli, A., Sampels, M. (Eds.), Hybrid Metaheuristics, An Emerging Approach to Optimization. Series: Studies in Computational Intelligence, vol. 114, pp. 31-62.; Raidl, G.R., Puchinger, J., 2008. Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization. In: Blum, C., Blesa Aguilera, M.J., Roli, A., Sampels, M. (Eds.), Hybrid Metaheuristics, An Emerging Approach to Optimization. Series: Studies in Computational Intelligence, vol. 114, pp. 31-62. · Zbl 1415.90054 |
| [19] | Reeves, C. R., Genetic algorithms for the operations researcher, INFORMS Journal on Computing, 9, 231-250 (1997) · Zbl 0893.90145 |
| [20] | Rei, W., Gendreau, M., Cordeau, J.-F., Soriano, P., 2006. Accelerating Benders decomposition by local branching. INFORMS Journal on Computing, in press. doi:10.1287/ijoc.1080.0296.; Rei, W., Gendreau, M., Cordeau, J.-F., Soriano, P., 2006. Accelerating Benders decomposition by local branching. INFORMS Journal on Computing, in press. doi:10.1287/ijoc.1080.0296. · Zbl 1243.90122 |
| [21] | Sastry, K.; Goldberg, D.; Kendall, G., Genetic algorithms, (Burke, E. K.; Kendall, G., Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (2005), Springer), 97-125 · Zbl 1140.90015 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
