Fuzzy relation equations (I): the general and specialized solving algorithms

 In this article, we develop a new method and an algorithm to solve a system of fuzzy relation equations. We first introduce a solution-base-matrix and then give a tractable mathematical logic representation of all minimal solutions. Next, we design a new universal algorithm to get them. Two simplification rules are found to simplify the solution-base-matrix. We show that a polynomial time algorithm to find all minimal solutions for a general system of fuzzy relation equations simply does not exist with expectation of P=N P. Hence, the problem of solving fuzzy relation equations is an N P-hard problem in terms of computational complexity. Our universal algorithm is still useful when one does not solve a large number of equations. In many real applications the problem of solving fuzzy relation equations can be simplified in polynomial time problems. In this article, we will discuss several cases of practical applications which have such polynomial algorithms.     

An efficient solution procedure for fuzzy relation equations withmax-product composition

We study a system of fuzzy relation equations with max-product composition and present an efficient solution procedure to characterize the whole solution set by finding the maximum solution as well as the complete set of minimal solutions. Instead of solving the problem combinatorially, the procedure identifies the “nonminimal” solutions and eliminates them from the set of minimal solutions     

Remarks on minimal solutions of a system of fuzzy relation equations over complete infinitely distributive lattices

In Section 3.6 of Fuzzy relation equations and their applications to knowledge engineering. Kluwer Academic Publishers, Boston (1989), Di Nola et al. presented a procedure to find a minimal solution from a fixed solution of a system of fuzzy relation equations over complete infinitely distributive lattices, and put the question: is the minimal solution found by the procedure unique or not? In this paper, we give a negative answer to the question and make some further remarks. We not only give a necessary and sufficient condition for the uniqueness of such minimal solutions, but also characterize the existence of the least solution and a unique solution of a system of fuzzy relation equations over complete infinitely distributive lattices.     

Minimization of linear objective functions under the constraints expressed by a system of fuzzy relation equations

This paper considers the following optimization problem: minimization of linear objective functions under the constraints expressed by a system of fuzzy relation equations using max-product composition. We first show some properties of minimal solutions of a system of fuzzy relation equations with max-product composition and present some rules for reducing the original problem. Then we derive an algorithm which enables us to find all the optimal solutions for solving the optimization problem and provide some numerical examples to illustrate.     

Analytical resolution and numerical identification of fuzzyrelational systems

Since Sanchez's seminal paper on fuzzy relational equations, both their theories and applications have been continuously exploited by researchers. However, the solvable conditions of a system of fuzzy relational equations, also known as a fuzzy relational system (FRS), are still poorly established and their relationship with the methods for obtaining approximate solutions are unclear. When the FRS is adopted to model a fuzzy system, most of the existing identification algorithms focus on parameter estimation and less on the structure identification. In this paper, these two issues are addressed. New theoretical understandings on solving a system of fuzzy relational equations exactly and approximately are presented and their implications on the use of FRS to encode fuzzy rulebases are highlighted. Based upon the guided evolutionary simulated annealing (GESA) algorithm, an evolutionary identification formulation called EVIDENT capable for both parameter and structure identifications in fuzzy system models is proposed. As demonstrated by the simulation results, the new algorithm not only is effective in determining the structure of the systems, but also identifies a better parametric solution, as compared with that of the existing FRS identification algorithms.     

Solutions of fuzzy relation equations based on continuous t-norms

This study is concerned with fuzzy relation equations with continuous t-norms in the form ATR = B, where A and B are the fuzzy subsets of X and Y, respectively; R ⊂ X × Y is a fuzzy relation, and T is a continuous t-norm. The problem is how to determine A from R and B. First, an “if and only if” condition of being solvable is presented. Novel algorithms are then presented for determining minimal solutions when X and Y are finite. The proposed algorithms generate all minimal solutions for the equations, making them efficient solving procedures.     

Solving interval-valued fuzzy relation equations

Solving systems of fuzzy relation equations is an important topic in fuzzy set theory. This paper studies the composite interval-valued fuzzy relation equations. After analyzing the properties of its solution set, we convert the fuzzy relation equations into a fuzzy relation inequality system and propose an efficient computational procedure to generate the whole solution set. Examples are included to illustrate the idea and algorithm     

Most Relevant Explanation: computational complexity and approximation methods

