Abstract: Attractive issues related with membership functions in fuzzy nonlinear programming have been discussed in depth in this study. Initially, an approach to constructing unilateral and bilateral membership functions is introduced to deal with soft constraints. In order to facilitate solution of fuzzy nonlinear programming problems, a procedure towards linearization of membership functions is presented, along with a novel modeling methodology to formulate fuzzy nonlinear programming with piecewise linear membership functions. Therein, taking advantage of compatible configuration of binary variables, relations between the sub-membership-functions are explicitly characterized, which could efficiently help prevent constraint-free problems and achieve satisfied solutions. Finally, a numerical example is employed to demonstrate the benefits of the contribution.
INTRODUCTION
At present, the crisp optimization problem already has mature mathematical programming methodologies but these approaches become powerless when facing variety of sources of uncertainty in industrial applications. Alternatively, since fuzzy decision and fuzzy linear programming theories were founded by Bellman and Zadeh (1970) and Zimmermann (1978), respectively, fuzzy programming has been extensively studied and applied to dealing with optimization problems with uncertainty (Zimmermann, 1987; Roubens and Teghem, 1991; Shi and Yu, 1992; Liu and Shi, 1994).
Membership functions are usually employed to represent Decision-Makers (DMs)’understanding and acceptance of uncertainty as well as subjective preferences when dealing with soft constraints in fuzzy programming problems. Generally, membership functions can be trapezoidalor triangular which are easily configured but rarely well accommodated with human’s subjective activities. Instead, Gaussian functions are acknowledged to be excellent alternatives in this issue. However, nonlinear expressions of Gaussian membership functions readily lead to huge difficulties in solving mathematical programming which possibly result in intractable problems such as achievement of local optima.
Piecewise Linear Functions (PLFs) were firstly introduced by Garvin et al. (1957), which have been used in the areas of drilling, production, manufacturing, marketing and distribution. Subsequently, Stone (1961) introduced construction methods of PLFs. After that, PLFs have been studied extensively, even being used to solve large-scale engineering problems in recent years (Wen and Ma, 2008; Effati and Abbasiyan, 2010; Toriello and Vielma, 2012; Sun et al., 2012). Since, the pioneer work of Narasimhan (1980) and Hannan (1981), Piecewise Linear Membership Functions (PLMFs) have been introduced into the fuzzy programming and decision-making community. Depending on the number of sub-segments assigned, PLFs could approximate any nonlinear functions in expected fidelity. Additionally, too much attention on local description could be avoid in simulating human’s satisfaction, which helps make achievement of solutions easier and far from local convergence of fuzzy programming. Nonetheless, PLMFs have found less popularity in applications. For instance, Chang (2010) presented an approach to build PLMFs through selecting the maximum error, which, however, over-relies on computations instead of DM’s preferences.
Due to the special form, the modeling methodologies of fuzzy programming with PLMF are the problem which researchers interesting. There are three existing main methodologies: The first one is the binary variable representation which proposed by Yang and Ignizio (1991), they use binary variables to distinguish the different sub-segments of PLMFs and lay a basis for this methodology; the second one is proposed by Hu and Fang (1999), they converted the problems to a one constraint programming by employing the concepts of constraint surrogation and maximum entropy; the last one is proposed by Li and Yu (2000), they distinguish different sub-segments by changing the symbol which controlled by the absolute values. In the three methodologies, the second one is too complicated to be used in real life and the third one needs adding extra binary variables which will increasing the computational burden. Due to the drawbacks, only the first one had been studied extensively.
After the proposed of Yang and Ignizio (1991), Li and Yu (1999) showed that the method of Yang and Ignizio (1991) demanded extra binary variables in the face of complex PLMFs, thereby solving this problem by adding extra satisfaction degrees. Lin and Chen (2002) suggested that the relationship between sub-segments could be expressed by intersections and unions, so that extending the method of Yang and Ignizio (1991) to handle fuzzy programming problem with complex PLMFs. They also pointed out three shortcomings of Li and Yu’s (1999) method, i.e., no generalized procedure or algorithms available, in need of extra binary variables sometimes and actual aspiration level unachievable directly. Besides, Chang (2007) employed a couple of binary numbers to represent the relationship among binary variables, which became the first generalized algorithm for fuzzy programming with PLMFs. However, in some cases, the combination of binary variables would even lead to constraint-free problems in solving.
The contribution of this study is twofold. First, an approach to manage discrete points of Gaussian membership functions and construct PLMFs according to the reference points selected by DMs is explicitly introduced. Second, a novel method to distribute binary variables in formulating fuzzy programming with PLMFs is suggested, which could not only avoid traditional demerits aforementioned but also make problem solving easier by utilization of few binary items in some situations.
FORMULATION OF NONLINEAR FUZZY MEMBERSHIP FUNCTIONS
Practically, a mathematical programming problem may involve “soft constraints” (Narasimhan, 1980) which refer to the constraints allowing admissible ranges of violations, such as:
| (1) |
where, membership functions μz, μg and μh associated with the goal and constraints are suggested to measure a DM’s satisfaction degree λ, characterized by λ (xi) = μz (xi)∩μg (xi) ∩h (xi). Therefore, we have:
| (2) |
Usually, two kinds of soft constraints are available for a mathematical programming problem, inequality and equality. For an equality constraint, the membership decreases whatever the left-hand side is higher or lower than the limit, which demands a bilateral membership function; while for an inequality constraint, a unilateral membership function could be employed, because the membership decreases when the left-hand side goes beyond the limits. Considering the inequality constraints gi (i) bi in problem (1), the satisfaction degree achieve 1 when gi become less than or equal to bi, while it will descend when gi are greater than bi. As depicted in Fig. 1, where the maximum relaxation of the right-hand side is supposed to be bi+δi, unilateral membership functions are obviously accommodated. As for the equality constraints, hj (xj)
Traditionally, unilateral and bilateral membership functions can be expressed by sub-section functions, such as:
| (3) |
and:
| (4) |
Which are apparently susceptible to expressional and computational difficulties relatively. In response, we introduce an approach to build continuous unilateral and bilateral membership functions in a novel way.
| Fig. 1: | Bilateral membership function |
| Fig. 2: | Unilateral membership function |
Suppose that αi indicates the expectation of ki. In the presence of ki≤ai there is μki = f1 (ki), otherwise μki = f2 (ki). A function y (ki) specified to change with ki on different sides ai. Here, we normalize ki-ai to the interval (-1, 1) by:
In so doing, the bilateral membership functions can be formulated as follow:
| (5) |
where, [•] denotes the Gaussian rounding functions, which can be characterized by:
| (6) |
| Fig. 3: | Unilateral Gaussian membership function |
And f1 (ki) and f2 (ki) are the functions corresponding to left and right sides of point ai, respectively. If ki≤ai, then there is μki = f1 (ki); if ai≤ki, then there is μki = f2 (ki). Therefore, the asymmetric unilateral and bilateral membership functions have been established consequently.
It is acknowledged that Gaussian functions serve best imitations to human’s subjective preferences as well as take advantage of nonlinearity, smoothness and continuous differentiates, which have been extensively applied in intelligent technologies such as neural networks and fuzzy expert systems (Hannan, 1981; Chang, 2010).
Gaussian membership functions are characterized by:
where, a and p are the center point and width factor, respectively. Therefore, the unilateral and bilateral Gaussian membership functions of the constraints corresponding to problem (1) can be specified as follows:
| (7) |
| (8) |
Accordingly, Fig. 3 and 4 show visualization of unilateral and bilateral Gaussian membership functions.
PIECEWISE LINEAR FUZZY MEMBERSHIP FUNCTIONS
Despite that Gaussian fuzzy membership functions could simulate human’s preferences in high fidelity, the inherent characteristics of nonlinearity would lead to computational complexity of the corresponding optimization problems.
| Fig. 4: | Bilateral gaussian membership function |
Motivated by this fact, the nonlinear membership functions are suggested to be segmented into piecewise linear ones. As an example shown in Fig. 5, a basic S-shaped PLMF is characterized by three parameters, μi1, μi2 and μi3, whose expressions are presented as follows:
| (9) |
| (10) |
| (11) |
The convex and concave points between sub-segments can be approximated by unions and intersections, respectively, thereby resulting in μi = μi1∪(μi2∩μi3). It is conceivable that the reference points between sub-segments such as the convex point k1 and concave point k2 depicted in Fig. 5 are decisive to the PLMFs. Therefore, the most important step to build PLMFs is to find the appropriate reference points.
We provide a general procedure towards constructing PLMFs as follows. Firstly, calculate the discrete points of integral membership functions using Eq. 5.
| Fig. 5: | A S-shaped piecewise linear membership function |
Secondly, choose reference points according to DM’s preferences. Finally, build the PLMFs by connecting the key points with straight lines. It is practical to consider that the approximating accuracy of PLFs to the originals relies on the number of sub-segments. Fewer sub-segments may lead to easy calculation but low accuracy, while more sub-segments may result in complicated calculation but high accuracy. To compromise the trade-off relations between accuracy and calculation, DMs are encouraged to consider following suggestions:
| • | Carefully choose the key points and the relevance, such as boundary points, extreme points and inflection points, etc |
| • | In the presence of linear parts involved in the original membership functions, specify the two endpoints of the lines as key points |
| • | More key points should be selected for the constraints sensitive to the optimum solutions |
| • | Consider fewer key points with small membership values because they are rarely concerned with in practice |
FORMULATION OF FUZZY PROGRAMMING
Problem statement: Consider the PLMF described in Fig. 5. As mentioned above, we have
| Fig. 6: | A binary tree representation |
| Fig. 7: | Piecewise linear membership functions |
Accordingly, in an attempt to achieve the greatest of satisfaction, the statement of corresponding fuzzy programming problem could be addressed as follow (Yang and Ignizio, 1991:
| (12) |
where, λ indicates the satisfaction degree, M is a big positive number and δ1 is an additional binary variable.
We should mention that it is less sufficient to use only one binary variable for modeling in the presence of more than one convex points available for a PLMF. Taking the membership function shown in Fig. 7 as an example, two convex points and one concave point available implies two unions and one intersection are involved, demanding two more binary variables for modeling. Accordingly, the fuzzy optimization problem can be formulated as follows (Lin and Chen, 2002):
| (13) |
where, δ1 and δ2 are additional binary variables. It is clear that more binary variables are demanded in the case of more complex PLMFs.
Approaches: We would like to introduce several related definitions before getting to the approaches:
| • | Definition 1: δi or (1-δi) is called a binary item, δi0 {0, 1} |
| • | Definition 2: A binary item group contains all binary-items used to describe a piecewise linear constraint |
| • | Definition 3: Binary item groups expressed in a form of matrix refers to a binary item matrix, in which, a row corresponds to a binary item group, implying that the numbers of matrix rows and columns equal to those of the sub-segments and binary items, respectively |
A crucial step of formulating fuzzy programming with PLMFs is to associate each sub-segment with a constraint, highlighting the assignment of the binary item groups required. In what follows, two approaches are introduced to facilitate the treatment of PLMFs. The first suggests a simple procedure to accommodate the binary item matrix, while the second presents a general formula to deal with the problems.
Considering that two sub-segments connected by a concave point can be described by one binary item and have same upper bound, only PLMFs with convex points are concerned with so as to facilitate the discussion.
Approach 1: The main idea behind this approach is, initially, to establish a binary item matrix based on the numbers of both sub-segments and binary items required, followed by deleting some useless items then, eventually resulting in the binary item groups responsible for describing each sub-segments of the PLMFs considered. Finally, we could formulate the soft constraints through the binary item matrix. In general, the detailed procedures can be addressed as follows:
| Step 1: | Compute θ, the number of binary items required, by θ = [In n/In 2], where n indicates the number of concave points associated with a PLMF |
| Step 2: | Establish the binary item matrix according to θ and the number of sub-segments q (q = n+1) by applying the following rules: In the 1st column δ1 and (1-δ1) are written alternately every 1 row; in the 2nd column, δ2 and (1-δ2) are written alternately every 2 rows; in the 3rd column, δ3 and (1-δ3) are written alternately every 4 rows; …, in the θth column, δθ and (1-δθ) are written alternately every 2θ-1 rows, ultimately resulting in a binary item matrix with q rows and θ columns, as shown in Table 1 |
| Step 3: | Delete the binary items located at row q-2θ-1+1 to 2θ-1 in the last column |
| Step 4: | Formulate each sub-segment as a constraints associated with the satisfaction degree λ, in which, each binary item in a row of the matrix is multiplied with a big positive number in turn and then added on the corresponding membership function |
| Table 1: | Binary item matrix |
| Table 2: | An intermediate binary item matrix |
| Table 3: | Final binary item matrix |
For instance, a procedure towards dealing with a PLMF with 4 concave points is given as follows:
| Step 1: | The number of binary items required is measured by θ = [In 4/ In 2] = 3 |
| Step 2: | Taking account of 5 sub-segments involved, we build a binary item matrix with 5 rows and 3 columns, as shown in Table 2 |
| Step 3: | Rows 2 to 4 of the last column were deleted, eventually attaining the matrix as shown in Table 3 |
| Step 4: | The statement of fuzzy programming is then addressed as follows: |
| (14) |
where, Ui is the upper bound of μi.
In contrast, we also deal with this problem using Ching-Ter=s methodology, whose corresponding models are characterized by:
| (15) |
where, bi is also binary variables. Because δi and bi are binary variables which can take values of 0 and 1 arbitrarily, when b2 = b3 = b4 = b5 = 1, in three particular situations, δ1 = δ2 = 1, δ3 = 1, δ1 = 0 δ2 = 0, δ3 = 1 and δ1 = 1 δ2 = 1 δ3 = 1, (18) can change to be of following type:
| (16) |
Considering that M is a big positive number, satisfaction degree λ becomes unconstrained. While this constraint-free problem would never happen by our methodologies regard to any change of binary variables.
Approach 2: Alternatively, fuzzy programming with PLMFs can be formulated directly by means of the following orthodox equations:
| (17) |
where, Uij is the upper bound of μij, n is the number of convex points, θ = [In n/In 2 ] is the number of binary variables demanded, q is the number of sub-sections of the PLMF.
For example, Eq. 17 accounts for a PLMFs with θ = 4 and n = 8, where, μ1 to μ9 are membership functions of each sub-segment respectively. In this case, unconstrained λ associated with the corresponding fuzzy programming problem could be avoided. Besides, it is observed that 2θ-q constraints are free of the fourth binary items, which implies that θ-1 binary items are demanded only. Undoubtedly, reduction of the number of binary items would help make solving the optimization problem easier:
| (18) |
AN ILLUSTRATIVE EXAMPLE
Consider the following numerical example:
| (19) |
where, all constraints are of soft type. For later comparison, we initially obtained the optimum solutions of the corresponding crisp optimization problem as: x*1 = 15.04, x*2 = 2.25, x*3 = 6.05, x*4 = 20.08, z* = 1305.6. In regard to the soft constraints, we construct unilateral and bilateral Gaussian membership functions, shown as follows:
| (20) |
| (21) |
| (22) |
| Fig. 8: | Piecewise linear membership functions of μg1 |
| Fig. 9: | Piecewise linear membership functions of μg2 |
| Fig. 10: | Piecewise linear membership functions of μh |
where, p1 = p2 = p3L = 100 and p3R = 70. The reference points for the PLMFs were specified as shown in Table 4.
| Table 4: | Reference points of the piecewise linear membership functions |
| Table 5: | Binary variables |
| Table 6: | Solutions of the fuzzy programming problems |
Then we got the PLMFs presented as Eq. 23, 24 and 25, whose profile curves are shown in Fig. 8-10 and the upper bounds of each PLMFs are: U11 = 1, U12 = 0.3649, U21 = 1, U22 = 0.2521, U31 = 0.315, U32 = 1, U3 = 0.1736:
| (23) |
| (24) |
| (25) |
It is clearly observed that 1, 1 and 2 convex points are involved in the three PLMFs, respectively. We calculate the number of binary variables required as θ1 = [In 1/In 2] = 1, θ2 = [In 1/In 2] = 1, θ3 = [In 1/In 2] = 2, which means 4 binary variables are needed to describe the relationship between the sub-segments. The binary variables are listed in Table 5.
Thus, the fuzzy programming formulations are created as follows:
| (26) |
The above nonlinear programming problem was solved using the ALPHAECP solver of GAMS which is always employed to deal with mixed-integer nonlinear programming problems. After 340 iterations, the optimum solution was achieved at δ1 = 0, δ2 = 0, δ3 = 1 and δ4 = 0, as show in the first line of Table 6. In this situation, Eq. 24 can be simplified and re-arranged as follows:
| (27) |
At the optimal point xi* and λ*, the active constraints must satisfy KKT conditions which are also known as the first order necessary conditions of optimality. Regarding Eq. 25, the KKT conditions are expressed by:
| (28) |
where, η1, η2, η3, η4 are the vectors of KKT multipliers corresponding to each constraint. To perform algebraic calculations, the solutions of Eq. 26 could be obtained as η1 = 0, η2 = 0.243, η3 = 0.447 and η4 = 0.31, which implies the optimality of the solutions.
For comparison, we also formulated this problem using regular Gaussian membership functions, the solutions are presented in Table 6. Due to the characteristics of PLMFs, the nonlinearity of the model didn’t be deepened which obtained better solutions.
CONCLUSION
A method of formulating unilateral and bilateral membership functions was presented. Taking advantage of options of reference points in Gaussian membership functions, an approach able to convert unilateral and bilateral membership functions into piecewise linear ones is subsequently introduced. By means of compatible configuration of binary variables, the PLMFs can be represented more efficiently, which helps the corresponding fuzzy optimization formulations prevent constraint-free problems. Compared with conventional modeling methodologies, this contribution demands fewer binary items in some scenarios, possibly reducing the complexity of optimization calculations.