A Necessity Measure of Fuzzy Inclusion Relation in Linear Programming Problems

Abstract

A programming problem with linear equality constraints can be generalised to the one with linear inclusions when coefficients are imprecisely given as possible ranges. In the problem with linear inclusions, the possible ranges of linear function values should always fluctuate within given ranges. In this paper, we investigate the programming problem with linear inclusions with coefficients being triangular fuzzy sets. To treat it, we introduce a new necessity measure, a linear extension of the one defined by the Dienes implication function, for the degree of the inclusions, and formulate a necessity measure maximisation problem. We propose a solution method based on the trade-off ratio and show that the maximisation problem becomes a regular linear programming problem in a particular condition. In general conditions, we also propose an algorithm utilising its properties and give a numerical example to demonstrate the solution procedure.

Supported by JSPS KAKENHI Grant Number JP18H01658.

1 Introduction

In applications, a linear programming problem (LPP) with coefficients imprecisely given by possible ranges can be modelled by linear inclusion relationships. Generally, one can study the set-inclusion constraints by building a maximum range that contains all possible ranges [9]. By utilising the set-inclusion relationships, Bard [1, 2] constructed the LP problems with inexact coefficients described by crisp sets. Furthermore, in the view of interval linear programming, Hladík [3] also considered the same question and tried to solve it by shrinking or expanding the interval space.

However, using set-inclusion constraints is still too rough to describe an acceptable solution. Instead of giving a degree of trade-off ratio, it can only identify whether an inclusion relationship is valid or not. Hence, we need a more comprehensive estimation to assess an acceptable solution.

Negoita [8] firstly considered such a problem by fuzzy sets called robust programming. He introduced fuzzy inclusive constraints expressed by inclusion relations between possible ranges and allowable ranges. Namely, the left-hand side fuzzy sets show the possible ranges with various level of estimation (from the narrowest to the widest) while the right-hand side fuzzy sets shows the allowable range for each different level of possible range estimation. However, he only concentrated on the inclusion relationships of discrete finite h-level sets, making the estimation still too rough. To treat the roughness, Inuiguchi and Tanino [7] applied a necessity measure approach to estimate the degree continuously. Furthermore, Inuiguchi et al. [5] tried several implication functions and modifier functions for more accurate estimation. However, the utilisation of modifier functions makes the model hard to calculate. To overcome the difficulty, Inuiguchi [4] proposed a simplified way to construct a necessity measure representing the decision maker’s requests on fuzzy set-inclusive constraints in the setting of linear programming with uncertain coefficients.

Inspired by the tabular [4], we propose a fuzzy LPP to represent the original problem. Instead of considering the fuzziness representing the ambiguousness, we denote it as one’s preference on the trade-off. For generality, we divide the constraints into hard and soft ones, where the hard is the one that should be fully satisfied, while the soft can be relaxed to a certain extent.

To represent the softness, we utilise symmetric triangular fuzzy numbers, enabling one to build a maximisation problem by the h-level sets. To treat the problem, we convert the set-inclusion constraints to a series of inequalities and form a non-linear model. We show that if only the right-hand-side coefficients contain softness, one can regard the model as a regular LPP by including the degree as one of the state variables. We also study the structure of the non-linear model generally and propose an algorithm linearly.

We organise the paper as follows. In Sect. 2, we give a brief preliminary about the fuzzy LP and NM. In Sect. 3, we propose the method for conversion and give the approach to solve it. In Sect. 4, we give a numerical example for illustrations, and finally, we briefly conclude our research with future work.

2 Preliminaries

2.1 Fuzzy LPP

Since we aim at the solution of an LPP, we regard it as a procedure to solve the following solution set:

$$\begin{aligned} \mathcal S(A,\boldsymbol{b}):=\{\boldsymbol{0} \le \boldsymbol{x}\in \mathbb {R}^n:A\boldsymbol{x} = \boldsymbol{b}\} \end{aligned}$$

(1)

where $A\in \mathbb {R}^{m\times n}$ and $\boldsymbol{b}\in \mathbb {R}^m$ are the coefficients in constraints.