Most Relevant Explanation (MRE) is the problem of finding a partial instantiation of a set of target variables that maximizes the generalized Bayes factor as the explanation for given evidence in a Bayesian network. MRE has a huge solution space and is extremely difficult to solve in large Bayesian networks. In this paper, we first prove that MRE is at least NP-hard. We then define a subproblem of MRE called MRE _k that finds the most relevant k-ary explanation and prove that the decision problem of MRE _k is NP^PPNP^{\it PP}-complete. Since MRE needs to find the best solution by MRE _k over all k, and we can also show that MRE is in NP^PPNP^{\it PP}, we conjecture that a decision problem of MRE is NP^PPNP^{\it PP}-complete as well. Furthermore, we show that MRE remains in NP^PPNP^{\it PP} even if we restrict the number of target variables to be within a log factor of the number of all unobserved variables. These complexity results prompt us to develop a suite of approximation algorithms for solving MRE, One algorithm finds an MRE solution by integrating reversible-jump MCMC and simulated annealing in simulating a non-homogeneous Markov chain that eventually concentrates its mass on the mode of a distribution of the GBF scores of all solutions. The other algorithms are all instances of local search methods, including forward search, backward search, and tabu search. We tested these algorithms on a set of benchmark diagnostic Bayesian networks. Our empirical results show that these methods could find optimal MRE solutions for most of the test cases in our experiments efficiently.     

An algorithm for solving fuzzy relation equations with max-T composition operator

This paper studies the problem of solving a max-T composite finite fuzzy relation equation, where T is a special class of pseudo-t-norms. If the equation is solvable, then its set of feasible solutions is determined by the greatest solution and a finite number of minimal solutions. Some necessary conditions are presented for the minimal solutions in terms of the maximum solution and zero value. Under these conditions, some minimal solutions of the system can be obtained easily. Some procedures are also proposed in order to simplify the original system. The simplified system is then decomposed (if possible) into several subsystems with smaller dimensions, which are very easy to solve. Furthermore, a method is presented to solve each subsystem. By combining the method and those procedures, an efficient algorithm is proposed to obtain the set of feasible solutions of the original system. Two examples are also given to illustrate the algorithm.     

Algorithm for Solving Max-product Fuzzy Relational Equations

Analytical methods are proposed for solving fuzzy linear system of equations when the composition is max-product. These methods provide universal algorithm for computing the greatest solution and the set of all minimal solutions, when the system is consistent. In case of inconsistency, the equations that can not be satisfied are obtained.     

Minimizing a nonlinear function under a fuzzy max-t-norm relational equation constraint

This work studies a nonlinear optimization problem subject to fuzzy relational equations with max-t-norm composition. Since the feasible domain of fuzzy relational equations with more than one minimal solution is non-convex, traditional nonlinear programming methods usually cannot solve them efficiently. This work proposes a genetic algorithm to solve this problem. This algorithm first locates the feasible domain through the maximum solution and the minimal solutions of the fuzzy relational equations, to significantly reduce the search space. The algorithm then executes all genetic operations inside this feasible domain, and thus avoids the need to check the feasibility of each solution generated. Moreover, it uses a local search operation to fine-tune each mutated solution. Experimental results indicate that the proposed algorithm can accelerate the searching speed and find the optimal solution.     

Deriving minimal solutions for fuzzy relation equations with max-product composition

This work considers fuzzy relation equations with max-product composition. The critical problem in solving such equations is to determine the minimal solutions when an equation is solvable. However, this problem is NP-hard and difficult to solve [A.V. Markovskii, On the relation between equations with max-product composition and the covering problem, Fuzzy Sets and Systems 153 (2005) 261-273]. This work first examines the attributes of a solvable equation and characteristics of minimal solutions, then reduces the equation to an irreducible form, and converts the problem into a covering problem, for which minimal solutions are correspondingly determined. Furthermore, for theoretical and practical applications, this work presents a novel method for obtaining minimal solutions. The proposed method easily derives a minimal solution, and obtains other minimal solutions from this predecessor using a back-tracking step. The proposed method is compared with an existing algorithm, and some applications are described in detail.     

A genetic algorithm for optimization problems with fuzzy relation constraints using max-product composition

We consider nonlinear optimization problems constrained by a system of fuzzy relation equations. The solution set of the fuzzy relation equations being nonconvex, in general, conventional nonlinear programming methods are not practical. Here, we propose a genetic algorithm with max-product composition to obtain a near optimal solution for convex or nonconvex solution set. Test problems are constructed to evaluate the performance of the proposed algorithm showing alternative solutions obtained by our proposed model.     

Enclosing solutions of linear interval equations is NP-hard

We show that if the conjectureP≠NP is true, then there does not exist a general polynomial-time algorithm for enclosing the solution set of a system of linear interval equations.     

An Efficient Procedure for Solving a Fuzzy Relational Equation With Max–Archimedean t-Norm Composition

