Bilevel Programming Problem (BLPP) Is a Special Case of Multiobjective Decision Making

INTRODUCTION

Bilevel programming problem (BLPP) is a special case of multiobjective decision making (MODM) problem in a hierarchical decision system. It is actually the most widely used and primitive version of a multilevel programming problem (MLPP) having multiple DMs with multiplicity of objectives in a large hierarchical decision making organization.

In a BLPP, two DMs are located at two different hierarchical decision levels and each one independently controls a vector of decision variables for optimizing individual objective functions, where objectives often conflict each other in the decision making horizon. Although, execution of the decision power is sequential from the upper-level DM (leader) to lower-level DM (follower), the decision of the leader is often affected by the reaction of the follower owing to his/her dissatisfaction with the decision of the leader. As a consequence, decision deadlock often arises and the problem of distribution of proper decision powers toDMs is encountered in most of the hierarchical decision making context.

From the historical perspective, the concept of BLPP was introduced separately by Fortuny-Amat and McCarl (1981)and Candler and Townsley (1982). Thereafter, various version of bilevel programming (BLP) have been studied by Bard (1981), Bialas and Carwan (1982), Bialas and Carwan (1984) and others researchers in this field.

During the last three decades, several solution approaches for BLPPs(Wen, and Hsu, 1991; Biswas and Pal, 2007; Pal and Biswas,2007; Arora and Gupta, 2009; Pal and Biswas, 2014)as well as MLPPs(Bard and Falk, 1982; Biswas and Pal, 2004)have been investigated from the point of view point of their potential use to different real-life decision problem as economic systems, warfare, network design, traffic control,government policy, conflict resolution, and others.

But, in a practical decision situation, the uses of most of the classical approaches lead to the paradox that the leader’s decision power is dominated by the follower. In order to overcome the shortcomings of the classical approaches, fuzzy programming (FP) approaches (Zimmermann, 1987),based on the theory of fuzzy sets, initially introduced by Zadeh (1975) anddeeply studied by Slowinski (1986), Hulsurkar et al. (1997)in the past to solve problems with imprecisely defined data,have been developed(Tiryaki, 2006) to solve hierarchical decision problems. But, the main difficulty with the use of a FP approach to BLPP is that there is a possibility of rejecting the solution again and again by DMs, and re-evaluation of the problem with the elicited membership functions is to be repeatedly made in the solution search process owing to conflicting in nature of the objectives.

To overcome the above difficulty, FGP(Pal, Moitra, & Maulik, 2003) approach to hierarchical decision problems have been studied by Pal & Biswas (2007),Pal & Chakraborti (2013)and others in the past.

Now, most of the methodological developments made for BLPPs and MLPPs in the past are mainly concerned with optimization of hierarchical decision problems with single-objective at each of the decision levels.But, it is to be observed that todays most of the the hierarchical decision problems are with multiplicity of objectives of today at each decision level.

An iterative approach for solving classical Multiobjective BLPP (MOBLPP) has been studied by Shi and Xia (1997). The use of FGP for solving MOBLPPs has been proposed by Biswas & Pal (2007), Pal & Biswas Pal (2007) in the past. In contrast to single-objective BLPPs, methodologies for solving MOBLPPsare yet to be widely circulated in the literature.

However, in most of the decision situations, it is to be realized to the fact that DMs are often faced with the problem of uncertainty to incorporate the parameter values, which are inherent to resource utilization of optimizing objectives in a decision making situation.

To cope with the above situation, the most prominent approach for solving problems with probabilistic data is stochastic programming (SP). The field of SP based on the theory of probability; initially introduced by Charnes and Cooper (1959), as the chance constrained programming (CCP) has been studied(Liu, 2000; Liu, 2002)extensively and applied to various real-life problemby Bravo Ganzalez (2009). The SP deals with the situations where some or all the parameters of an optimization problem are described by stochastic (random / probabilistic) variables rather than deterministic quantities (Rao, 1977). There are several sources for occurrence of random variables, and that depend on how uncertainties are involved there in the decision making environment. In the recent years, the methods of multiobjective stochastic optimization problems have become increasingly important in searching of solutions of practical decisionproblems arising out of economics, industry, healthcare, transportation, agriculture, military operations, and other real-life problems.

Now, it is to be noted that both the probabilistic and fuzzy data are frequently involvedin real-life decision problems, and both the aspects of SP and FP need be taken into accountin actual practice of modeling and solving the and thereby taking proper decisions. However, consideration of both the aspects in a problem creates a great challenge for developing efficient solution methods to deal with both the stochastic and fuzzy terms in actual practice. The constructive modellingaspects on programming problems under randomness and fuzziness were first studied by Luhandjula(1983). The methodological development of fuzzy stochastic programming (FSP) approaches for solving linear programming (LP) problems has been surveyed by Luhandjula(2006).

Although,fuzzy dependent-chance constrained BLPPshave been studied(Gao Liu, 2005; Yang Zhang, 2007)in the past, the extensive study in this area isat an initial stage. Further, the use of FGP method towith chance constrainedBLPPs are yet to circulate in the literature.

Now, GAs (Goldberg, 1989; Deb, 2002) as prominent tools for optimization ofdecision making problems with multiplicity of objectives , i. e., multiobjective decision making (MODM) problems (Pal Gupta, 2008)have been successfully employed to BLPPs (Malhotr, and Arora, 2000)in the past.

The GA based FGP approaches to BLPPs has been studied by Pal & Chakraborti(2013) in the recent past. However, the extensive study on the use of GA based method to solve MOBLPPsis at an early stage.

In this chapter, how GA can be effectively used to solve a MOBLPP with randomized coefficient matrix and resource vector of chance constraints with known probability distribution is consideration. In the proposed solution approach, the notion of the use of mean and variance in CCP is taken into account to convert the defined chance constraints into their equivalent crisp system constraints. Then, the membership functions of the fuzzy goal objectives of both the DMs are defined by introducing fuzzy aspiration level and tolerance limit to each of them. In the solution process, the GA method is efficiently used to solve the BLPP having non-linear characteristics of the defined deterministic constraints.

To illustrate the effectiveness of the proposed approach, a numerical example issolved, and the resultant decision is compared with the solution obtained by using a conventional FP approach studied previously.

PROBLEM FORMULATION

Let X=(x1, x2, …, xn) be the vector ofdecision variables, which areassociated with the two hierarchical decision levels.

Again, in the decision situation, it is assumed that the DMs are motivated to cooperate each other with regard to optimization of controlling objectives of both of them as well asoverall benefit and sustainable growth of the organization. Then, letX1 and X2 be the vectors of decision variables that are controlled by the leader and follower, respectively, and let Z1i and Z2j be the i-th and j-th objective functions of the leader and follower, respectively, and where all the objective functions are linear and bounded. Such a MOBLPPunder a set of chance constraints can be stated as:

Find (X1, X2) so as to:

Max Z1i (X1, X2)=Ci1 X1 + Ci2 X2 ; i = 1, 2, …, N1

X1

and for given X1; X2 solves

Max Z2j (X1, X2) = cj1 X1 + cj2 X2 ; j = 1, 2, …, N2

X2

subject to

(1)

whereX1∩X2= Φ,X1∪X2=X and X={x1, x2, …, xn}S (≠ Φ) Ci1, Ci2, cj1, cj2 are constant vectors. Pr indicates the probabilistically defined constraints, A is a coefficient matrix and b is a resource vector and p (0 <p <1) is the vector of satisficing probability levels defined for randomness ofparameters associated with the constraints set.

Again, it is assumed that the feasible region S (≠ Φ) is bounded to avoid any infeasibility and unbounded situation in the decision search process.

Then, the conversion to crisp equivalent of the chance constraints in (1) is described in the following section.

Deterministic Equivalent of Chance Constraints

The chance constraints set in (1) can be explicitly presented as:

 pi (2)

In the present decision situation, it is assumed that the elements ofthe coefficient matrix A and resource vector b are independent normally distributedcontinuous random variables.

Let and be the mean and variance pairs of the random variables and respectively with the characteristic of normal distribution.

Then, following the notion of distribution function for a random variable, the crisp equivalent of the constraints in (2) can be defined. Let Fi(y) be the distribution function of the i-th random variable bi.

Then, since Fi(y) is a monotonically non-decreasing function, the value of the corresponding variable is determined as:

F-1i () = {Max y / Pr (bi y)  }, 0 < < 1 (3)

where F-1i () is the inverse function of the probability distribution of the random variable .

Now, in the decision situation, either or or both of them simultaneously may become independent random variables.

For simplicity, it is assumed that either or is defined randomly in the decision making context.

• When are only normally distributed random variables,

Thenletting (4)

The mean of is obtained as:

(5)

Sinceare deterministic.

Again, the variance of is found as:

(6)

where, represents the i-th covariance matrix of the order (n×n) for the defined , T means transpose.

Then, following the basic rules of probability theory, the expressions of the chance constraints in (1) can be obtained as:

(7)

where is the standard normal variate with mean zero and variance unity.

Now, realizing the fact that and using the notion of the distribution function defined in (3), the deterministic equivalent of the given chance constraints appear as:

,

i.e., (8)

Here, it is to be observed that, since , follow normal distribution, the covariance terms would be zero.

As such, the expressions in (8) in a simplified version and in non-linear functional form appear as:

(9)

• When i-th resource element in the expression (1) is only random in nature, then using the basic probability rules in an analogous to the above, the deterministic equivalent of the expressions in (1) can be presented as(Hulsurkar et al., 1997):

(10)

The expressions in (10) in a simplified linear form appear as:

, i=1,2,…,m (11)

Now, it is worthy to mention here that when non-linearity in objectives and/or constraints occurs, then computational complexity (Hannan, 1981) is involved in solving optimization problems and computational load as well as inherent error with the use of traditional transformation approach (Kornbluth and Steuer, 1981)generally arises in a practical decision situation.

To overcome the above difficulties, a GA approach as goal satisficers (Deb, 2002) in the notion of goal satisficing philosophy (Simon, 1957) rather than objective optimizer can be effectively used to reach the solution.

The GA scheme adopted in the decision search process is introduced in the followingsection.

DESIGN OF THE GA SCHEME

In the literature of the GAs, there is a number of schemes (Holland, 1975; Goldberg, 1989) for generation of new populations with the use of the different operators: selection, crossover and mutation.Here, real-valued representation of candidate solutions, i.e., real value coded chromosomes are considered in the evaluation process of the problem. In the genetic search process, the simple roulette-wheel scheme (Deb, 2002), arithmetic crossover (Hasan, & Saleh, 2011) for exploration of the promising the search space and uniform mutation (Craenen, Eiben, & Marchiori, 2001) are taken into account in the decision making environment.The fitness score of a chromosome v (say) in evaluating a function, say, based on maximization or minimization of an objective function defined on the basis of DMs’ needs and desires in the decision making context.

However, the basic steps of the GA scheme with the core functions adopted in the solution search process are presented in the following steps.

Algorithmic Steps of the GA Scheme

Step1.Representation and initialization

Let E denote the real-valued representation of chromosome in a population as E=. The population size is defined by pop_size and pop_size chromosomes are randomly initialized in its search domain.

Step2.Fitness function

The fitness score of each individual is evaluated by the defined objective function of the GP formulation of the problem. The fitness value of each individual is determined as:

The best chromosome with largest fitness value at each generation is determined as:

or,,

which depends on the searching of the best or least value of an objective function.

Step3.Selection

The selection process consists of choosing the individuals (the parent solutions) within the population for mating purposes. The Roulette wheel selection scheme (Goldberg, 1989)is used to generate a new population. Here, the selection of two individuals is made on the basis of their respective highest fitness scores.

Step4.Crossover

The parameter is defined as the probability of crossover. The conventional single-point crossover is used in the solution search process. In the crossover mechanism, a chromosome (solution individual) is selected as a parent for producing offspring if, for a defined random number r, r <is satisfied.

Here, when two parents and (the feasible search space) are selected in crossover operation, then the offspringand are produced as:

= =

where, ,, .

Step5.Mutation

Mutation mechanism is applied over the population after performing the crossover operation. It alters one or more genes of a selected chromosome according to mutation process in order to introduce some extra variability and re-introduce the genetic material in the population. As in the conventional scheme, a parameter of the genetic system is defined as the probability of mutation. The mutation operation is performed on a bit - by - bit basis, where for a random number r [0, 1], a chromosome is selected for mutation provided r <.

Step6.Termination

A loop of the Steps 3 to 5 is executed for a certain number of times. Each iteration of the loop is called a generation. The solution search process terminates after a number of generations when the most satisfactory solution is reached.

Now, the model formulation of the problem is described as follows.

FGP PROBLEM FORMULATION

In FGP formulation of the problem, both the objectives and the control vector of the leader are to betransformed into fuzzy goals by means of assigning an imprecise aspiration level to each of them. Then, the defined fuzzy goals are characterized by the membership functions to measuring the degree of achievement of the goals in terms of the associated membership values.

In the present decision situation, individual best decisions of the DMs are introduced as the aspiration levels of the respective objectives, and they are evaluated by using the proposed GA scheme.

Let (i = 1, 2, …, N1) and (j = 1, 2, …, N2) be the individualoptimal values of the defined objectives of leader and follower, respectively, where

and .

Now in a MODM situation, it can easily be realized to the fact that individual achievement of the optimal values of each objective of a DM is not possible in actual practice owing to resource limitations. In such a situation, fuzzy descriptions of objectives of both the DMs as well as the decision vector controlled by the leader would have to be consideredwith regard to achievement of the aspired levels and of objectives of the DMs.

Let (,;) and (, ; ) be theoptimal decisions of the leader and follower, respectively.

Then,fuzzy objective goals appear as:

Z1i ; i = 1, 2, ….., N1

and Z2j; j =1, 2, ….., N2.

Again, since the leader has a higher power of making decision, the decision of the follower actually depends upon the relaxation of the leader’s decision. So, the fuzzy goal for the control vector is obtained as:

X1 .

where refers to the fuzziness of an aspiration level and it is to be understood as ‘essentially greater than’ in the sense of Zimmermann(1987).

In a fuzzy decision situation, certain tolerance limits for goal achievements are considered. Here, the least values of the objectives are considered the lower-tolerance limits for fuzzy goal achievements, they are determined as:

[=Z1i (,)] < and [=Z2j (,)] <

Again, let () be the lower tolerance limit of.

Now, in the decision situation, the fuzzy goals are to be characterized by their respective membership functions.

The characterization of membership functions of the defined fuzzy goals are presented in the following section.

Characterization of membership function

The membership function for the fuzzy objective goal of the leader appears as (Zimmermann, 1987):

(12)

Similarly, the membership function of the fuzzy objective goal of the follower takes the form:

(13)

The membership function for the fuzzy decision of the leader appears as:

(14)

Now in the decision making context, the aim of each of the DMs is to achieve the highest membership value (unity) of each of the objectives to the extent possible. Considering this aspect of a BLPP, FGP seems to be most appropriate to make the decision for proper distribution of decision power to the DMs.

Now, the FGP model formulation is presented in the following section.

FGP model formulation

In FGP formulation, the defined membership functions are transformed into membership goals by assigning the highest membership value (unity) as the aspiration level and introducing under- and over-deviational variables to each of them. Then, minimization of the under-deviational variables of the stated membership goals on the basis of their weights of importance of achieving the goal levels is taken into account.

The minsum FGP formulation can be stated as:

Find so as to:

Minimize