Due to an objective function being trivial, we concentrate on the solution set of the corresponding fuzzy LPP. Since Inuiguchi et al. [6] have illustrated the fuzzy number in details, we only review the h-level set.

Definition 1

(h-level set). An h-level set $[A]_h$ and a strong h-level set $(A)_h$ of a fuzzy subset A are crisp sets defined as below, respectively:

$$\begin{aligned}{}[A]_h := \{r:\mu _A(r)\ge h\}, \quad (A)_h := \{r:\mu _A(r)> h\}, \end{aligned}$$

(2)

where $\mu _A(r)$ denotes the membership function of A.

By Definition 1, it can be inferred that for any fuzzy subset A, $\forall \, 0\le h_1\le h_2\le 1, \ [A]_{h_2}\subseteq [A]_{h_1}$. In a sense, the higher h is, the more precise the information to describe A is. Therefore, one can regard h as the reliability degree to describe a fuzzy subset, and when treating h, it is preferable to have it as large as possible.

By converting the LPP (1) into a fuzzy one, we have the solution set as:

$$\begin{aligned} \mathcal S(\tilde{A},\tilde{\boldsymbol{b}}):=\{\boldsymbol{0} \le \boldsymbol{x}\in \mathbb {R}^n:\tilde{A}\boldsymbol{x} = \tilde{\boldsymbol{b}}\}, \end{aligned}$$

(3)

where $\tilde{A}\subseteq \mathbb {R}^{m\times n}$ and $\tilde{\boldsymbol{b}}\subseteq \mathbb {R}^m$ denote the fuzzy coefficients.

Since $\mathcal S(\tilde{A},\tilde{\boldsymbol{b}})$ becomes a fuzzy subset, we prefer a non-empty one with the greatest reliability degree, which is estimated by a necessity measure.

2.2 Necessity Measure

Possibility measure (PM) and necessity measure (NM) are techniques to measure the relation between two events by logical reasoning. Mathematically, given the information $r\in A$, a possibility (necessity) measure is to measure how possible (necessary) it can be for the condition $r\in B$.

Since PM is too weak, we only give a review of NM. Intuitively, an NM should follow the remark [5] below:

Remark 1

An NM should follow that

• (i) $N_A(B)=1$ iff $\mathrm {cl}(A)_0\subseteq [B]_1$,

• (ii) $N_A(B)>0$ iff $[A]_1\subseteq \mathrm {cl}(B)_0$,

where $\mathrm {cl}(\cdot )$ denotes the closure of a set.

In Remark 1, the first condition means for all $x\in A$ in the weakest sense implies $x\in B$ in the strongest sense, and the second condition means for all $x\in A$ in the strongest sense implies $x\in B$ in the weakest sense. Since there exist multiple ways to define an NM, we review the original one by using membership functions.

Definition 2

(Necessity Measure). An NM of a fuzzy subset B on another fuzzy subset A, which measures what extent $x\in B$ is certain when given $x\in A$ or what extent $x\in A$ implies $x\in B$, is defined as

$$\begin{aligned} N_A(B) = \inf _{x\in X} I(\mu _A(x), \mu _B(x)), \end{aligned}$$

(4)

where $I: [0,1]\times [0,1]\rightarrow [0,1]$ is an implication function (IF) and satisfies $I(0,0)=I(0,1)=I(1,1)=1$ and $I(1,0)=0$.

The most wide-spread type is the one using Dienes IF as $I^D(a,b) = \max \{1-a,b\}$ such that $N^D_A(B) = \inf _{x\in X}\max \{1-\mu _A(x),\mu _B(x)\}$. If one prefers to use the h-level set to represent the Dienes type, we have the result with its proof found in [6].

Proposition 1

For the NM using Dienes IF, we have:

$$\begin{aligned} N^D_A(B) \ge h \iff \mathrm {cl}((A)_{1-h}) \subseteq [B]_h \end{aligned}$$

(5)

Proposition 1 suggests the way to use h-level sets to accomplish an NM, which is more comprehensive than using membership functions. For example, the necessity measure using Gödel IF [5] can be expressed more intuitively by h-level sets as $N^G_A(B) = h^* \iff \forall h < h^*, \ (A)_h \subseteq (B)_h$.

3 Model Conversion