In the literature, a necessary condition for minimal solutions of a fuzzy relational equation with max-product composition shows that each of its components is either zero or the corresponding component's value of the greatest solution. In this paper, we first extend this necessary condition to the situation with max-Archimedean triangular-norm (t-norm) composition. Based on this necessary condition, we then propose rules to reduce the problem size so that the complete set of minimal solutions can be computed efficiently. Furthermore, rather than work with the actual equations, we employ a simple matrix whose elements capture all of the properties of the equations in finding the minimal solutions. Numerical examples with specific cases of the max-Archimedean t-norm composition are provided to illustrate the procedure.     

Localized algorithms for vlsi processor arrays

In this paper we analyze the algorithms expressed as a system of recurrence equations. The algorithms are called 2^?1 output algorithms if two output values of one function (variable identification) are specified by the system of recurrence equations for each index point in the algorithm. The algorithm is in free form if the indexes of these two values are not dependent. Two standard classes are determined by this criteria: the nearest neighbour and the all pair form. For example the sorting algorithm can be expressed in the all pair form i.e., the linear insertion algorithm or in the nearest neighbour form i.e., the bubble sort algorithm. However these algorithms are different in their nature. A procedure to eliminate the computational broadcast for the all pair 2^?1output algorithm has been proposed by the authors in [1]. The result obtained by implementing this procedure was a localized form of the algorithm and a system of uniform recurrence equations by eliminating the computational and data broadcast. So he data dependence method can be efficiently used for parallel implementations. The proposed procedure cannot be implemented directly on the nearest neighbour form algorithms. Here we show how the algorithm can be restructured into a form where the computational and data broadcast can be eliminated. These transformations result in localized algorithms. A few examples show how these algorithms can be implemented on processor arrays. For example, the Gentleman Kung triangular array [2] can be used for solving the QR decomposition algorithm for both forms of the algorithm. The implementations differ in the order of the data flow and the processor operation. We show that the implementation of the nearest neighbour algorithm is even better than the standard one.     

Fuzzy relation equations and reduction of fuzzy automata

We show that the state reduction problem for fuzzy automata is related to the problem of finding a solution to a particular system of fuzzy relation equations in the set of all fuzzy equivalences on its set of states. This system may consist of infinitely many equations, and finding its non-trivial solutions may be a very difficult task. For that reason we aim our attention to some instances of this system which consist of finitely many equations and are easier to solve. First, we study right invariant fuzzy equivalences, and their duals, the left invariant ones. We prove that each fuzzy automaton possesses the greatest right (resp. left) invariant fuzzy equivalence, which provides the best reduction by means of fuzzy equivalences of this type, and we give an effective procedure for computing this fuzzy equivalence, which works if the underlying structure of truth values is a locally finite residuated lattice. Moreover, we show that even better reductions can be achieved alternating reductions by means of right and left invariant fuzzy equivalences. We also study strongly right and left invariant fuzzy equivalences, which give worse reductions than right and left invariant ones, but whose computing is much easier. We give an effective procedure for computing the greatest strongly right (resp. left) invariant fuzzy equivalence, which is applicable to fuzzy automata over an arbitrary complete residuated lattice.     

Infinite fuzzy relation equations with continuous t-norms

This study develops a concept of infinite fuzzy relation equations with a continuous t-norm. It extends the work by Xiong and Wang [Q.Q. Xiong, X.P. Wang, Some properties of sup-min fuzzy relational equations on infinite domains, Fuzzy Sets and Systems 151 (2005) 393-402]. We describe attainable (respectively, unattainable) solutions, which are closely related to minimal solutions to the equations. It is shown that a solution set comprises both attainable and unattainable solutions. The study offers a characterization of these solutions. Under some assumptions, the solution set is presented and discussed. Two applications are also given.     

Solving sparse linear systems of equations using the modified digraph approach

We propose two different algorithms which depend on the modified digraph approach for solving a sparse system of linear equations. The main feature of the algorithms is that the solution of a sparse system of linear equations can be expressed exactly if all the non-zero entries, including the right-hand side, are integers and if none of the products exceeds the size of the largest integer that can be represented in the arithmetic of the computer used. The implementation of the algorithms is tested on five problems. The results are compared with those obtained using an algorithm proposed earlier. It is shown that the efficiency with which a sparse system of linear equations can be analysed by a digital computer using the proposed modified digraph approach as a tool depends mainly on the efficiency with which semifactors and k-semifactors are generated. Finally, in our implementation of the proposed algorithms, the input sparse matrix is stored using a row-ordered list of a modified uncompressed storage scheme.