Abstract
In real-world problems, the parameters of optimization problems are uncertain. A class of multilevel linear programming (MLLP) with uncertainty problem models cannot be determined exactly. Hence, in this paper, we are concerned with studying the uncertainty of MLLP problems. The main motivation of this paper is to obtain the solution to a multilevel rough interval linear programming (MLRILP) problem. To obtain that, we start turning the problem into its competent crisp equivalent using the interval method. Moreover, we rely on three methods to address the problem of multiple levels. First, by applying the constraint method in which upper levels give satisfactory solutions that are reasonable in rank order to the lower levels, second, by an interactive approach that uses the satisfaction test function, and third, by the fuzzy approach that is based on the concept of the tolerance membership function. A numerical example is given for illustration and to examine the validity of the approach. An application to deduce the optimality for the cost of the solid MLLP transportation problem in rough interval environment is presented.
Keywords
Introduction
The multilevel linear programming (MLLP) problem is a sequential optimization problem where some of the variables of the upper level are constrained to a lower level to be a solution of a given optimization problem parameterized by the remaining variables [1, 13]. El Sayed et al. [9] modified the TOPSIS approach to solve the stochastic fuzzy multilevel multi-objective fractional decision-making problem. Fathy [14] planned an acceptable resolution procedure supported by the associated interval technique, linearization technique, and fuzzy approach to resolving the fully rough multi-objective multilevel linear fractional programming problem. Researchers have stressed the importance of developing a variety of structure decision-making techniques to handle a large style of management and improvement issues in real-world applications. These applications mostly represent the following areas [15, 31]: supply chain management; network interdiction; traffic and transportation network design; safety and accident management; policy making; energy management; taxation problems; capacitated lot-sizing problems; and so on.
The rough set theory (RST) proposed by Pawlak [23] in 1982 may be regarded as a successful mathematics tool for dealing with analyses of inaccurate and ambiguous data and can be used in machine learning, knowledge discovery and pattern recognition [24, 30]. The most notion in Pawlak’s rough set model is associate equivalence relation. All equivalence classes form a partition of a specific universe. An arbitrary subset enables approximation by utilizing the equivalence classes into two subsets named the lower and upper approximation. The equivalence relationship is a strict condition that may reduce the applications of rough set in real and practical problems. Hence, different extensions of the initial Pawlak’s rough set from the equivalence relation to more general mathematical concepts were developed [4, 26]. The rough intervals (RIs) presented by Rebolledo [25] in 2006 are used to transact with partially unknown or ill-defined parameters and variables. Midya and Roy [20] introduced an analysis of interval programming utilizing rough intervals. Dalic et al. [6] bestowed a novel integrated fuzzy–rough multicriteria decision-making (MCDM) model based on integrated fuzzy and interval rough set theories. In Ammar et al. [3], the fuzzy rough multi-objective problem was reworked into five crisp multi-objective integer linear fractional programming problems, and therefore, the resultant problems square measure was resolved as a crisp integer linear programming problem by using the Dinkelbach concept.
The main contributions that can be achieved by the proposed study are as follows: An MLLP is incorporated to an uncertain problem. Uncertain MLLP is converted into an ordinary problem by applying the interval method [16]. A conceptual study of three optimization algorithms, namely, the constraint method, interactive approach, and fuzzy approach, is proposed for solving transformed MLLP problems. Optimization algorithms are proposed based on rough interval data. The effectiveness of three methodologies is demonstrated through numerical examples. The proposed approaches are applied to the cost of solid multilevel linear programming transportation problem in the rough interval environment. A comparison study is made between the proposed approaches. The modified approaches are provided an appropriate best solution to various MLLP models having rough interval parameters. These approaches can be extended for solving MLLP problems in fully rough interval environment.
In many practical situations, the decision maker may not be in a situation to determine the objective and/or the feasible set accurately but rather can determine them in a rough sense [2, 22]. A class of MLLP with uncertainty, rough data, and problem models cannot be determined exactly. In this paper, our aim is to solve the multilevel rough interval linear programming (MLRILP) problem. In section 2, preliminaries of the rough intervals are given. In section 3, a formulation of the proposed problem will be considered. In section 4, a transformation of the MLRILP problem to a crisp model is obtained. In section 5, we present three different methods to solve the MLRILP problem. In subsection 5.1, the constraint method for the MLRILP problem is discussed. Subsection 5.2 presents an interactive approach for the MLRILP problem. In subsection 5.3, a fuzzy approach for the MLRILP problem is presented. A numerical example is given for illustration and to check the validity of the planned approaches in section 6. An application to deduce the optimality for the cost of the solid MLLP transportation problem in rough interval environment is presented in section 7. Finally, the conclusions are reported in section 8.
Preliminaries
In this section, we introduce some notions and definitions related to the MLRILP problem. The following concepts can be found in [16].
X
R
⩾
R
0
R
iff X(LA) ⩾ 0 and X(UA) ⩾ 0. X
R
⩽
R
0
R
iff X(LA) ⩽ 0 and X(UA) ⩽ 0.
Let I R denote the set of all rough intervals in R. Suppose A R , B R ∈ I R we can write A R = [A LA : A UA ] and B R = [B LA : B UA ] such that A LA = [a LL , a UL ] and A UA = [a LU , a UU ] where a LL , a UL , a LU and a UU ∈ R. where LL, UL, LU, UU to represent the lower-lower, upper-lower, lower-upper, and upper-upper approximations, respectively. Similarly, we can define B LA and B UA .
A
R
=
R
B
R
iff A
LA
= B
LA
and A
UA
= B
UA
. A
R
⩽
R
B
R
iff A
LA
⩽ B
LA
and A
UA
⩽ B
UA
. A
R
⩾
R
B
R
iff A
LA
⩾ B
LA
and A
UA
⩾ B
UA
.
Addition: A
R
⊕ B
R
= [[A
LA
+ B
LA
] : [A
UA
+ B
UA
]] such that Subtraction: A
R
⊖ B
R
= [[A
LA
- B
LA
] : [A
UA
- B
UA
]] such that Multiplication: A
R
⊗ B
R
= [[A
LA
× B
LA
] : [A
UA
× B
UA
]] such that Division: A
R
ø B
R
= [[A
LA
/B
LA
] :] A
UA
/ B
UA
]] such that
Problem formulation and solution concept
The multilevel rough interval linear programming (MLRILP) problem may be written as follows:
⋮
where x
k
… , x
n
solves
subject to
In Equation (1),
The interval Let The optimal solution of each corresponding linear programming (LP) problem of Equation (1), which its optimal value belongs to
The Equation (1) can be rewritten for r
th
-level decision maker (LDM) in the following form:
subject to
Use the interval method [16] to convert the MLRILP problem into two linear programming (LP) problems with interval coefficients. One of these problems is an LP where all its coefficients are upper approximations of RIs, and the other is an LP where all its coefficients are lower approximations of RIs. Let
Lower approximations of RI coefficients of the rth-LDM:
subject to
subject to
After the division of the rough interval coefficient in the objective functions and constraints into upper and lower intervals to build a crisp equivalent model, the following theorem is necessary and useful.
The possibly optimal range of rth-LDM using the interval method [16] can be obtained by obtaining the possibly optimal range of Equation (2), which resulted in the following two LP problems:
Upper approximations of RI coefficients of the rth-LDM:
subject to
subject to
Constraint method for MLRILP problem
The constraint method [29] of multilevel optimization uses the concept of inserting the variable’s value of every higher-level decision maker into his lower-level decision maker to break the difficulty faced by the MLRILP problem.
Solution Algorithm I: Formulate the MLRILP problem as Equation (1). Set r = 1. If the rth -LDM obtains the optimal solution, go to Step 10. Otherwise, go to Step 4. Formulate the rth -LDM problem, then go to Step 5. rth -LDM uses the interval method [16] to convert the lower and upper interval coefficients into equivalent crisp models, which results in four crisp LP problems, called P1, P2, P3 and P4 problems. Solve the resulting linear programming problems to obtain the possibly and surely optimal range solution of the rth -LDM problem; then, go to Step 7. If the optimal solution of the rth -LDM problem is obtained, then go to Step 9; otherwise, go to Step 8. All variables in the objective functions and constraints of the rth -LDM problem must satisfy the bounded variable constraints. The rth -LDM gets the optimal rough solution If r = k, then go to Step 13; otherwise, go to Step 11. Set r = r + 1, then go to Step 12. The rth-LDM defines his/her problem in point of view of the (r-1)th-LDM, and then go to Step 3. The The optimal rough solution of the MLRILP problem is obtained, and go to Step 15. Stop.
Interactive approach for MLRILP problem
In this section, the MLRILP problem is solved by using an interactive approach, as described in [10, 21]. We try to use the same concept to our problem at the beginning. The FLDM gives satisfactory solutions that are reasonable in rank order to the SLDM, and after that, the SLDM takes the satisfactory solutions of the FLDM to obtain the solutions and to gradually obtain the preferred solution of the FLDM. The satisfactory solutions of the FLDM and the SLDM are conveyed to the TLDM, who will obtain the solutions and to gradually obtain the preferred solution of the SLDM. The satisfactory solutions of the FLDM, the SLDM, the TLDM, and the (k - 1) th -LDM are conveyed to the k th -LDM, who will obtain the solutions and to gradually obtain the preferred solution of the (k - 1) th LDM. Finally, the FLDM, the SLDM and the (k - 1) th -LDM decide the preferred solutions of the MLRILP according to the satisfactoriness test functions.
Solution Algorithm II Formulate the MLRILP problem as Equation (1). Set r = 1. If the rth -LDM obtains the optimal solution, go to Step 10. Otherwise, go to Step 4. Formulate the rth -LDM problem, then go to Step 5. rth -LDM uses the interval method [16] to convert the lower and upper interval coefficients into equivalent crisp models, which results in four crisp LP problems, called P1, P2, P3 and P4 problems. Solve the resulting linear programming problems to obtain the possibly and surely optimal range solution of the rth -LDM problem; then, go to Step 7. If the optimal solution of the rth -LDM problem is obtained, then go to Step 9; otherwise, go to Step 8. All variables in the objective functions and constraints of the rth -LDM problem must satisfy the bounded variable constraints. The rth -LDM gets the optimal rough solution If r = k, then go to Step 18; otherwise, go to Step 11. Set r = r + 1, then go to Step 12. The rth-LDM defines his/her problem in point of view of the (r-1)th-LDM, and then go to Step 3. The rth- LDM estimates the value of If If If If The The optimal rough solution of the MLRILP problem is obtained and go to Step 20. Stop.
Fuzzy approach for the MLRILP problem
In this section, the MLRILP problem with r objective functions is solved by using a fuzzy approach as described in [13]. At the beginning, let
The sub-membership functions for the objective functions at the rth-LDM are formulated in the following manner:
Now, we can obtain the solution of the rth-LDM problem by solving the following Tchebycheff problems.
Thus, the solutions of the rth-LDM are
Now, the solutions of the FLDM, SLDM, and k
th
LDM are disclosed. However, solutions are usually different because of the nature of the multilevel objective functions. The FLDM knows that using the optimal decisions
In this way, the range of decision variables
Then, the membership functions of rth-LDM (r = 1, 2, … , k) can be assumed as follows:
Such that at r = k, then
Finally, to generate a satisfactory solution with overall satisfaction for all decision-makers, the following Tchebycheff problems will be solved:
Solution Algorithm III Formulate the MLRILP problem as Equation (1). Set r = 1. If the rth -LDM obtains the optimal solution, go to Step 12. Otherwise, go to Step 4. Formulate the rth -LDM problem, then go to Step 5. rth -LDM uses the interval method [16] to convert the lower and upper interval coefficients into equivalent crisp models, which results in four crisp LP problems, called P1, P2, P3 and P4 problems. Find the best and worst optimum solutions that correspond to each objective function of the rth -LDM problem. Build the membership function of the rth -LDM problem as Equations. (11)–(14). Solve a Tchebycheff problem for all decision-makers problem at each level as Equations (15)–(18). If the optimal solution of the rth -LDM problem is obtained, then go to Step 12; otherwise, go to Step 10. All variables in the objective functions and constraints of the rth -LDM problem must satisfy the bounded variable constraints. The rth -LDM gets the optimal solution If r = k, then go to Step 14; otherwise, go to Step 13. Set r = r + 1, then go to Step 14. Define the value of the control decision variables and the maximum tolerance for the rth -LDM. Build the membership function of the rth -LDM as Equations (19)–(22). Formulate Tchebycheff problems for all decision-makers problems as Equatins (27)–(30). If ω < 0, where The The optimal solution of the MLRILP problem is obtained and go to Step 20. Stop.
To illustrate the use and benefits of using the presented algorithms, for the solution of MLRILP problems, a numerical example is solved using three different computational methods: (a) constraint method, (b) interactive approach, and (c) fuzzy approach.
Consider the following example of a three-level programming problem with rough interval coefficients in the objective functions and constraints (TLRILP):
Where x2, x3 solve
First: (Constraint Approach) Using Theorems (1) and (2), the equivalent crisp problems, which are equivalent to TLRILP problem, can be written as:
1
st
LDM:
Now set
2
nd
LDM:
Now set
3
rd
LDM:
Finally, getting the results are obtained in Table 1.
The optimal rough interval solution of an MLRILP problem using a constraint method
The optimal rough interval solution of an MLRILP problem using a constraint method
Second: (Interactive Approach) By using Theorems (1) and (2), the equivalent crisp problems, which are equivalent to TLRILP problem, can be written as problems P rs , (r = 1, 2 ; s = 1, 2, 3, 4):
First, the 1
st
LDM decides whether the proposed solution
Therefore,
Second, the 2
nd
LDM decides whether the proposed solution
Therefore,
Finally, getting the results are obtained in Table 2.
The optimal rough interval solution of a TLRILP problem using an interactive approach
Third: (Fuzzy Approach) By using Theorems (1) and (2), the equivalent crisp problems, which are equivalent to TLRILP problem, can be written as problems P
rs
, (r = 1, 2 ; s = 1, 2, 3, 4): By using Equations (9)–(12), the FLDM builds the membership functions
Second, the 2
nd
LDM performs the same actions as the 1
st
LDM to obtain the following results:
Third, the 3rd LDM performs the same actions as the 1
st
. LDM to obtain the following results:
Finally, to generate a satisfactory solution with overall satisfaction for all decision-makers, by (25)–(28), the tolerance function is also calculated. We assume the 1
st
LDM’s control decision
Then, the optimal rough interval solution of the TLRILP problem using a fuzzy approach is obtained in Table 3.
The optimal rough interval solution of a TLRILP problem using a fuzzy approach
Comparison Study:
In this part, a comparison will be made between the algorithms used in the three methods, namely, the constraint method, the interactive model, and the fuzzy approach to solving TLRILP problem, by comparing the result in Tables 1, 2, and 3, the result shows that the proposed algorithms for the constraint method and the interactive model are better than the result in the proposed algorithm of the fuzzy approach where the proposed algorithm for the constraint method and the algorithm of the interactive model gave us the same results when using them for solving the TLRILP problem.
Consider Jalil et al.’s example [17] in a rough environment to demonstrate the application of the proposed MLRILP model and solution procedure.
For any firm or organization, the strategy for transportation planning is very important. The main aim is to obtain the optimality of the solid transportation problem (STP). The STP deal with three objectives viz. minimizing the cost, total time, and total number of items defective during transportation. These three objective functions are arranged in a hierarchical manner such that the 1 st LDM is interested in minimizing the cost associated, whereas the 2 nd LDM is interested in minimizing the total time involved and the 3 rd LDM is concerned with minimizing the number of rejected items. Two conveyance options k1 and k2 with capacities c1 and c2 are available to transport the products from i source points with supply capacity ai to j destination points having demand bj. The data for the problem are of continuous type, so all the involved supply, demands, capacities and variables are taken as normal uncertain supply, demands, capacities and variables.
The rough interval coefficient data for the given example are given in Tables 4 to 8.
Transportation costs by conveyance k
r
, (r = 1, 2)
Transportation costs by conveyance k r , (r = 1, 2)
Transportation time by conveyancek r , (r = 1, 2)
Number of defected items by conveyancek r , (r = 1, 2)
Supply availability parameters at origins and demand parameters at the destinations
Parameters of transportation capacities
Applying the steps of Algorithm I and Algorithm II, we obtain the results in Table 9.
The optimal rough interval solution of the decision variables of a solid transportation problem in a rough environment
The optimal rough interval solution of the solid transportation problem in a rough environment is obtained in Table 10.
The optimal rough interval solution of a solid transportation problem in a rough environment
This paper presented three approaches to acquire the solution to the multilevel linear programming (MLLP) problem in which all the parameters are rough intervals. The authors first turned the problem into its respective crisp equivalent using the interval method. Then, the first procedure is followed by using the constraint method, the second procedure by the interactive approach, and the third procedure by the fuzzy approach to find a rough compromise solution for the multilevel rough interval linear programming (MLRILP) problem. The authors stated an example of showing the applicability of the stated procedures for solving the MLRILP problem. The proposed approaches are excellent for solving the MLRILP problem because they can serve DMs by providing an appropriate best solution to a variety of MLP models having crisp or rough interval parameters and variables simply and effectively. Our application problem is deducing the optimality of the solid transportation problem (STP). The optimality of the solid multistate transportation problem was considered by using the constraint method and interactive approach.