3.1 Fuzzy LPP by Inclusion Relation

As Remark 1 shows the methodology of an NM by h-level sets, we notice that it is possible to have a more general expression. Instead of using a single h in an NM, we can separate it into two variables at both sides of the equation. Namely, we construct a fuzzy inclusion relationship of $[A]_{1-v}\subseteq [B]_w$ with two h-levels v and w. Hence, we have the following lemma¹.

Lemma 1

An inclusion measure $[A]_{1-v}\subseteq [B]_w$ where $v,w\in [0,1]$ implies $[A]_{1-{v'}}\subseteq [B]_{w'}$ for all $v'\le v$ and $w'\le w$.

Proof

It is apparent that $\forall v'\le v, \ [A]_{1-v'}\subseteq [A]_{1-v}$ and $\forall w'\le w, \ [B]_w\subseteq [B]_{w'}$, which gives out the final result. $\blacksquare$

Unfortunately, such a manipulation constructs a multi-objective problem. Hence, we use weighted factors to convert it back to a single one, which gives out the following problem equivalent to Model (3).

$$\begin{aligned} \max _{\boldsymbol{0} \le \boldsymbol{x}\in \mathbb {R}^n}\{\alpha v+\beta w: [A]_{1-v}\boldsymbol{x} \subseteq [\boldsymbol{b}]_w, \ v, w\in [0,1]\}, \end{aligned}$$

(6)

where $\alpha$ and $\beta$ are non-negative constants and $\alpha + \beta = 1$.

Moreover, for the simplification of using h-level sets in a fuzzy LPP, we prefer the fuzzy coefficients all being symmetric triangular fuzzy numbers, which are defined as

Definition 3 (Symmetric Triangular Fuzzy Number)

In this paper, we define a symmetric triangular fuzzy number as a fuzzy subset with symmetric and linear reference functions. Moreover, it could always be re-written by its h-level sets as

$$\begin{aligned}{}[A]_h = [A^c-(1-h)A^r,A^c+(1-h)A^r] \end{aligned}$$

(7)

where $A^c$ and $A^r$ denote the centre and radius of $\mathrm {cl}((A)_0)$, respectively. Mathematically, they equal to:

$$\begin{aligned} A^c = \frac{1}{2}(\sup {(A)_0} + \inf {(A)_0}), \ A^r = \frac{1}{2}(\sup {(A)_0} - \inf {(A)_0}) \end{aligned}$$

3.2 Conversion Principles

Before continuing the procedure of solving the fuzzy problem, it is essential to have a discussion on the principle of conversion.

At first, if the original LPP is infeasible, the result of Problem (6) should always be strictly less than 1. If it equals to 1, then $v, w = 1$, which indicates there exists a feasible solution $\boldsymbol{x} \ge \boldsymbol{0}$ such that $[A]_0 \boldsymbol{x} \subseteq [\boldsymbol{b}]_1$. According to Remark 1, it implies the necessity measure is 1, which contradicts the premise that the LP problem is infeasible.

Then, by the inclusion relation of two interval sets as $A\subseteq B \iff A^L \ge B^L \ \& \ A^U \le B^U$, as well as the assumption such that A and B are symmetric triangular fuzzy subsets, we have the following conclusion that for all $i\in \{1,2,\ldots ,m\}$ and $j\in \{1,2,\ldots ,n\}$,

• (i) The larger $\mathrm {cl}((\boldsymbol{b}_i)_0)$ is, the easier to have a solution.

• (ii) The smaller $\mathrm {cl}((A_{ij})_0)$ is, the easier to have a solution.

Due to the complexity, one should not try to enlarge $\mathrm {cl}((A)_0)$. Alternatively, keeping A being constant may be a better choice for both model construction and calculation. Because of this, it is preferred to set $\beta >\alpha$, and when A is constant, we set $\alpha =0$.

Hence, to use the fuzziness in representing the preference of a decision-maker, one should follow the several principles in the conversion.

• (i) If a constraint is a hard one, keep the original coefficients constant and do not apply fuzziness on it.

• (ii) If a constraint is a soft one, convert the coefficients into symmetric triangular fuzzy subsets.

