Skip to main content
SpringerLink
Log in

Multi-start and path relinking methods to deal with multiobjective knapsack problems

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper deals with a multiobjective combinatorial optimization problem called Extended Knapsack Problem. By applying multi-start search and path relinking we rapidly guide the search toward the most balanced zone of the Pareto-optimal front. The Pareto relation is applied in order to designate a subset of the best generated solutions to be the current efficient set of solutions. The max-min criterion with the Hamming distance is used as a measure of dissimilarity in order to find diverse solutions to be combined. The performance of our approach is compared with several state-of-the-art MOEAs for a suite test problems taken from the literature.

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

Similar content being viewed by others

References

  • Beausoleil, R. (2001). Multiple criteria scatter search. In J. Pinho de Sousa (Ed.), Proceedings of 4th metaheuristics international conference (pp. 534–539). Porto, Portugal.

  • Beausoleil, R. (2004). Bounded variables nonlinear multiple criteria optimization using scatter search. Revista de Matemática: Teoría y Aplicaciones. CIMPA, 11(1), 17–40.

    Google Scholar 

  • Beausoleil, R. (2006). MOSS—multiobjective scatter search applied to nonlinear multiple criteria optimization. European Journal of Operational Research, 169, 426–449.

    Google Scholar 

  • Corne, D. W., Knowles, J. D., & Oates, M. J. (2000). The Pareto envelop-based selection algorithm for multiobjective optimization. In M. Schoenauer (Ed.), Parallel problem solving from nature—PPSN VI (pp. 839–848). Berlin: Springer.

    Chapter  Google Scholar 

  • Czyzak, P., & Jazkiewicz, A. (1996). A multiobjective metaheuristc approach to the location of a petrol station by the capital budgeting model. Control and Cybernetics, 25, 177–187.

    Google Scholar 

  • Gandileaux, X., Vancoppenolle, D., & Tuytentts, A. (1998). A first making use of GRASP for solving MOCO problem. Technical Report, University of Valenciennes, France.

  • Glover, F. (1994). Optimization by ghost image processes in neural networks. Computers and Operation Research, 21(8), 801–822.

    Article  Google Scholar 

  • Glover, F. (2000). Multi-start and strategic oscillation methods—principles to exploit adaptive memory. In M. Laguna, & J. L. Gonzalez-Velarde (Eds.), Computing tools for modeling, optimization and simulation: interfaces in computer science and operations research (Chapter 1, pp. 1–24). Dordrecht: Kluwer Academic.

    Google Scholar 

  • Glover, F., & Laguna, M. (1997). Tabu search. Dordrecht: Kluwer Academic.

    Google Scholar 

  • Hansen, M. P. (1997). Solving multiobjective knapsack problems using MOTS. Conference paper, MIC’97, Sophia Antipolis, France, July 21–24.

  • Jazkiewicz, A. (2002). Genetic local search for multiobjective combinatorial optimization. European Journal of Operational Research, 137, 50–71.

    Article  Google Scholar 

  • Knowles, J. D., & Corne, D. W. (2000). M-PAES: a memetic algorithm for multiobjective optimization. In Proc. of 2000 congress on evolutionary computation (pp. 325–332).

  • Makarov, I. M., Vinogradskaia, T. M., Rubinski, A. A., & Sokolov, V. B. (1982). Choice theory and decision making. Moscow: Nauka (in Russian).

    Google Scholar 

  • Papadimitriu, C., & Steiglitz, K. (1982). Combinatorial optimization: algorithm and complexity. Englewood Cliffs: Prentice-Hall.

    Google Scholar 

  • Tuyttens, D., Teghem, J., Fortemps, P., & Van Nieuwenhuyse, K. (2000). Performance of the MOSA method for the bicriteria assignment problem. Journal of Heuristics, 6(3), 295–310.

    Article  Google Scholar 

  • Zitzler, E., & Laumanns, M. (2001). Test problems for multiobjective optimizers. Institute TIK, Swiss Federal Institute of Technology (ETH) Zurich, Switzerland. http://www.tik.ee.ethz.ch/~zitzler/testdata.html.

  • Zitzler, E., & Thiele, L. (1999). Multiobjective evolutionary algorithms: a comparative case study and the strenght Pareto approach. IEEE Transaction on Evolutionary Computation, 3(4), 257–271.

    Article  Google Scholar 

  • Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: improving the strength Pareto evolutionary algorithm. In K. Giannakoglou, D. Tsahalis, J. Periaux, P. Papailou, T. Fogarty (Eds.), EUROGEN 2001, Evolutionary methods for design, optimization and control with applications to industrial problems (pp. 95–100). Athens, Greece, September.

Download references

Author information

Authors and Affiliations

  1. Departmento de Matemática Interdisciplinaria, Instituto de Cibernética Matemática y Física, Ciudad Habana, Cuba

    Ricardo P. Beausoleil & Rodolfo A. Montejo

  2. Fac. Ing. Industrial, Instituto Superior Politécnico José Antonio Echeverría, Ciudad Habana, Cuba

    Gulnara Baldoquin

Authors
  1. Ricardo P. Beausoleil
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gulnara Baldoquin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rodolfo A. Montejo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ricardo P. Beausoleil.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Beausoleil, R.P., Baldoquin, G. & Montejo, R.A. Multi-start and path relinking methods to deal with multiobjective knapsack problems. Ann Oper Res 157, 105–133 (2008). https://doi.org/10.1007/s10479-007-0199-8

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-007-0199-8

Keywords

Search

Navigation