Skip to main content
SpringerLink
Log in

Circulant weighing matrices: a demanding challenge for parallel optimization metaheuristics

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

Circulant weighing matrices constitute a special type of combinatorial matrices that have attracted scientific interest for many years. The existence and determination of specific classes of circulant weighing matrices remains an active research area that involves both theoretical algebraic techniques as well as high-performance computational optimization approaches. The present work aims at investigating the potential of four established parallel metaheuristics as well as a special Algorithm Portfolio approach, on solving such problems. For this purpose, the algorithms are applied on a hard circulant weighing matrix existence problem. The obtained results are promising, offering insightful conclusions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1

Similar content being viewed by others

References

  1. Alba, E.: Parallel Metaheuristics: A New Class of Algorithms. Wiley, London (2005)

    Book  MATH  Google Scholar 

  2. Ang, M., Arasu, K., Ma, S., Strassler, Y.: Study of proper circulant weighing matrices with weigh 9. Discrete Math. 308, 2802–2809 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  3. Arasu, K., Dillon, J., Jungnickel, D., Pott, A.: The solution of the waterloo problem. J. Comb. Theory Ser. A 71, 316–331 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  4. Arasu, K., Gulliver, T.: Self-dual codes over fp and weighing matrices. IEEE Trans. Inf. Theory 47(5), 2051–2055 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  5. Arasu, K., Gutman, A.: Circulant weighing matrices. Cryptogr. Commun. 2, 155–171 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  6. Arasu, K., Leung, K., Ma, S., Nabavi, A., Ray-Chaudhuri, D.: Determination of all possible orders of weight 16 circulant weighing matrices. Finite Fields Appl. 12, 498–538 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chiarandini, M., Kotsireas, I., Koukouvinos, C., Paquete, L.: Heuristic algorithms for hadamard matrices with two circulant cores. Theor. Comput. Sci. 407(1–3), 274–277 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  8. Cousineau, J., Kotsireas, I., Koukouvinos, C.: Genetic algorithms for orthogonal designs. Australas. J. Comb. 35, 263–272 (2006)

    MathSciNet  MATH  Google Scholar 

  9. van Dam, W.: Quantum algorithms for weighing matrices and quadratic residues. Algorithmica 34, 413–428 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  10. Eades, P.: On the existence of orthogonal designs. Ph.D. thesis, Australian National University, Canberra (1997)

  11. Eades, P., Hain, R.: On circulant weighing matrices. Ars Comb. 2, 265–284 (1976)

    MathSciNet  MATH  Google Scholar 

  12. Eberhart, R.C., Kennedy, J.: A new optimizer using particle swarm theory. In: Proceedings Sixth Symposium on Micro Machine and Human Science, pp. 39–43. Piscataway, NJ (1995)

  13. Geramita, A., Sebery, J.: Orthogonical designs: quadratic forms and hadamard matrices. Lecture Notes in Pure and Applied Mathematics (1979)

  14. Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533–549 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  15. Gomes, C.P., Selman, B.: Algorithm portfolio design: theory vs. practice. In: Proceedings Thirteenth conference on Uncertainty in artificial intelligence, pp. 190–197 (1997)

  16. Hansen, P., Mladenović, N., Brimberg, J., Moreno Pérez, J.A.: Variable neighborhood search. In: M. Gendreau, J.Y. Potvin (eds.) Handbook of Metaheuristics, vol. 146, chap. 3. Springer, Berlin (2010)

  17. Huberman, B.A., Lukose, R.M., Hogg, T.: An economics approach to hard computational problems. Science 27, 51–53 (1997)

    Article  Google Scholar 

  18. Kotsireas, I.: Algorithms and metaheuristics for combinatorial matrices. In: P. Pardalos, D.Z. Du, R.L. Graham (eds.) Handbook of Combinatorial Optimization, pp. 283–309. Springer, New York (2013)

  19. Kotsireas, I., Koukouvinos, C., Pardalos, P., Shylo, O.: Periodic complementary binary sequences and combinatorial optimization algorithms. J. Combin. Optim. 20(1), 63–75 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  20. Kotsireas, I., Koukouvinos, C., Pardalos, P., Simos, D.: Competent genetic algorithms for weighing matrices. J. Combin. Optim. 24(4), 508–525 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  21. Kotsireas, I., Parsopoulos, K., Piperagkas, G., Vrahatis, M.: Ant-based approaches for solving autocorrelation problems. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7461 LNCS, pp. 220–227 (2012)

  22. Koukouvinos, C., Seberry, J.: Weighing matrices and their applications. J. Stat. Plan. Inference 62(1), 91–101 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  23. Mladenovic, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  24. Parsopoulos, K.E., Vrahatis, M.N.: Particle Swarm Optimization and Intelligence: Advances and Applications. Information Science Publishing (IGI Global), Hershey, USA (2010)

  25. Peng, F., Tang, K., Chen, G., Yao, X.: Population-based algorithm portfolios for numerical optimization. IEEE Trans. Evol. Comput. 14(5), 782–800 (2010)

    Article  Google Scholar 

  26. Ribeiro, C., Resende, M.: Path-relinking intensification methods for stochastic local search algorithms. J. Heuristics 18(2), 193–214 (2012)

    Article  Google Scholar 

  27. Schmidt, B., Smith, K.W.: Circulant weighing matrices whose order and weight are products of powers of 2 and 3. J. Comb. Theory Ser. A 120(1), 275–287 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  28. Seberry, J., Whiteman, A.: Some results on weighing matrices. Bull. Aust. Math. Soc. 12, 433–447 (1975)

    Article  MathSciNet  MATH  Google Scholar 

  29. Souravlias, D., Parsopoulos, K.E., Alba, E.: Parallel algorithm portfolio with market trading-based time allocation. In: Proceedings International Conference on Operations Research 2014 (OR2014) (2014)

  30. Storn, R., Price, K.: Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. J. Glob. Optim. 11(4), 341–359 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  31. Strassler, Y.: The classification of circulant weighing matrices of weight 9. Ph.D. thesis, Bar-Ilan University (1997)

  32. Tang, K., Peng, F., Chen, G., Yao, X.: Population-based algorithm portfolios with automated constituent algorithms selection. Inf. Sci. 279, 94–104 (2014)

    Article  Google Scholar 

  33. Tasgetiren, F., Chen, A., Gencyilmaz, G., Gattoufi, S.: Smallest position value approach. Stud. Comput. Intel. 175, 121–138 (2009)

    MATH  Google Scholar 

  34. Yevseyeva, I., Guerreiro, A.P., Emmerich, M.T.M., Fonseca, C.M.: A portfolio optimization approach to selection in multiobjective evolutionary algorithms. Proc. PPSN 2014, 672–681 (2014)

    Google Scholar 

Download references

Acknowledgments

The authors would like to thank the Shared Hierarchical Academic Research Computing Network (SHARCNET) as well as the WestGrid HPC consortium for offering the necessary computational resources.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, University of Ioannina, 45110, Ioannina, Greece

    D. Souravlias & K. E. Parsopoulos

  2. Department of Physics and Computer Science, Wilfrid Laurier University, Waterloo, ON, Canada

    I. S. Kotsireas

Authors
  1. D. Souravlias
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. K. E. Parsopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. I. S. Kotsireas
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to I. S. Kotsireas.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Souravlias, D., Parsopoulos, K.E. & Kotsireas, I.S. Circulant weighing matrices: a demanding challenge for parallel optimization metaheuristics. Optim Lett 10, 1303–1314 (2016). https://doi.org/10.1007/s11590-015-0927-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-015-0927-y

Keywords

Search

Navigation