Computing improved optimal solutions to max–min flexible constraint satisfaction problems

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.