Benders decomposition, Lagrangean relaxation and metaheuristic design |
| |
Authors: | Marco Boschetti Vittorio Maniezzo |
| |
Affiliation: | (1) Department of Mathematics, University of Bologna, Bologna, Italy;(2) Department of Computer Science, University of Bologna, Bologna, Italy |
| |
Abstract: | Large part of combinatorial optimization research has been devoted to the study of exact methods leading to a number of very diversified solution approaches. Some of those older frameworks can now be revisited in a metaheuristic perspective, as they are quite general frameworks for dealing with optimization problems. In this work, we propose to investigate the possibility of reinterpreting decompositions, with special emphasis on the related Benders and Lagrangean relaxation techniques. We show how these techniques, whose heuristic effectiveness is already testified by a wide literature, can be framed as a “master process that guides and modifies the operations of subordinate heuristics”, i.e., as metaheuristics. Obvious advantages arise from these approaches, first of all the runtime evolution of both upper and lower bounds to the optimal solution cost, thus yielding both a high-quality heuristic solution and a runtime quality certificate of that same solution. |
| |
Keywords: | Combinatorial optimization Lagrangean relaxation Benders’ s decomposition Metaheuristic |
本文献已被 SpringerLink 等数据库收录! |
|