• (iii) Focus on $\boldsymbol{b}$ preferentially instead of A, and remember that the softer a constraint is, the larger $\mathrm {cl}((\boldsymbol{b})_0)$ should be.

After the conversion to the fuzzy problem in Model (6), we can continue to the solving approach.

4 Algorithm for the Fuzzy LP

Instead of considering the general condition with both fuzzy A and $\boldsymbol{b}$, it would be better to analyse the problem with only either of them at first. As it is indicated that focusing on $\boldsymbol{b}$ is preferential, we assume that only $\boldsymbol{b}$ contains fuzzy coefficients, which gives a constant A.

4.1 Special Case with Constant A

Assume a decision-maker has already set up fuzzy coefficients $\boldsymbol{b}$ with a constant matrix A, then Problem (6) equals to:

$$\begin{aligned} \begin{aligned} \max&\,\, w \\ \text {s.t. }&-A_s \boldsymbol{x} \le -[\boldsymbol{b}_s]_w^L \\&\quad \ A_s \boldsymbol{x} \le \ \ [\boldsymbol{b}_s]_w^U \\&\quad \ A_h \boldsymbol{x} = \quad \boldsymbol{b}_h \end{aligned} \end{aligned}$$

(8)

where $A_s$ and $A_h$, $\boldsymbol{b}_s$ and $\boldsymbol{b}_h$ represent the soft and hard constraints, respectively.

Since each fuzzy entry in $\boldsymbol{b}$ is a symmetric triangular fuzzy number, one can write the h-level set by Definition 3 as $\forall \, h\in (0,1],$

$$\begin{aligned}{}[\boldsymbol{b}]_h = [\boldsymbol{b}^c - (1-h)\boldsymbol{b}^r, \boldsymbol{b}^c + (1-h)\boldsymbol{b}^r] \end{aligned}$$

(9)

where $\boldsymbol{b}^c$ denote the only entry in $[\boldsymbol{b}]_1$ and $\boldsymbol{b}^r$ denotes the radius of $\mathrm {cl}((\boldsymbol{b})_0)$.

Consequently, we have the following model equivalent to Problem (8):

$$\begin{aligned} \begin{aligned} \max&\,\, w \\ \text {s.t. }&\quad \, A_h \boldsymbol{x} = \ \ \boldsymbol{b}_h \\&-A_s \boldsymbol{x} \le -\boldsymbol{b}^c_s + (1-w) \boldsymbol{b}^r_s\\&\quad \, A_s \boldsymbol{x} \le \ \ \, \boldsymbol{b}^c_s + (1-w)\boldsymbol{b}^r_s \end{aligned} \end{aligned}$$

(10)

By denoting w as a state variable, Problem (10) becomes a regular LPP. If it is infeasible, the tolerance given to $\boldsymbol{b}$ is still too narrow to make LPP (1) feasible even in the worst case.

4.2 General Case

After having the result with a constant A, we can proceed to study the situation with a fuzzy one. Similar to Problem (8), let us assume a decision-maker has set up $\alpha$, $\beta$ and the symmetric triangular fuzzy entries in A and $\boldsymbol{b}$, then the model becomes:

$$\begin{aligned} \begin{aligned} \max&\,\, \alpha v + \beta w \\ \text {s.t. }&A_h \boldsymbol{x} = \ \ \boldsymbol{b}_h \\&(-A^c_s+vA^r_s) \boldsymbol{x} \le -\boldsymbol{b}^c_s + (1-w) \boldsymbol{b}^r_s\\&(A^c_s+vA^r_s) \boldsymbol{x} \le \boldsymbol{b}^c_s + (1-w) \boldsymbol{b}^r_s \end{aligned} \end{aligned}$$

(11)

Therefore, Problem (11) is equivalent to:

$$\begin{aligned} \max \{\alpha v + \beta w:(A^1+vA^2) \boldsymbol{x} + \boldsymbol{b}^2w = \boldsymbol{b}^1 + \boldsymbol{b}^2\} \end{aligned}$$

(12)

where $A^1, \ A^2, \ \boldsymbol{b}^1, \ \boldsymbol{b}^2$ are conveniently defined from Problem (11).

