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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Agar, M., Salhi, S.: Lagrangean heuristics applied to a variety of large capacitated plant location problems. J. Oper. Res. Soc. 49, 1072–1084 (1998)
Ahuja, R.K., Orlin, J.B., Pallottino, S., Scaparra, M.P., Scutellà, M.G.: A multi-exchange heuristic for the single source capacitated facility location problem. Manag. Sci. 50 (2003)
Barahona, F., Anbil, R.: The volume algorithm: producing primal solutions with a subgradient method. Math. Program. 87, 385–399 (2000)
Barcelo, J., Casanova, J.: A heuristic Lagrangean algorithm for the capacitated plant location problem. Eur. J. Oper. Res. 15, 212–226 (1984)
Beasley, J.E.: Lagrangean relaxation. In: Reeves, C.R. (ed.) Modern Heuristic Techniques for Combinatorial Problems, pp. 243–303. Blackwell Scientific, Oxford (1993)
Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4, 280–322 (1962)
Boschetti, M.A., Jelasity, M., Maniezzo, V.: A local approach to membership overlay design. Working paper, Department of Computer Science, University of Bologna (2006)
Bouleimen, K., Lecocq, H.: A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem. In: Barbarosoglu, G., Karabati, S., Ozdamar, L., Ulusoy, G. (eds.) Proceedings of the Sixth International Workshop on Project Management and Scheduling, pp. 1922. Bogazici University (1998)
Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for a capacitated facility location problem. In: Proc. 10th Annu. ACM-SIAM Sympos. Discrete Algorithms, pp. S875–S876 (1999)
Delmaire, H., Diaz, J.A., Fernandez, E., Ortega, M.: Reactive grasp and tabu search based heuristics for the single source capacitated plant location problem. INFOR 37, 194–225 (1999)
Drexl, A., Grunewald, J.: Nonpreemptive multi-mode resource-constrained project scheduling. IIE Trans. 25(5), 74–81 (1993)
Elmaghraby, S.E.: Activity Networks: Project Planning and Control by network Models. Wiley, New York (1977)
Ganesh, A.J., Kermarrec, A.-M., Massoulié, L.: Peer-to-peer membership management for gossip-based protocols. IEEE Trans. Comput. 52(2) (February 2003)
Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13, 533–549 (1986)
Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Boston (1997)
Hartmann, S.: Project scheduling with multiple modes: a genetic algorithm. Ann. Oper. Res. 102, 111–135 (2001)
Holmberg, K., Ronnqvist, M., Yuan, D.: An exact algorithm for the capacitated facility location problems with single sourcing. Eur. J. Oper. Res. 113, 544–559 (1999)
Holt, J., Ronnqvist, M., Tragantalerngsak, S.: A repeated matching heuristic for the single source capacitated facility location problem. Eur. J. Oper. Res. 116, 51–68 (1999)
Jozefowska, J., Mika, M., Royzycki, R., Waligora, G., Weglarz, J.: Simulated annealing for multi-mode resource-constrained project scheduling. Ann. Oper. Res. 102, 137–155 (2001)
Klincewicz, J., Luss, H.: A Lagrangean relaxation heuristic for capacitated facility location with single-source constraints. J. Oper. Res. Soc. 37, 495–500 (1986)
Kolisch, R., Drexl, A.: Local search for nonpreemptive multi-mode resource constrained project scheduling. Technical Report 360, Institut fr Betriebswirtschaftslehre, Christian-Albrechts-Universitt zu Kiel, Kiel (1994)
Kolisch, R., Sprecher, A., Drexl, A.: Characterization and generation of a general class of resource constrained project scheduling problems. Manag. Sci. 41, 1693–1703 (1995)
Maniezzo, V., Mingozzi, A.: A heuristic procedure for the multi-mode project scheduling problem based on benders decomposition. In: Weglarz, J. (ed.) Project Scheduling: Recent Models, Algorithms and Applications, pp. 179–196. Kluwer Academic, Dordrecht (1999)
Maniezzo, V., Boschetti, M.A., Jelasity, M.: An ant approach to membership overlay design. In: Ant Colony, Optimization and Swarm Intelligence: Proc. ANTS 2004. Lecture Notes in Computer Science, vol. 3172, p. 3748. Springer, Berlin (2004)
Maniezzo, V., Boschetti, M.A., Jelasity, M.: A fully distributed Lagrangean metaheuristic for a P2P overlay network design problem. In: Proceedings of the 6th Metaheuristics International Conference (MIC 2005), Vienna, Austria (2005)
Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990)
Mingozzi, A., Maniezzo, V., Ricciardelli, S., Bianco, L.: An exact algorithm for the resource constrained project scheduling problem based on a new mathematical formulation. Manag. Sci. 44, 715–729 (1998)
Neebe, A., Rao, M.: An algorithm for the fixed-charge assigning users to sources problem. J. Oper. Res. Soc. 34, 1107–1113 (1983)
Peersim: A peer-to-peer simulator, http://peersim.sourceforge.net/ (2006)
Pirkul, H.: Efficient algorithm for the capacitated concentrator location problem. Comput. Oper. Res. 14, 197–208 (1987)
Planetlab: An open platform for developing, deploying, and accessing planetary-scale services, http://www.planet-lab.org/ (2006)
Polyak, B.T.: Minimization of unsmooth functionals. USSR Comput. Math. Phys. 9, 14–29 (1969)
Saroiu, S., Krishna Gummadi, P., Gribble, S.D.: A measurement study of peer-to-peer file sharing systems. In: Proceedings of Multimedia Computing and Networking 2002 (MMCN’02), San Jose, CA (2002)
Sherali, H.D., Choi, G.: Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of liner programs. Oper. Res. Lett. 19, 105–113 (1996)
Solomon, M.: Algorithms for the vehicle routing and scheduling problem with time window constraints. Oper. Res. 35, 254–365 (1987)
Sprecher, A., Drexl, A.: Solving multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm. Eur. J. Oper. Res. 107, 431–450 (1998)
Sridharan, R.: A Lagrangian heuristic for the capacitated plant location problem with single source constraints. Eur. J. Oper. Res. 66, 305–312 (1991)
Talbot, B.: Resource-constrained project scheduling with time-resource tradeoffs: the nonpreemptive case. Manag. Sci. 28, 1197–1210 (1982)
Ulusoy, G., Ozdamar, L.: A constraint-based perspective in resource constrained project scheduling. Int. J. Prod. Res. 32, 693–705 (1994)
van Roy, T.J.: A cross decomposition algorithm for capacitated facility location. Oper. Res. 34(1), 145–163 (1986)
Voss, S.: Meta-heuristics: The state of the art. In: Nareyek, A. (ed.) Local Search for Planning and Scheduling. LNAI, vol. 2148, pp. 1–23. Springer, Berlin (2001)
Zhang, H., Tam, C.M., Li, H.: Multimode project scheduling based on particle swarm optimization. Comput. Aided Civ. Infrastruct. Eng. 21, 93–103 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Boschetti, M., Maniezzo, V. Benders decomposition, Lagrangean relaxation and metaheuristic design. J Heuristics 15, 283–312 (2009). https://doi.org/10.1007/s10732-007-9064-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10732-007-9064-9