Abstract
This paper presents an interactive method for solving general 0-1 multiobjective linear programs using Simulated Annealing and Tabu Search. The interactive protocol with the decision maker is based on the specification of reservation levels for the objective function values. These reservation levels narrow the scope of the search in each interaction in order to identify regions of major interest to the decision maker. Metaheuristic approaches are used to generate potentially nondominated solutions in the computational phases. Generic versions of Simulated Annealing and Tabu Search for 0-1 single objective linear problems were developed which include a general routine for repairing unfeasible solutions. This routine improves significantly the results of single objective problems and, consequently, the quality of the potentially nondominated solutions generated for the multiobjective problems. Computational results and examples are presented.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aarts, E. and J. Korst. (1989). Simulated Annealing and Boltzman Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. Wiley.
Aboudi, R. and K. Jörnsten. (1994). “Tabu Search for General Zero-one Integer Programs using the Pivot and Complement Heuristic. ” ORSA Journal on Computing 6(1), 82–93.
Abramson, D., H. Dang, and M. Krishnamoorthy. (1996). “A Comparison of Two Methods for Solving 0–1 Integer Programs Using a General Purpose Simulated Annealing Algorithm. ” Annals of Operations Research 63, 129–155.
Alves, M.J. and J. Clímaco. (1996). “One Experiment Using Simulated Annealing on 0–1 Linear Programming Problems. ” Presented at the Symposium on Combinatorial Optimization, London, 27–29/3/1996.
Balas, Egon. (1965). “An Additive Algorithm for Solving Linear Problems with Zero-One Variables. ” Operations Research 15, 517–546.
Beasley, J.E. (1990). “OR-Library: Distributing Test Problems by Electronic Mail. ” Journal of Operational Research Society 41(11), 1069–1072. See also in WWW site http://mscmga.ms.ic.ac.uk/info.html.
Connolly, D. (1992). “General Purpose Simulated Annealing. ” Journal of Operations Research Society 43(5), 495–505.
Czyzak, P. and A. Jaszkiewicz. (1996). “A Multiobjective Metaheuristic Approach by the Capital Budgeting Model. ” Control and Cybernetics 25(1), 177–187.
Dowsland, K. (1993). “Simulated Annealing. ” In C.R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems, Blackweel Scientific Publication, Oxford, ch. 2.
Drexl, A. (1988). “A Simulated Annealing Approach to the Multiconstraint Zero-One Knapsack Problem. ” Computing 40, 1–8.
Fortemps, P., J. Teghem, and E.L. Ulungu. (1994). “Heuristics for Multiobjective Combinatorial Optimization by Simulated Annealing. ” Presented at the XIth International Conference on MCDM, Coimbra, 1–6/8/1994.
Glover, Fred. (1986). “Future Paths for Integer Programming and Links to Artificial Intelligence. ” Computers and Operations Research 5, 533–549.
Glover, Fred. (1989). “Tabu Search-Part 1. ” ORSA Journal on Computing 4(3), 190–206.
Glover, Fred. (1990a). “Tabu Search-Part II. ” ORSA Journal on Computing 2(1), 4–32.
Glover, Fred. (1990b). “Tabu Search: A Tutorial. ” Interfaces 20(4), 74–94.
Glover, F. and M. Laguna. (1993). “Tabu Search. ” In C.R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems, Blackweel Scientific Publication, Oxford, ch. 3.
Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, Mass: Addison-Wesley.
Grossman, T. and A. Wool. (1997). “Computational Experience with Approximation Algorithms for the Set Covering Problem. ” European Journal of Operational Research 101(1), 81–92.
Hansen, M.P. (1997). “Tabu Search for Multiobjective Optimization: MOTS. ” Presented at the XII International Conference on MCDM, University of Cape Town, 6–10/1/97.
Kirkpatrick, S., C.D. Gellat, and M.P. Vecchi. (1983). “Optimization by Simulated Annealing. ” Science 220, 671–680.
Khuri, S., T. Bäck, and J. Heitkötter. (1994). “The Zero-One Multiple Knapsack Problem and Genetic Algorithms. ” In E. Deaton, D. Oppenheim, J. Urban, and H. Berghel (eds.), Proceedings of the 1994 ACM Symposium on Applied Computing, ACM-Press, New York, 188–193.
Larichev, O. and A. Nikiforov. (1987). “Analytical Survey of Procedures for Solving Multicriteria Mathematical Programming Problems. ” In Y. Sawaragi, K. Inoue, and H. Nakayama (eds.), Towards Interactive and Intelligent Decision Support Systems. Springer-Verlag, pp. 95–104. Lecture Notes in Economics and Mathematical Systems, Vol. 285.
Lokketangen, A., K. Jörnsten, and S. Storoy. (1994). “Tabu Search within a Pivot and Complement Framework. ” International Transactions in Operations Research 1(3), 305–316.
Nakayama, H. (1985). “On the Components in Interactive Multiobjective Programming Methods. ” In M. Grauer, M. Thompson, and A.Wierzbicki (eds.), Plural Rationality and Interactive Decision Processes, Springer-Verlag, pp. 234–247. Lecture Notes in Economics and Mathematical Systems, Vol. 248.
Petersen, C.C. (1967). “Computational Experience with Variants of the Balas Algorithm Applied to the Selection of R&D Projects. ” Management Science 13(9), 736–750.
Senyu, S. and Y. Toyada. (1967). “An Approach to Linear Programming with 0–1 Variables. ” Management Science 15B, 196–207.
Serafini, P. (1994). “Simulated Annealing for Multi Objective Optimization Problems. ” In G.H. Tzeng, H.F. Wang, U.P. Wen, and P.L. Yu (eds.), Multiple Criteria Decision Making, Proceedings of the Xth International Conference, Taipei 19–24/7/92, Springer-Verlag, pp. 283–292.
Steuer, R. (1986). Multiple Criteria Optimization: Theory, Computation and Application. Wiley.
Ulungu, E.L. (1993). Optimisation Combinatoire Multicritère: Détermination de l'ensemble des solutions efficaces et méthods interactives. Phd dissertation, University de Mons-Hainaut.
Weingarter, H.M. and D.N. Ness. (1967). “Methods for the Solution of the Multi-Dimensional 0/1 Knapsack Problem. ” Operations Research 15, 83–103.
Wierzbicki, A. (1980). “The Use of Reference Objectives in Multiobjective Optimization. ” In G. Fandel, and T. Gal (eds.), Multiple Criteria Decision Making. Theory and Application. Springer-Verlag, Berlin, pp. 468–486.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Alves, M.J., Clímaco, J. An Interactive Method for 0-1 Multiobjective Problems Using Simulated Annealing and Tabu Search. Journal of Heuristics 6, 385–403 (2000). https://doi.org/10.1023/A:1009686616612
Issue Date:
DOI: https://doi.org/10.1023/A:1009686616612