Abstract
We consider in this paper the solving of 0-1 knapsack problems with multiple linear objectives. We present a tabu search approach to generate a good approximation of the efficient set. The heuristic scheme is included in a redu tion decision space framework. The case of two objectives is developed in this paper. TS principles viewed into the multiobjective context are discussed. According to a prospective way, several variations of the algorithm are investigate. Numerical experiments are reported and compared with available exact efficient solutions. Intuitive justifications for the observed empirical behavior of the procedure and open questions are discussed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ben Abdelaziz, F., S. Krichen, and J. Chaouachi. (1999). “An Hybrid Metaheuristic for the MultiObjective Knapsack Problem. ” In St. Voss, S. Martello, I. Osman, and C. Roucairol (eds.), Meta-Heuristics-Advances and Trends in Local Search Paradigms for Optimization. Kluwer, pp. 205–212.
Brandimarte, P. and M. Calderini. (1995). “A Hierarchical Bicriterion Approach to Integrated Process Plan Selection and Job Shop scheduling. ” Int. J. Prod. Res. 33(1), 161–181.
Czyzak, P. and A. Jaszkiewicz. (1998). “Pareto Simulated Annealing-A Metaheuristic Technique for Multiple Objective Combinatorial Optimization. ” Journal of Multicriteria Decision Analysis 7, 34–47.
Dahl, G., K. Jornsten, and A. Lokketangen. (1995). “A Tabu Search Approach to the Channel Minimization Problem. ” ICOTA'95, 9p.
Fréville, A. and G. Plateau. (1993). “Sac-à-dos multidimensionnel en variables 0–1: encadrement de la somme des variables à l'optimum. ” RAIRO 27(2), 169–187.
Fréville, A. and G. Plateau. (1994). “An Efficient Preprocessing Procedure for the Multidimensional 0–1 Knapsack Problem. ” Discrete Applied Mathematics, 189–212.
Gandibleux, X., N. Mezdaoui, and A. Fréville. (1997a). “A Multi-Objective Tabu Search Procedure to Solve Combinatorial Optimization Problems. ” In R. Caballero, F. Ruiz, and R. Steuer (eds.), Advances in Multiple Objective and Goal Programming. Lecture Notes 455 in Economics and Mathematical Systems, Springer, pp. 291–300.
Gandibleux, X., N. Mezdaoui, and E.L.B. Ulungu. (1997b). “Simulated Annealing Versus Tabu Search Multi-Objective Approaches to the MultiObjective KnapSack Problem. ” 13th International Conference on Multiple Criteria Decision-Making, Jan. 6–10, 1997, Cape Town, South Africa.
Geoffrion, A.M. (1974). “Lagrangean Relaxation for Integer Programming. ” Mathematical Programming Study 2, 82–114.
Glover, Fr. (1965). “A Multiphase Dual Algorithm for the Zero-One Integer Programming Problem. ” Operations Research 13(6), 879–919.
Habenicht, W. (1982). “Quad Trees. A Data Structure for Discrete Vector Optimization Problems. ” In P. Hansen (ed.), Springer-Verlag, pp. 136–145. Lecture Notes “Essays and surveys on MCDM”.
Hansen, M.P. (1997). “Tabu Search for MultiObjective Optimization: MOTS. ” 13th International Conference on Multiple Criteria Decision-Making, Jan. 6–10, 1997, Cape Town, South Africa.
Hertz, A., B. Jaumard, C.C. Ribeiro, and W.P. Formosinho. (1994). “A MultiCriteria Tabu Search Aproach to Cell Formation Problems in Group Technology with Multiple Objectives. ” Recherche Opérationnelle-Operations Research 28(3), 303–328.
Malakooti, B., J. Wang, and E.C. Tandler. (1990). “A Sensor-Based Accelerated Approach for Multi-Attribute Machinability and Tool Life Evaluation. ” International Journal of Production Research 28, 2373.
Martello, S. and P. Toth. (1990). Knapsack Problems: Algorithms and Computer Implementations. New York: Wiley.
Martello, S., D. Pisinger, and P. Toth. (1997). “New Trends in Exact Algorithms for the 0–1 Knapsack Problem. ” EURO/INFORMS-97, Barcelona, Spain, pp. 151–160.
Mezdaoui, N., X. Gandibleux, and A. Fréville. (1997). “Decision Space Exploration Techniques in the MultiObjective Tabu Search Procedure Applied on the 0–1 MOKP. ” EURO XV-INFORMS XXXIV, July 14–17, 1997, Barcelona, Spain.
Osman, I. and G. Laporte. (1996). “Metaheuristics: A Bibliography. ” Annals of Operations Research 63, 513–623.
Reeves, C. (1995). Modern Heuristic Techniques for Combinatorial Problems. London: McGrawHill.
Roy, B. and D. Bouyssou. (1993). Aide multicritère à la décision: méthode et cas. Gestion, Economica.
Savelsberg, M.W.P. (1994). “Preprocessing and Probing Techniques for Mixed Integer Programming Problems. ” ORSA Journal on Computing 6(4), 445–454.
Schaffer, J.D. (1985). “Multiple Objective Optimization using Vector Evaluated Genetic Algorithms. ” In Proc. of 1st Int. Conf. on G.A. and Their Applications, 1985, pp. 93–100.
Serafini, P. (1992). “Simulated Annealing for Multi Objective Optimization Problems. ” 10th Int. Conf. on MCDM Proc., Vol. 1, July 19–24, 1992, Taipei, Taiwan, pp. 87–96.
Steuer, R. (1986). Multiple Criteria Optimization: Theory, Computation and Application. New York: Wiley.
Sun, M. and R. Steuer. (1995). “Quad-Trees and Linear Lists for Identifying Non Dominated Criterion Vectors. ” Informs, Journal on Computing 8(4), Fall 1996.
Teghem, J and E.L. Ulungu. (1997). “Bicriteria Assigment Problem. ” MAMDM Int. Conf, May 14–16, 1997, Mons, Belgium, pp. 144–147.
Ulungu, E.L.B. and J. Teghem. (1994). “Multi-Objective Combinatorial Optimization Problems: A Survey. ” Journal of Multi-Criteria Decision Analysis 3, 83–104.
Ulungu, E.L. and J. Teghem. (1995). “The Two Phases Method: An Efficient Procedure to Solve Bi-Objective Combinatorial Optimization Problems. ” Foundations of Computing and Decision Sciences 20(2), 149–165, 1995.
Ulungu, E.L.B., J. Teghem, and Ph. Fortemps. (1995). “Heuristics for Multi-objective Combinatorial Optimization Problems by Simulated Annealing. ” In J. Gu, G.C.Q. Wei, and Sh. Wang (eds.), MCDM: Theory and Applications SCI-TECH Information Services, pp. 228–238.
Vanderpooten, D. (1990). “Multiobjective Programming: Basic Concepts and Approaches. ” In R. Slowinski and J. Teghem (eds.), Stochastic versus Fuzzy Approaches to Multiobjective Mathematical Programming under Uncertainty Kluwer, pp. 7–22.
Van Wassenhove, L. and L. Gelders. (1980). “Solving a Bicriterion Scheduling Problem. ” European Journal of Operational Research 4, 42–48.
WWW Site, LAMIH-ROAD, UVHC, numerical instances for MultiObjective MetaHeuristics. http://www.univ-valenciennes.fr/ROAD/MCDM.html, Université de Valenciennes.
Yu, G. (1990). “Algorithms for Optimizing Piecewise Linear Functions and for Degree Constrained Minimum Spanning Tree Problems. ” PhD, 09–11–01, Wharton School, University of Pennsylvania.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gandibleux, X., Freville, A. Tabu Search Based Procedure for Solving the 0-1 MultiObjective Knapsack Problem: The Two Objectives Case. Journal of Heuristics 6, 361–383 (2000). https://doi.org/10.1023/A:1009682532542
Issue Date:
DOI: https://doi.org/10.1023/A:1009682532542