Since Problem (12) is non-linear, we may have to apply some non-linear techniques for it. However, if we regard v or $\boldsymbol{x}$ as a constant variable at a specific step during the calculation, the system becomes linear. As an linear problem tends to be simpler than a non-linear one, solving the problem linearly is preferential. Hence, before applying non-linear algorithms directly, we prefer to do some analysis on Problem (12) at first.

Assume that we already have a pair of $v^*$ and $w^*$ at a specific step, and we want to improve the objective value. However, we cannot increase both $v^*$ and $w^*$ simultaneously because they are the intermediate solutions to Problem (12). Hence, the only way is to increase $v^*$ with sacrificing $w^*$ or the opposite direction. Since the situation with constant A gives the preference to have a larger w and $\alpha < \beta$, we usually have a large $w^*$ and a small $v^*$ at startup. Hence, let us consider the one by improving $v^*$ and sacrificing $w^*$.

Let $\varDelta v > 0$ and $\varDelta w > 0$ denote the improvement such that $\alpha (v^*+\varDelta v)+\beta (w^*-\varDelta w) > \alpha v^* + \beta w^*$, which results in $\varDelta w < (\alpha / \beta )\varDelta v$. Moreover, to make the analysis more illustrative, we only consider the soft constraints and remove the slack variables in Problem (12). Then we have the constraints as:

$$\begin{aligned} (A^1_s+vA^2_s) \boldsymbol{x} + \boldsymbol{b}^2_s w \le \boldsymbol{b}^1_s + \boldsymbol{b}^2_s \end{aligned}$$

(13)

By adding $\varDelta v$ and $\varDelta w$, Constraint (13) becomes:

$$\begin{aligned} (A^1_s+v^*A^2_s) \boldsymbol{x} + \boldsymbol{b}^2_s w^* + \varDelta v A^2_s x - b^2_s \varDelta w \le \boldsymbol{b}^1_s + \boldsymbol{b}^2_s \end{aligned}$$

(14)

To avoid the possibility that $\boldsymbol{x}$ may become infeasible, let $\varDelta v, \varDelta w \rightarrow 0^+$. Then inequalities in (14) becomes $\varDelta v A^2_s x \le b^2_s \varDelta w$. Combined with $\varDelta w < (\alpha / \beta )\varDelta v$, it becomes the one as below:

$$\begin{aligned} A^2_s \boldsymbol{x} < \frac{\alpha }{\beta } \boldsymbol{b}^2_s \end{aligned}$$

(15)

Condition (15) implies that, if the current solution $\boldsymbol{x}$ does not satisfy it, then $v^*$ and $w^*$ at current step are already optimal to Problem (12) and cannot be improved. Due to $A^2_s$, $\boldsymbol{x}$ and $b^2_s$ being all non-negative, Condition (15) is usually hard to be achieved, especially with a large ratio $\alpha / \beta$.

Therefore, we can have the algorithm as below:

5 Numerical Example

We propose the following example:

$$\begin{aligned} \text {Find }&\boldsymbol{0} \le \boldsymbol{x} \in \mathbb {R}^n \\ \text {s.t. }&3 x_1 + 4 x_2 = 7 \\&9 x_1 + 8 x_2 = 16 \\&x_1 - x_2 = 1 \end{aligned}$$

Since the number of constraints is over the variables, the system is obviously infeasible. At first, we only consider the right-hand-side vector being fuzzy one. Assuming Constraint 1 is a hard one, while Constraint 2 has higher priority than Constraint 3, we give 2 and 3 as $(16,14,18)_{LL}$ and $(1,-3,5)_{LL}$, respectively. Hence we have the following system by introducing slack variables:

$$\begin{aligned} \max \;&w\in [0,1] \\ \text {s.t. }&\left[ \begin{array}{rrr} 3 &{} 4 &{} \ \ 0 \\ -9 &{} -8 &{} 2 \\ 9 &{} 8 &{} 2 \\ -1 &{} 1 &{} 4 \\ 1 &{} -1 &{} 4 \end{array}\right] \left[ \begin{array}{c} x_1 \\ x_2 \\ w \end{array}\right] + \left[ \begin{array}{c} 0 \\ y_1 \\ y_2 \\ y_3 \\ y_4 \end{array}\right] = \left[ \begin{array}{r} 7 \\ -16 + 2 \\ 16 + 2 \\ -1+4 \\ 1+4 \end{array}\right] \end{aligned}$$

