Skip to main content
SpringerLink
Log in

A black-box scatter search for optimization problems with integer variables

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

The goal of this work is the development of a black-box solver based on the scatter search methodology. In particular, we seek a solver capable of obtaining high quality outcomes to optimization problems for which solutions are represented as a vector of integer values. We refer to these problems as integer optimization problems. We assume that the decision variables are bounded and that there may be constraints that require that the black-box evaluator is called in order to know whether they are satisfied. Problems of this type are common in operational research areas of applications such as telecommunications, project management, engineering design and the like.Our experimental testing includes 171 instances within four classes of problems taken from the literature. The experiments compare the performance of the proposed method with both the best context-specific procedures designed for each class of problem as well as context-independent commercial software. The experiments show that the proposed solution method competes well against commercial software and that can be competitive with specialized procedures in some problem classes.

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.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

References

  1. April, J., Better, M., Glover, F., Kelly, J.P., Laguna, M.: Enhancing Business Process Management with Simulation Optimization. BPTrends, 1–11 (2005)

  2. Baños, R., Gil, C., Agulleiro, J.I., Reca, J.: A memetic algorithm for water distribution network design. In: Saad, A., Avineri, E., Dahal, K., Sarfraz, M., Roy, R. (eds.) Soft Computing in Industrial Applications: Recent and Emerging Methods and Techniques, pp. 279–289. Springer, Berlin (2007)

    Chapter  Google Scholar 

  3. Bean, J.C.: Genetic algorithms and random keys for sequencing and optimization. INFORMS J. Comput. 6(2), 154–160 (1994)

    Article  Google Scholar 

  4. Campos, V., Laguna, M., Martí, R.: Context-independent scatter and Tabu search for permutation problems. INFORMS J. Comput. 17(1), 111–122 (2005)

    Article  Google Scholar 

  5. Chen, C.-C.: Placement and Partitioning Methods for Integrated Circuit Layout. University of California, Berkeley (1986)

    Google Scholar 

  6. Dolezal, O., Hofmeister, T., Lefmann, H.: A Comparison of Approximation Algorithms for the MaxCut-Problem. Universität Dortmund, (1999)

  7. Duarte, A., Glover, F., Martí, R., Gortázar, F.: Hybrid scatter Tabu search for unconstrained global optimization. Ann. Oper. Res. 183, 95–123 (2011)

    Article  Google Scholar 

  8. Duarte, A., Martí, R., Gortázar, F.: Path relinking for large scale global optimization. Soft Comput. 15, 2257–2273 (2011)

    Article  Google Scholar 

  9. Feo, T.A., Khellaf, M.: A class of bounded approximation algorithms for graph partitioning. Networks 20, 181–195 (1990)

    Article  Google Scholar 

  10. Fujiwara, O., Khang, D.B.: A two-phase decomposition method for optimal design of looped water distribution networks. Water Resour. Res. 26(4), 539–549 (1987)

    Article  Google Scholar 

  11. Gallego, M., Laguna, M., Martí, R., Duarte, A.: Tabu search with Strategic Oscillation for the maximally diverse grouping problem. J. Oper. Res. Soc. doi:10.1057/jors.2012.66 (2011)

  12. Glover, F.: Tabu search and adaptive memory programing—advances, applications and challenges. In: Barr, R.S., Helgason, R.V., Kennington, J.L. (eds.) Interfaces in Computer Science and Operations Research: Advances in Metaheuristics, Optimization and Stochastic Modeling Technologies, pp. 1–75. Kluwer, Boston (1997)

    Chapter  Google Scholar 

  13. Glover, F., Laguna, M.: Tabu Search. Kluwer, Boston (1997)

    Book  Google Scholar 

  14. Gonçalves, J.F., Resende, M.G.: Biased random-key genetic algorithms for combinatorial optimization. J. Heuristics 17(5), 487–526 (2011)

    Article  Google Scholar 

  15. Gortázar, F., Duarte, A., Laguna, M., Martí, R.: Black-box scatter search for general classes of binary optimization problems. Comput. Oper. Res. 37(11), 1977–1986 (2010)

    Article  Google Scholar 

  16. Hansen, P., Mladenovic, N.: An introduction to variable neighborhood search. In: Voss, S., Martello, S., Ossman, I., Roucairol, C. (eds.) Meta-heuristics, Advances and Trends in Local Search Paradigms for Iotimization, pp. 433–458. Kluwer, Boston (1999)

    Chapter  Google Scholar 

  17. Iman, R.L., Conover, W.J.: A distribution-free approach to inducing rank correlation among input variables. Commun. Stat. Simul. Comput. 11, 311–334 (1982)

    Article  Google Scholar 

  18. Kral, J.: To the problem of segmentation of a program. Inf. Process. Mach. 2, 116–127 (1965)

    Google Scholar 

  19. Laguna, M., Martí, R.: Scatter Search: Methodology and Implementations in C. Kluwer, Boston (2003)

    Book  Google Scholar 

  20. Laguna, M., Martí, R.: Experimental testing of advanced scatter search designs for global optimization of multimodal functions. J. Glob. Optim. 33, 235–255 (2005)

    Article  Google Scholar 

  21. Laguna, M., Duarte, A., Martí, R.: Hybridizing the cross entropy method: an application to the max-cut problem. Comput. Oper. Res. 36(2), 487–498 (2009)

    Article  Google Scholar 

  22. Laguna, M., Molina, J., Pérez, F., Caballero, R., Hernández-Díaz, A.: The challenge of optimizing expensive black boxes: a scatter search / rough set theory approach. J. Oper. Res. Soc. 61(1), 53–67 (2010)

    Article  Google Scholar 

  23. Larrañaga, P., Lozano, J.A.: Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston (2002)

    Book  Google Scholar 

  24. Lippai, I., Heaney, J.P., Laguna, M.: Robust water system design with commercial intelligent search optimizers. J. Comput. Civ. Eng. 13(3), 135–143 (1999)

    Article  Google Scholar 

  25. Lusa, A., Potts, C.N.: A variable neighbourhood search algorithm for the constrained task allocation problem. J. Oper. Res. Soc. 59(6), 812–822 (2008)

    Article  Google Scholar 

  26. Martí, R., Gortázar, F., Duarte, A.: Heuristics for the bandwidth colouring problem. Int. J. MetaHeuristics. 1(1), 11–29 (2010)

    Google Scholar 

  27. McKay, M.D., Beckman, R.J., Conover, W.J.: A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21, 239–245 (1979)

    Google Scholar 

  28. Prestwich, S.: Constrained bandwidth multicoloration neighborhoods. Computational symposium on graph coloring and its generalizations, (pp. 126–133). Ithaca, NY (2002)

  29. Rossman, L.A.: EPANET: User’s Manual. United States Environmental Protection Agency, Cincinnati (2000)

    Google Scholar 

  30. Schittekat, P., Sörensen, K.: Supporting 3PL decisions in the automotive industry by generating diverse solutions to a large-scale location-routing problem. Oper. Res. 57(5), 1058–1067 (2009)

    Article  Google Scholar 

  31. Shaake, J.C., Lai, D.: Linear Programming and Dynamic Programming Application to Water Distribution Network Design. Massachusetts Institute of Technology, Cambridge (1969)

    Google Scholar 

  32. Spears, W.M., DeJong, K.A.: On the virtues of parameterized uniform crossover. In: Belew, R.K., Booker, L.B. (eds.) Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 230–236. Morgan Kaufmann Publishers Inc, San Francisco (1991)

  33. Stein, M.: Large sample properties of simulations using latin hypercube sampling. Technometrics 29, 143–151 (1987)

    Article  Google Scholar 

  34. Taillard, E.D., Gambardella, L.M., Gendreau, M., Potvin, J.-Y.: Adaptive memory programming: a unified view of metaheuristics. Eur. J. Oper. Res. 135, 1–16 (2001)

    Article  Google Scholar 

  35. Vasan, A., Simonovic, S.P.: Optimization of water distribution network design using differential evolution. J. Water Resour. Plan. Manag. 136(2), 279–287 (2010)

    Article  Google Scholar 

  36. Weitz, R.R., Jelassi, M.T.: Assigning students to groups: a multi-criteria decision support system approach. Decis. Sci. 23(3), 746–757 (1992)

    Article  Google Scholar 

  37. Yates, D.F., Templeman, A.B., Boffey, T.B.: The computational complexity of the problem of determining least capital cost designs for water supply networks. Eng. Optim. 7(2), 143–155 (1984)

    Article  Google Scholar 

  38. Yeniay, Ö.: Penalty function methods for constrained optimization with genetic algorithms. Math. Comput. Appl. 10(1), 45–56 (2005)

    Google Scholar 

Download references

Acknowledgments

This research has been partially supported by the Government of Spain (Grant Refs. TIN2009-07516 and TIN2012-35632).

Author information

Authors and Affiliations

  1. Leeds School of Business, University of Colorado at Boulder, Boulder, CO, USA

    Manuel Laguna

  2. Departamento de Ciencias de la Computación, Universidad Rey Juan Carlos, Madrid, Spain

    Francisco Gortázar, Micael Gallego & Abraham Duarte

  3. Departamento de Estadística e Investigación Operativa, Universitat de València, Valencia, Spain

    Rafael Martí

  4. Visiting the Leeds School of Business, University of Colorado at Boulder, Boulder, CO, USA

    Rafael Martí

Authors
  1. Manuel Laguna
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Francisco Gortázar
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Micael Gallego
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Abraham Duarte
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Rafael Martí
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Manuel Laguna.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Laguna, M., Gortázar, F., Gallego, M. et al. A black-box scatter search for optimization problems with integer variables. J Glob Optim 58, 497–516 (2014). https://doi.org/10.1007/s10898-013-0061-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-013-0061-2

Keywords

Search

Navigation