Abstract
This paper presents a Population-based Strategic Oscillation (denoted by PBSO) algorithm for solving the linear ordering problem with cumulative costs (denoted by LOPCC). The proposed algorithm integrates several distinguished features, such as an adaptive strategic oscillation local search procedure and an effective population updating strategy. The proposed PBSO algorithm is compared with several state-of-the-art algorithms on a set of public instances up to 100 vertices, showing its efficacy in terms of both solution quality and efficiency. Moreover, several important ingredients of the PBSO algorithm are analyzed.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Lü, Z., Hao, J.K.: A memetic algorithm for graph coloring. European Journal of Operational Research 203(1), 241–250 (2010)
Lü, Z., Glover, F., Hao, J.K.: A hybrid metaheuristic approach to solving the UBQP Problem. European Journal of Operational Research 207(3), 1254–1262 (2010)
Benvenuto, N., Carnevale, N., Tomasin, S.: Optimum power control and ordering in SIC receivers for uplink CDMA systems. In: IEEE International Conference on Communications, ICC 4, pp. 2333–2337 (2005)
Bertacco, L., Brunetta, L., Fischetti, M.: The linear ordering problem with cumulative costs. European Journal of Operational Research 189(3), 1345–1357 (2005)
Duarte, A., Laguna, M., Marti, R.: Tabu search for the linear ordering problem with cumulative costs. Computational Optimization and Applications 48, 697–715 (2011)
Duarte, A., Marti, R., Alvarez, A., Angel-Bello, F.: Metaheuristics for the linear ordering problem with cumulative costs. European Journal of Operational Research 216(2), 270–277 (2012)
Villanueva, D.T., Huacuja, H.J.F., Duarte, A., Rodolfo Pazos, R., Valadez, J.M.C., Soberanes, H.J.P.: Improving Iterated Local Search Solution for the Linear Ordering Problem with Cumulative Costs (LOPCC). In: Setchi, R., Jordanov, I., Howlett, R.J., Jain, L.C. (eds.) KES 2010, Part II. LNCS (LNAI), vol. 6277, pp. 183–192. Springer, Heidelberg (2010)
Righini, G.: A branch-and bound algorithm for the linear ordering problem with cumulative costs. European Journal of Operational Research 186(3), 965–971 (2008)
Schiavinotto, T., Stützle, T.: The linear ordering problem: Instances, search space analysis and algorithms. European Journal of Operational Research 177, 2033–2049 (2007)
Glover, F., Hao, J.K.: The case for strategic oscillation. Annals OR 183(1), 163–173 (2011)
Ruiz, R., Stützle, T.: A simple and effective iterated greedy algorithm for the linear ordering problem with cumulative costs. European Journal of Operational Research 177, 2033–2049 (2007)
Reinelt, G., Hofmann, H.H., Wille, R.: The linear ordering problem: Algorithms and applications. Research and Exposition in Mathematics 8 (1985)
Laguna, M., Marti, R., Campos, V.: Intensification and diversification with elite tabu search solutions for the linear ordering problem. Computers & OR 26(12), 1217–1230 (1999)
Proakis, J.G.: Digital Comunnications, 4th edn. McGraw-Hill (2004)
Holma, H., Toskala, A.: WCDMA for UMTS: Radio access for Third generation mobile communications. Wiley, New York (2000)
Glover, F., Laguna, M.: General purpose heuristics for integer programming-part II. J. Heuristics 3(2), 161–179 (1997)
Glover, F.: Multi-start and strategic oscillation methods - Principles to exploit adaptive memory. In: Laguna, M., Gonzales Velarde, J.L. (eds.) Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, pp. 1–24 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Xiao, W., Chu, W., Lü, Z., Ye, T., Liu, G., Cui, S. (2013). A Population-Based Strategic Oscillation Algorithm for Linear Ordering Problem with Cumulative Costs. In: Middendorf, M., Blum, C. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2013. Lecture Notes in Computer Science, vol 7832. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-37198-1_5
Download citation
DOI: https://doi.org/10.1007/978-3-642-37198-1_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-37197-4
Online ISBN: 978-3-642-37198-1
eBook Packages: Computer ScienceComputer Science (R0)