By the Simplex method, the solution is $w = 0.6935$ with the solution being $x_1 = 0.871, x_2 = 1.097$.

If one sets $\alpha = 0.05$ and $\beta = 0.95$, and considers fuzziness in A with $A_{21} = (9,8.95,9.05)_{LL}$, $A_{22} = (8, 7.98,9.02)_{LL}$ and $A_{31} = (1,0.999,1.001)_{LL}$, then the Model becomes:

$$\begin{aligned} \max \;&0.05v + 0.95w \\ \text {s.t. }&\left[ \begin{array}{rrr} 3 &{} 4 &{} \ \ 0 \\ -9 &{} -8 &{} 2 \\ 9 &{} 8 &{} 2 \\ -1 &{} 1 &{} 4 \\ 1 &{} -1 &{} 4 \end{array}\right] \left[ \begin{array}{c} x_1 \\ x_2 \\ w \end{array}\right] + v \left[ \begin{array}{cc} 0 &{} 0 \\ 0.05 &{} 0.02 \\ 0.05 &{} 0.02 \\ 0.001 &{} 0 \\ 0.001 &{} 0 \\ \end{array}\right] \left[ \begin{array}{c} x_1 \\ x_2 \end{array}\right] + \left[ \begin{array}{c} 0 \\ y_1 \\ y_2 \\ y_3 \\ y_4 \end{array}\right] = \left[ \begin{array}{r} 7 \\ 14 \\ 18 \\ 3 \\ 5 \end{array}\right] \end{aligned}$$

By Algorithm 1, we first solve $v^*=0$ and $w^*=0.6935$ with the solutions being $x_1 = 0.871, x_2 = 1.097$. Then, we check Condition (15), where in this example, $A^2_s = [0.05 \ 0.02; \ 0.001 \ 0]$, $\boldsymbol{b}^2_s = [2;\ 4]$, and $\alpha / \beta =0.05/0.95$. Hence we find that $A^2_s \boldsymbol{x} < (\alpha / \beta ) \boldsymbol{b}^2_s$, which means we can do the improvement.

The following table is the result, which implies $v^* = 1$ and $w^* = 0.6861$, and the optimal solution is $x_1 = 0.854, \ x_2 = 1.109$.

$\quad v^* \quad$	$\quad \quad w^* \quad \quad$	$\quad \alpha v^* + \beta w^* \quad$	$\quad \quad x_1 \quad \quad$	$\quad \quad x_2 \quad \quad$
0	0.6935	0.6588	0.871	1.097
1	0.6861	0.7018	0.854	1.109
0.5	0.6898	0.6803	0.863	1.103

6 Conclusion

In this paper, we present a fuzzy model for an LPP with linear equalities. To get a desired solution, we utilise fuzziness to imply one’s preference and priority, which results in an NM based on an h-level set. we obtain a non-linear programming problem, which can be linear if we only consider the right-hand-side part containing fuzziness. To solve the system, we first solve the linear case by standard LP techniques. Instead of applying non-linear tools directly, we analyse the structure of the system at first. The analysis suggests that we can still deal with it linearly, where we find an extra condition to identify whether it is possible to improve the optimal value. To illustrate our work, we give a numerical example in both situations.

For future progress, we separate our work into two sections. The first one is concerned with computational complexity. Since it still needs a bisection method to get the solution, we wonder if it is possible to have a direct one without iteration. As the space formed by w and v depends on the solved solution $\boldsymbol{x}$, we do not know whether it is always connected and convex. If it is, we can accomplish our goal with $v=0$ and $v=1$. However, if it is not, the algorithm may not give a globally optimised solution.

The second one is concerned with the solution set. Since we consider a fuzzy LPP to treat an infeasible LPP, we always have a fuzzy solution set. However, in this paper, we only solve one solution with the most significant reliability degree. Namely, we only solve one fuzzy solution in a fuzzy solution set, which is not enough for some situations. Hence, the result of the whole fuzzy solution set would become our goal of the following research and study.