Abstract
We propose a new metaheuristic framework embodied in two approaches, Relaxation Adaptive Memory Programming (RAMP) and its primal-dual extension (PD-RAMP). The RAMP method, at the first level, operates by combining fundamental principles of mathematical relaxation with those of adaptive memory programming, as expressed in tabu search. The extended PD- RAMP method, at the second level, integrates the RAMP approach with other more advanced strategies. We identify specific combinations of such strategies at both levels, based on Lagrangean and surrogate constraint relaxation on the dual side and on scatter search and path relinking on the primal side, in each instance joined with appropriate guidance from adaptive memory processes. The framework invites the use of alternative procedures for both its primal and dual components, including other forms of relaxations and evolutionary approaches such as genetic algorithms and other procedures based on metaphors of nature.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Duarte, R., C. Rego and D. Gamboa (2004) “A Filter and Fan Approach for the Job Shop Scheduling Problem: A Preliminary Study,” in Proceedings: International Conference on Knowledge Engineering and Decision Support, 401–406.
Glover, F. (1965) “A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem,” Operations Research, 13:879–919.
Glover, F. (1968) “Surrogate Constraints,” Operations Research, 16(4):741–749.
Glover, F. (1975) “Surrogate Constraint Duality in Mathematical Programming,” Operations Research, 23(3):434–451.
Glover, F. (1997) “A Template for Scatter Search and Path Relinking,” in Lecture Notes in Computer Science, 1363, J.K. Hao, E. Lutton, E. Ronald, M. Schoenauer, D. Snyers (Eds.), 13–54.
Greenberg, H.J. and W.P. Pierskalla (1970) “Surrogate Mathematical Proramming,” Operations Research, 18:1138–1162.
Greistorfer, P., C. Rego and B. Alidaee “Simple Filter-and-Fan Approach for the Facility Location Problem,” Research Report, Hearin Center for Enterprise Science, School of Business Administration, University of Mississippi, USA.
Held, M., P. Wolfe and H.P. Crowder (1975) “Validation of Subgradient Optimization,” Mathematical Programming, 6:62–88.
Lorena, L.A.N. and M.G. Narciso (1999) “Lagrangean/Surrogate Relaxations for the Generalized Assignment Problems,” European Journal of Operational Research, 114(1): 165–177.
Lorena, L.A.N. and F.B. Lopes (1994) “A Surrogate Heuristic for Set Covering Problems,” European Journal of Operational Research, 79:138–150.
Martello, S., D. Pisinger and P. Toth (2000), “New Trends in Exact Algorithms for the 0-1 Knapsack Pproblem,” European Journal of Operational Research, 123:325–332.
Pisinger, D. (1999a) “Core problems in Knapsack Algorithms,” Operations Research, 47:570–575.
Pisinger, D. (1999b) “An Exact Algorithm for Large Multiple Knapsack Problems”, European Journal of Operational Research, 114:528–541.
Pisinger, D. (2004) “Where are the hard knapsack problems?,” Computers and Operations Research, to appear.
Poljak, B.T. (1969) “Minimization of Unsmooth Functionals,” USSR Computational Mathematics and Mathematical Physics, 9:14–29.
Rego, C. and F. Glover (2002) “Local Search and Metaheuristics for the Traveling Salesman Problem,” in book The Traveling Salesman Problem and its Variations, G. Gutin and A. Punnen Editors, Kluwer Academic Publishers, 309–368.
Rego, C., H. Li, and F. Glover (2004) “Adaptive and Dynamic Search Neighborhoods for Protein Folding in a 2D-HP Lattice Model”, Research Report, Hearin Center for Enterprise Science, School of Business Administration, University of Mississippi, USA.
Rego, C., L. Sagbansua, B. Alidaee, and F. Glover (2004) “RAMP and Primal-Dual RAMP Algorithms for the Multi-Resource Generalized Assignment Problem,” Research Report, Hearin Center for Enterprise Science, School of Business Administration, University of Mississippi, USA.
Yagiura, M., T. Ibaraki, and F. Glover (2004a) “A Path Relinking Approach with Ejection Chains for the Generalized Assignment Problem,” European Journal of Operational Research, to appear.
Yagiura, M., T. Ibaraki and F. Glover (2004b) “An Ejection Chain Approach for the Generalized Assignment Problem,” INFORMS Journal on Computing, 16(2):133–151.
Yagiura, M., S. Iwasaki, T. Ibaraki and F. Glover (2004) “A Very Large-Scale Neighborhood Search Algorithm for the Multi-Resource Generalized Assignment Problem,” Discrete Optimization, 1:87–98.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Kluwer Academic Publishers
About this chapter
Cite this chapter
Rego, C. (2005). RAMP: A New Metaheuristic Framework for Combinatorial Optimization. In: Sharda, R., Voß, S., Rego, C., Alidaee, B. (eds) Metaheuristic Optimization via Memory and Evolution. Operations Research/Computer Science Interfaces Series, vol 30. Springer, Boston, MA. https://doi.org/10.1007/0-387-23667-8_20
Download citation
DOI: https://doi.org/10.1007/0-387-23667-8_20
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4020-8134-7
Online ISBN: 978-0-387-23667-4
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)