PDF EndNote BibTex Cite

Year 2019, Volume 9, Issue 4, 724 - 734, 01.12.2019

Abstract

References

  • Babayev, D. A., Bell, G. I. and Nuriyev, U. G., (2009), The Bandpass Problem: Combinatorial Optimization and Library of Problems, Journal of Combinatorial Optimization, 18, pp. 151-172.
  • Chen, Z. Z. and Wang, L., (2012), An improved approximation algorithm for the bandpass-2 prob- lem, In Proceedings of the 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012), LNCS, 7402, 185-196.
  • Dorigo, M., (1992), Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Mi- lano.
  • Gen M., (2006), Genetic Algorithms and Their Applications, in Springer Handbook of Engineering Statistics (eds. P. Hoang), pp. 749-773.
  • Goralski, W. J., (1997), SONET, a Guide to Synchronous Optical Networks, McGraw-Hill, New York. [6] Gursoy, A., Tekin, A., Keserlioglu, S., Kutucu, H., Kurt M. and Nuriyev, U., (2017), An improved binary integer programming model of the Band Collocation problem, Journal of Modern Technology and Engineering, 2(1), pp. 34-42.
  • Holland, J. H., (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press.
  • Huang, L., Tong, W., Goebel, R., Liu, T. and Lin, G., (2015), A 0.5358-Approximation for Bandpass-2, Journal of Combinatorial Optimization, 30, pp. 612-626.
  • Kennedy, J. and Eberhart, R. C., (1985), Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks, 4, pp. 1942-1948.
  • Kirkpatrick, S., Gelatt Jr, C.D. and Vecchi, M.P., (1983), Optimization by Simulated Annealing, Science, 220, pp. 671-680.
  • Laguna, M., Sanchez-Oro, J., Marti, R. and Duarte, A., (2015), Scatter Search for the Bandpass Problem, 27th European Conference on Operational Research, July.
  • Li, Z. and Lin, G., (2011), The Three Column Bandpass Problem is Solvable in Linear Time, Theor. Comput. Sci., 412, pp. 281-299.
  • Nuriyev, U., Kutucu, H., Kurt, M. and Gursoy, A., (2015), The Band Collocation Problem in Telecom- munication Networks, Book of Abstracts of the 5th International Conference on Control and Opti- mization with Industrial Applications, pp. 362-365, Baku, Azerbaijan, August 27-29.
  • Nuriyev, U., Kurt, M., Kutucu, H. and Gursoy A., (2015), The Band Collocation Problem and Its Combinatorial Model, Abstract Book of the International Conference Matematical and Computational Modelling in Science and Technology, pp. 140-142, Izmir, Turkey, August 02-07.
  • Nuriyev U., Kurt M., Kutucu, H. and Gursoy, A., (2015), Band Collocation Problem Online Library (BCPLib): http://fen.ege.edu.tr/ arifgursoy/bps/, (2015) (LAD: December 6, 2017).
  • Nuriyeva, F., (2016), On a generalized sequential partially covering problem, Appl. Comput. Math., 15(2), pp. 239-242.
  • Ramaswami, R., Sivarajan, K. and Sasaki, G., (1998), Optical Networks: A Practical Perspective. Morgan Kaufmann, San Francisco.
  • Tong, W., Goebel, R., Liu, T. and Lin, G., (2014) Approximation Algorithms for the Maximum Multiple RNA Interaction Problem, Theoretical Computer Science, 556, pp. 63–70.

ON THE SOLUTION APPROACHES OF THE BAND COLLOCATION PROBLEM

Year 2019, Volume 9, Issue 4, 724 - 734, 01.12.2019

Abstract

This paper introduces the rst genetic algorithm approach for solving the Band Collocation Problem BCP which is a combinatorial optimization problem that aims to reduce the hardware costs on ber optic networks. This problem consists of nding an optimal permutation of rows of a given binary rectangular matrix representing a communication network so that the total cost of covering all 1's by Bands is minimum. We present computational results which indicate that we can obtain almost optimal solutions of moderately large size instances up to 96 rows and 28 columns of the BCP within a few seconds.

References

  • Babayev, D. A., Bell, G. I. and Nuriyev, U. G., (2009), The Bandpass Problem: Combinatorial Optimization and Library of Problems, Journal of Combinatorial Optimization, 18, pp. 151-172.
  • Chen, Z. Z. and Wang, L., (2012), An improved approximation algorithm for the bandpass-2 prob- lem, In Proceedings of the 6th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2012), LNCS, 7402, 185-196.
  • Dorigo, M., (1992), Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Mi- lano.
  • Gen M., (2006), Genetic Algorithms and Their Applications, in Springer Handbook of Engineering Statistics (eds. P. Hoang), pp. 749-773.
  • Goralski, W. J., (1997), SONET, a Guide to Synchronous Optical Networks, McGraw-Hill, New York. [6] Gursoy, A., Tekin, A., Keserlioglu, S., Kutucu, H., Kurt M. and Nuriyev, U., (2017), An improved binary integer programming model of the Band Collocation problem, Journal of Modern Technology and Engineering, 2(1), pp. 34-42.
  • Holland, J. H., (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press.
  • Huang, L., Tong, W., Goebel, R., Liu, T. and Lin, G., (2015), A 0.5358-Approximation for Bandpass-2, Journal of Combinatorial Optimization, 30, pp. 612-626.
  • Kennedy, J. and Eberhart, R. C., (1985), Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks, 4, pp. 1942-1948.
  • Kirkpatrick, S., Gelatt Jr, C.D. and Vecchi, M.P., (1983), Optimization by Simulated Annealing, Science, 220, pp. 671-680.
  • Laguna, M., Sanchez-Oro, J., Marti, R. and Duarte, A., (2015), Scatter Search for the Bandpass Problem, 27th European Conference on Operational Research, July.
  • Li, Z. and Lin, G., (2011), The Three Column Bandpass Problem is Solvable in Linear Time, Theor. Comput. Sci., 412, pp. 281-299.
  • Nuriyev, U., Kutucu, H., Kurt, M. and Gursoy, A., (2015), The Band Collocation Problem in Telecom- munication Networks, Book of Abstracts of the 5th International Conference on Control and Opti- mization with Industrial Applications, pp. 362-365, Baku, Azerbaijan, August 27-29.
  • Nuriyev, U., Kurt, M., Kutucu, H. and Gursoy A., (2015), The Band Collocation Problem and Its Combinatorial Model, Abstract Book of the International Conference Matematical and Computational Modelling in Science and Technology, pp. 140-142, Izmir, Turkey, August 02-07.
  • Nuriyev U., Kurt M., Kutucu, H. and Gursoy, A., (2015), Band Collocation Problem Online Library (BCPLib): http://fen.ege.edu.tr/ arifgursoy/bps/, (2015) (LAD: December 6, 2017).
  • Nuriyeva, F., (2016), On a generalized sequential partially covering problem, Appl. Comput. Math., 15(2), pp. 239-242.
  • Ramaswami, R., Sivarajan, K. and Sasaki, G., (1998), Optical Networks: A Practical Perspective. Morgan Kaufmann, San Francisco.
  • Tong, W., Goebel, R., Liu, T. and Lin, G., (2014) Approximation Algorithms for the Maximum Multiple RNA Interaction Problem, Theoretical Computer Science, 556, pp. 63–70.

Details

Primary Language English
Journal Section Research Article
Authors

H. KUTUCU This is me
Department of Computer Engineering, Karabuk University, Karabuk, Turkey


A. GURSOY This is me
Corresponding Author, Department of Mathematics, Ege University, Izmir, Turkey.


M. KURT This is me
Faculty of Engineering and Natural Sciences, Bahcesehir University, Istanbul, Turkey.


U. NURİYEV This is me
Department of Mathematics, Ege University, Izmir, Turkey.

Publication Date December 1, 2019
Published in Issue Year 2019, Volume 9, Issue 4

Cite

Bibtex @ { twmsjaem760940, journal = {TWMS Journal of Applied and Engineering Mathematics}, issn = {2146-1147}, eissn = {2587-1013}, address = {Işık University ŞİLE KAMPÜSÜ Meşrutiyet Mahallesi, Üniversite Sokak No:2 Şile / İstanbul}, publisher = {Turkic World Mathematical Society}, year = {2019}, volume = {9}, number = {4}, pages = {724 - 734}, title = {ON THE SOLUTION APPROACHES OF THE BAND COLLOCATION PROBLEM}, key = {cite}, author = {Kutucu, H. and Gursoy, A. and Kurt, M. and Nuriyev, U.} }