×

zbMATH — the first resource for mathematics

Computing improved optimal solutions to max-min flexible constraint satisfaction problems. (English) Zbl 0945.90087
Summary: The formal framework for decision making in a fuzzy environment is based on a general max-min, bottleneck-like optimization problem, proposed by Zadeh. It is also the basis for extending the constraint satisfaction paradigm of artificial intelligence to accommodating flexible or prioritized constraints. This paper surveys refinements of the ordering of solutions supplied by the max-min formulation, namely the discrimin partial ordering and the leximin complete preordering. A general algorithm is given which computes all maximal solutions in the sense of these relations. It also sheds light on the structure of the set of best solutions. Moreover, classes of problems for which there is a unique best discrimin and leximin solution are exhibited, namely, continuous problems with convex domains, and so called isotonic problems. Noticeable examples of such problems are fuzzy linear programming problems and fuzzy PERT-like scheduling problems.

MSC:
90C70 Fuzzy and other nonstochastic uncertainty mathematical programming
90C47 Minimax problems in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Behringer, F., On optimal decisions under complete ignorance: A new criterion stronger than both Pareto and maxmin, European journal of operational research, 1, 295-306, (1977) · Zbl 0369.90141
[2] Behringer, F., A simplex based algorithm for the lexicographically extended linear maxmin problem, European journal of operational research, 7, 274-283, (1981) · Zbl 0455.90053
[3] Behringer, F., Lexmaxmin in fuzzy multiobjective decision making, Optimization, 21, 23-49, (1990) · Zbl 0777.90021
[4] Bellman, R.; Giertz, M., On the analytic formalism of the theory of fuzzy sets, Information sciences, 5, 149-156, (1973) · Zbl 0251.02059
[5] Bellman, R.; Zadeh, L., Decision-making in a fuzzy environment, Management science, 17, 4, 141-164, (1970) · Zbl 0224.90032
[6] Benferhat, S., Cayrol, C., Dubois, D., Lang, J., Prade, H., 1993. Inconsistency management adn prioritized syntax-based entailment. Proceedings of the 13th Joint Conference on Artificial Intelligence (IJCAI), Chambery, pp. 640-645
[7] Brewka, G., 1989. Preferred subtheories: An extended logical framework for default reasoning. Proceedings of the 11th Joint Conference on Artificial Intelligence (IJCAI 89), Detroit, MI, pp. 1043-1048 · Zbl 0713.68053
[8] Burkard, R.; Rendl, F., Lexicographic bottleneck problems, Operations research letters, 10, 303-308, (1991) · Zbl 0744.90069
[9] Chanas, S.; Kamburowski, J., The use of fuzzy variables in PERT, Fuzzy sets and systems, 5, 11, 11-19, (1981) · Zbl 0451.90076
[10] Delgado, M., Verdegay, J., Vila, M., 1990. A possibilistic approach for multiobjective programming problem efficiency of solutions, in: Slowinski and Teghem (1990) pp. 229-248 · Zbl 0728.90093
[11] Descloux, J., Approximation in lp and Chebyshev approximations, J. soc. indust. appl. math., 11, 1017-1026, (1963) · Zbl 0125.31004
[12] Dubois, D.; Prade, H., Algorithmes de plus courts chemins pour traiter des données floues, Rairo, 12, 213-227, (1978) · Zbl 0379.90046
[13] Dubois, D., Prade, H., 1987. Théorie des Possibilités: applications à la représentation des connaissances en informatique, 2 ed., Masson, Paris · Zbl 0674.68059
[14] Dubois, D., Fargier, H., Prade, H., 1994. Propagation and satisfaction of flexible constraints fuzzy sets neural networks and soft computing. Kluwer Academic Publishers, Dordrecht
[15] Dubois, D.; Fargier, H.; Prade, H., Fuzzy constraints in job-shop scheduling, Journal of intelligent manufacturing, 6, 1995, 215-234, (1995)
[16] Dubois, D.; Fargier, H.; Prade, H., Possibility theory in constraint satisfaction problems: handling priority preference and uncertainty, Applied intelligence, 6, 287-309, (1996) · Zbl 1028.91526
[17] Dubois, D., Fargier, H., Fortemps, P., Prade, H., 1997. Leximin optimality and fuzzy set theroretic operations. IFSA’97
[18] Erschler, J.; Lopez, P.; Thuriot, C., Raisonnement temporel sous contraintes de ressource et problèmes d’ordonnancement, Revue d’intelligence artificielle, 5, 3, 7-32, (1991)
[19] Erschler, J., Roubellat, J., Vernhes, 1976. Finding some essential characteristics of the feasible solutions for a scheduling problem. Operations Research 24, 774-783 · Zbl 0335.90027
[20] Esquirol, P.; Lopez, P.; Fargier, H.; Schiex, T., Constraint programming, Jorbel, 35, 5-36, (1995) · Zbl 0874.90162
[21] Fargier, H., 1994. Problèmes de satisfaction de contraintes flexibles: application à l’ordonnancement de production, Ph.D. Thesis, Université P. Sabatier Toulouse
[22] Fargier, H., 1997. Fuzzy scheduling: Principles and experiments. In: Dubois, D., Prade, H., Yagar, R.R. (Eds.), Fuzzy Information Engineering: A Guided Tour of Applications. Wiley, New York, pp. 655-668
[23] Fargier, H., Lang, J., Schiex, T., 1993. Selecting preferred solutions in fuzzy constraint satisfaction problems. Proc. of EUFIT’93 Aachen
[24] Fishburn, P.C., Lexicographic orders, utilities and decision rules: A survey, Management science, 20, 1442-1471, (1974) · Zbl 0311.90007
[25] Fortemps, P., 1997. Jobshop scheduling with fuzzy durations IEEE Transactions on Fuzzy Systems 5, 557-569
[26] Freuder, E., Snow, 1989. Improved relaxation and search methods for approximate constraint satisfaction with a maximin criterion. Proceedings of the 8th Conference of the Canadian Society for Computational Studies of Intelligence, pp. 227-230
[27] Hillier, F.S., Lieberman, G.J., 1989. Introduction to Operations Research, 4th ed. McGraw-Hill, New York · Zbl 0155.28202
[28] Keeney, R., Raiffa, H., 1976. Decisions with Multiple Objectives: Preferences and value tradeoffs. Wiley, New York · Zbl 0488.90001
[29] Leberling, H., On finidng the compromise solution in multicriteria problems using the fuzzy MIN operator, Fuzzy sets and systems, 6, 105, (1981) · Zbl 0465.90081
[30] Lootsma, F.A., Stochastic and fuzzy PERT, European journal of operational research, 43, 174-183, (1989) · Zbl 0681.90039
[31] Mackworth, A., Consistency in networks of relations, Artificial intelligence, 8, 99-121, (1977) · Zbl 0341.68061
[32] Martello, S.; Toth, P., Linear assignment problems, Annals of discrete mathematics, 31, 259-282, (1987)
[33] Montanari, H., Networks of constraints: fundamental properties and applications to picture processing, Information sciences, 7, 95-142, (1974) · Zbl 0284.68074
[34] Moulin, H., 1988. Axioms of Cooperative Decision Making. Cambridge University Press, Cambridge, UK · Zbl 0699.90001
[35] Pirlot, M., A characterization of ‘min’ as a procedure for exploiting valued preference relations and related results, Journal of multi-criterial decision analysis, 4, 37-56, (1995) · Zbl 0838.90072
[36] Rice, J., Tschebyscheff approximation in a compact metric space, Bulletin of the American mathematical society, 68, 405-410, (1962) · Zbl 0111.26501
[37] Sadeh, N., 1991. Look-ahead techniques for micro-opportunistic job shop scheduling. Report CS91-102, Carnegie Mellon University, Pittsburgh, PA
[38] Sakawa, M., 1993. Fuzzy Sets and Interactive Multiobjective Optimization. Plenum Press, New York · Zbl 0842.90070
[39] Schweizer, B., Sklar, A., 1983. Probabilistic Metric Spaces. North-Holland, Amsterdam · Zbl 0546.60010
[40] Sen, A.K., 1986. Social choice theory, In: Arrow, K.J., Intriligator, M.D., Handbook of Mathematical Economics 3, North-Holland, Amsterdam, pp. 1073-1181
[41] Slowiński, R., Teghem, J. (Eds.), 1990. Stochastic Versus Fuzzy Approaches to Multiobjective Mathematical Programming under Uncertainty. Kluwer Academic Publishers, Dordrecht, The Netherlands
[42] Teghem, J., 1996. Programmation linéaire, collection statistique et mathématiques appliquées. Editions de l’Université de Bruxelles
[43] Van Hentenryck, P., 1989. Constraint Satisfaction and Logic Programming. MIT Press, Cambridge, MA
[44] Yager, R., On ordered weighted averaging aggregation operators in multicriteria decision making, IEEE transactions on systems, man and cybernetics, 18, 183-190, (1988) · Zbl 0637.90057
[45] Zadeh, L.A., Fuzzy sets as a basis for a theory of possibility, Fuzzy sets and systems, 1, 3-28, (1978) · Zbl 0377.04002
[46] Zimmermann, H., Description and optimization of fuzzy system, International journal of general system, 2, 209-216, (1976)
[47] Zimmermann, H., Fuzzy programming and linear programming with several objective functions, Fuzzy sets and systems, 1, 45-55, (1978) · Zbl 0364.90065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.