Accelerating benders decomposition: multiple cuts via multiple solutions
| Autor: | N. Beheshti Asl, S. A. MirHassani |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
021103 operations research Control and Optimization Series (mathematics) Computer science Applied Mathematics 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology Benders' decomposition 01 natural sciences Facility location problem Computer Science Applications Reduction (complexity) Computational Theory and Mathematics 010201 computation theory & mathematics Theory of computation Discrete Mathematics and Combinatorics Slow convergence |
| Zdroj: | Journal of Combinatorial Optimization. 37:806-826 |
| ISSN: | 1573-2886 1382-6905 |
| DOI: | 10.1007/s10878-018-0320-8 |
| Popis: | Benders decomposition (BD) is a well-known approach that has been successfully applied to various mathematical programming problems. According to previous studies, slow convergence is the main drawback of this method. In this paper, multi-solution of the master problem has been applied to accelerate the BD algorithm and improve both lower and upper bounds by simultaneously adding multiple feasibility and optimality cuts. A novel integration of Benders cuts was used to prevent the growth of master problem. Computational experiments were applied to a series of logistics facility location problems. Our numerical experiments resulted in a 61% decrease in the total number of iterations and up to 73% reduction in the solution time, confirming the outstanding performance of the proposed method. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink