Trends in Applied Sciences Research

Year: 2008 | Volume: 3 | Issue: 2 | Page No.: 154-164
DOI: 10.17311/tasr.2008.154.164

Interactive Bi-level Multiobjective Stochastic Integer Linear Programming Problem

Mervat M.K. Elshafei and M. Salah EL-Sherbeny

Abstract: In this study, consider Bi-level multiobjective stochastic integer linear programming (BL-MOILP) problem with chance constraints. Assume that there is randomness in the right-hand sides of the constraints only and that the random variables are normal distributed. An interactive algorithm for solving such problem is presented. By using the chance-constrained programming technique, the problem converted from probalistic into deterministic bi-level multiobjective integer linear programming (DBL-MOILP) problem. This problem can be transform into separate multiobjective decision making problems and solving it by using ε-constraint method. Finally, an illustrative numerical example is given to demonstrate the obtained results.

Keywords: Bi-level programming, interactive, multiobjective decision-making problem, Stackelberg game, chance-constrained programming, integer programming and branch-and-bound method

INTRODUCTION

Stochastic or probabilistic programming deals with situations where some or all of the parameters of the optimization problem are described by stochastic (or random or probabilistic) variables rather than by deterministic quantities (Rao, 1977; Taha, 1976; Sharif and Saad, 2005). The sources of random variables my be several, depending on the nature and the type of problem. Decision problems of stochastic or probabilistic optimization arise when certain coefficients of an optimization model are not fixed or known but are instead, to some extent, stochastic (or random or probabilistic) quantities. In recent years methods of multiobjective stochastic optimization have become increasingly important in scientifically based decision making involved in practical problem arising in economic, industry, health care, transportation, agriculture, military purposes and technology. A bi-level programming problem is formulate for a problem in which two decision makers (DMs) make decisions successively (Bard, 1983, 1984; Bard et al., 2000; Bialas and Karwan, 1984; Campelo and Scheimberg, 2000; Calvete and Gale, 1999; Marcotte et al., 2001; Sakawa and Nishizaki, 2001; Shi and Xia, 1997, 2001). For example, in a decentralized firm, top management, an executive board or headquarters makes a decision such as a budget of the firm and then each division determines a production plan in the full knowledge of the budget. Many researchers have developed various interactive algorithms for solving multicriteria decision making (MCDM)problem (Sakawa, 1993; Sakawa and Nishizaki, 2001; Shi and Xia, 1997, 2001; Elshafei, 2006).

This study has proposed an interactive algorithm for solving bi-level multiobjective integer linear programming problem with random parameters in the right hand side of constraints. Finally an illustrative numerical example has been given to clarify the solution method.

PROBLEM FORMULATION

be a vector variables indicating the first decision level’s choice and the second level’s choice, n_i ≥ 1, (i = 1,2).

are the first level objective functions and the second level objective functions, N_i ≥ 2, (i = 1,2).

Let the first level decision maker (FLDM) and the Second Level Decision Maker (SLDM) have N₁ and N₂ linear objective functions, respectively.

The Bi-Level multiobjective stochastic integer linear programming problem with random parameters in the right hand side of the constraints (BL-MSILP) can be stated as follows:

subject to

Here (x₁, x₂) is the vector of integer decision variables. Assuming that the decision variables x_j and a_ij are deterministic. Furthermore, P means probability and 0 ≤ α_i≤ 1 is a specified probability value. Assume that the random parameters b_i, (i = 1, 2,…, m) are distributed normally with known means E{b_i}and variances var{b_i} and independently of each other.

Definition 1

For any x₁ (x₁ ∈ G₁ = {x₁ | (x₁, x₂) ∈ G})given by (FLDM), if the decision-making variable x₂ (x₂ ∈ G₂ = {x₂ | (x₁, x₂) ∈ G}) given by (SLDM) is the non-inferior solution of the (SLDM), then (x₁, x₂) is a feasible solution of (BL-MSILP) problem (Shi and Xia,1997).

Definition 2

If is a feasible solution of the (BL- MSILP) problem, no other feasible solution (x₁, x₂)∈ G exists, such that; at least one j(j = 1,2,…, N₁) is strict inequality, then is the non-inferior solution of the (BL-MSIP) problem (Shi and Xia, 1997).

The basic idea in treating (BL-MOSILP) problem is to convert the probabilistic nature of this problem into a deterministic form. Here, the idea of employing deterministic version will be illustrated by using the interesting technique of chance-constrained programming (Rao, 1977; Taha, 1976).

The stochastic constraints:

can be restated as:

where, is a standard normal variable with zero mean and unit variance

The above inequalities can be stated as:

or

The above constraints can be expressed as:

These inequalities will be satisfied only if:

where, is the standard normal value such that φ () = 1-α_i and φ(a) represents the cumulative distribution function of the standard normal distribution evaluated at a. Thus, the stochastic constraint is equivalent to the deterministic linear constraint,

Thus, (BL-MOSILP) problem can be understood as following deterministic bi-Level multiobjective integer linear programming (DBL-MILP) problem:

[1st level]

[2nd level]

subject to

DEFINITIONS AND THEOREMS (Shi and Xia, 1997)

To obtain the solution of (DBL-MILP) problem solving (FLDM) problem and the (SLMD) problem each one separately. In this way, we can quantitatively present satisfactoriness and the preferred solution in view of singular-level multiobjective decision-making problem and introduce several theorems with the help of the quality of ε-constraint method (Rao, 1977; Shi and Xia, 1997) to provide a theoretical basis for upper-level multiobjective decision-making.

Consider a multiobjective decision making (MODM) problem as follows:

Max (f₁(x),…, f_n (x))

subject to

h_j (x) ≥ 0, j = 1,……,q,

where, x denotes the decision making variable and f_i (x), (i = 1,2,…,n) denotes the objective function of the multiobjective decision making problem.

as below:

Definition 3

If x* is a non-inferior solution, then is defined as the satisfactoriness of x* to objective f_i (x).

Definition 4

μ (x*) = Min is defined as the satisfactoriness of non-inferior solution x* to all the objectives.

Definition 5

If x, x* are two non-inferior solution to the objective f_i (x), then x* is more preferred

than

Definition 6

With a certain value s_o given in advance by the decision maker, if non-inferior solution x* satisfies μ(x*) ≥ s_o, then x* is the preferred solution corresponding to the satisfactoriness s_o.

The membership function is given as below:

It is decided according to the decision maker’s requirements. Obviously, (I) meets the two requirements (i) and (ii) for (f_i (x)).

The ε-constraint method (Rao, 1977; Sharif and Saad, 2005) is effective for solving multiobjective decision making problems. The formulation of P (ε_-1) is as follows:

Max f₁(x)

subject to

f_i(x) ≤ ε_i, i = 2,…, n

x ∈Ω

Assume

ε_-1 = (ε₂, …, ε_n),

x/(ε_-1) = {x| f_i(x) ≤ ε_i, i = 2,…, n, x ∈Ω } and

E₁ = {ε_-1 | x^/(ε_-1) ≠ φ (empty set)}.

Theorem 1

If ε_-1 = (ε₂, ε₃, …., ε_n) ∈ E₁, then the optimal solution to P(ε_-1) exists and includes a the non-inferior solution of (MODM) problem.

Corollary

If x¹ is the only optimal solution to P (ε_-1), then x¹ is the non-inferior solution of (MODM) problem.

Given satisfactoriness s, if ≥ s, then by solving (I), obtain that:

f_i (x) = (b_i-a_i) + a_i ≥ (b_i-a_i) s + a_i.

Let δ_i = (b_i-a_i) s + a_i, (i = 1,2,…,n), ε_-1 (s) = (δ_{2, …,} δ_n).

Therefore, we can obtain P (ε_-1(s)), the ε constraint problem including satisfactoriness is as follows P (ε_-1 (s)):

Max f₁(x)

subject to

f_i(x) ≥ δ_i, i = 2,3,…,n,

x ∈ Ω

Theorem 2

If P ((ε_-1 (s)) has no solution or has the optimal solution and f₁() ≤ δ₁, then no non-inferior solution x* exists, such that μ (x*) ≥ s

Theorem 3

Assume s < s₁, if there is no preferred solution to s, then go to s₁.

Theorem 4

Assume is an optimal solution

(i = 1,2,…. n) and ε_-1 = (ε₂, ε₃, …., ε_n), then is still an optimal solution of P (ε_-1).

AN INTERACTIVE MODELS FOR (DBL-MILP) PROBLEM

To solve the (DBL-MILP) problem,one first gets the preferred or satisfactory solutions that are acceptable in rank order to the (FLDM) and then give the (FLDM) variables one by one to the (SLDM) for him or her to seek the solutions by ε-constraints method.and to arrive at the solution that gradually approaches the preferred solution or satisfactory solution to the (FLDM). Finally, the (FLDM) decides the preferred solution of the (DBL-MILP) problem according to his satisfactoriness.

Solving the (FLDM) Problem

The first level decision maker (DBL-MILP) problem is as follows:

subject to

(x₁, x₂) ∈ G^/

To obtain the preferred solution of the (FLDM) problem, transform (1) into the following single objective problem P/(ε_-1 (s)):

subject to

where, s ∈ {1,2,…., N₁} can be taken arbitrary. Problem (2) can be written in the following form:

subject to

where, the constraint γ_j ≤ x_j ≤ B_j, j ∈ J ⊆ { 1,..,n} is an additional constraint on the decision variable x_j and that has been added to the set of constraints of problem (3) for obtaining its optimal integer solution by the branch-and-bound algorithm (Taha, 1976; Rao, 1977). According to the definitions and theorems in section 3, the algorithm steps for solving (3) are as follows:

The Algorithm for solving (FLDM)

Step 1: Set the satisfactoriness. Let s = s_o at the beginning and let s = s₁, s₂,…, respectively.

Step 2: Set the ε-constraint problem P^/(ε_-1 (s)), find the solution of this problem by ignoring the integer condition and use lingo program or any package to solve this problem.

Step 3: If the solution is an integer then go to step 6, otherwise using the branch-and-bound method.

Step 4: If the integer solution has not been reached go to step 5, otherwise go to step 6.

Step 5: If P^/(ε_-1 (s)) problem has no solution or has an optimal solution making then go to step 1, to adjust s = s_j+1 < s. Otherwise, go to step 6.

Step 6: Assuming that an optimal solution of P^/(ε_-1 (s)), judge by theorem 4 whether or not is a noninferior solution of (1). If is a non-inferior solution, turn to step 7. If is inferior solution, there must be a and at least one >; Repeat step 6 with

Step 7: If the decision maker is satisfied with then is a preferred solution and go to step 9. Otherwise, go to step 8.

Step 8: Adjust the satisfactoriness. Let s = s_j+1 > s_j and go to step 2.

Step 9: Stop.

Solving the Second Level Decision Making (SLDM) Problem

According to the interactive mechanism of the (DBL-MILP) problem, the FLDM variables should be given to the (SLDM), hence, the (SLDM) problem can be written as follows:

subject to

This problem will convert into the following single objective function as follows:

subject to

Problem (5) can be written as:

subject to

where, the constraint is an additional constraint on the decision variable x_j and that has been added to the set of constraints of problem (5) for obtaining its optimal integer solution by the branch-and-bound algorithm and our basic thought on solving (6) is to find the second level non inferior solution that is closest to (FLDM) preferred solution

Now, we will test whether is preferred solution to the FLDM or it may be changed, by the following test:

So, is a preferred solution to the (FLDM), which means is a preferred solution of (DBL-MILP) problem, where δ is a small positive constant given by the (FLDM).

INTERACTIVE ALGORITHM FOR SOLVING (DBL-MILP) PROBLEM

Step 1

Set q = 0, solve the 1st level decision-making problem to obtain a set of preferred solutions that are acceptable to the (FLDM); the(FLDM) puts the solutions in order in the format as follows:

Preferred solution,

Preferred ranking (satisfactory ranking),

Step 2

Given to the SLDM, solve the SLDM problem to obtain

Step 3

where, δ^F is a fairly small positive number given by the (FLDM),then go to step 4. Otherwise, go to step 5.

Step 4

If the (FLDM) is satisfied with then is the preferred solution to (DBL-MSIL) problem and go to step 6.Otherwise, go to step 5.

Step 5

Set q = q + 1 and go to step 2.

Step 6

Stop.

NUMERICAL EXAMPLE

Here, we provide a numerical example to clarify the proposed algorithm:

[1st level]

[2nd level]

subject to

P {2 x₁+ x₂≤ b₁} ≥ 0.99, P {2 x₁+ 3 x₂≤ b₂} ≥ 0.90, x₁ ≥ 0, x₁ ≥ 0 and integer.

Suppose that b₁, b₂ are normally distributed random parameters with the following means and variances, E {b₁} = 1, E {b₂} = 3, Var{b₁} = 9, Var{b₂} = 4.

From standard normal tables, we have:

For the first constraint,

For the second constraint,

The equivalent deterministic multiobjective integer linear programming Problem can now be stated as:

[1st level]

[2nd level]

subject to

2 x₁ + x₂≤ 7.99, 2 x₁ + 3 x₂ ≤ 5.57, x₁≥ 0, x₂≥ 0 and integer.

The (FLDM) solves this problem as follows:

Also obtain the solution (2.785, 0), f*₁₂ = 7.59 which is not integer solution, so by using the branch and bound method, the integer solution is x*₁ = 1, x*₂ = 1 and f*₁₂ = 4 = b₁₂ and a₁₂ = 0.

So, (b₁₁, b₁₂) = (7, 4) and (a₁₁, a₁₂) = (0,0).

subject to

2 x₁ + x₂ ≤ 7.99, 2 x₁+ 3 x₂ ≤ 5.57, 2 x₁+ 2 x₂ ≥ 1.2,

x₁ ≥ 0, x₂ ≥ 0 and integer.

Where, δ₁₂ = (b₁₂-a₁₂) s₁ + a₁₂ = 1.2.So the FLDM solution is (2.785, 0) which is not integer, by the branch-and-bound method, the integer solution is (are given by FLMD).

Secondly, the SLMD solve his problem as:

subject to

2x₁+ x₂≤ 7.99, 2 x₁ + 3 x₂≤ 5.57, 4 x₁+2 x₂≥ 3.5, x₁= 2, x₂ ≥ 0, x₂≥ 0 and integer.

Where, δ₂₂ = (b₂₂-a₂₂) s₂ + a₂₂ = 3.5. So the SLDM solution is = (2, 0) and s₂ = 0.35, δ^s = 0.12.

From the following test, find that (2, 0) is a preferred solution to the FLDM

So (2, 0) is a preferred solution to the (BL-MOSILP) problem.

REFERENCES