^{1}

^{2}

Multi - objective optimization problem (MOOP) is an important class of optimization problem that ensures users to model a large variety of real world applications. In this paper an advanced transformation technique has been proposed to solve MOOP. An algorithm is suggested and the computer application of algorithm has been demonstrated by a flow chart. This method is comparatively easy to calculate. Applying on different types of examples, the result indicate s that the proposed method gives better solution than other methods and it is less time consuming. Physical presentation and data analysis represent the worth of the method more compactly.

Multi-objective optimization (MOO) is an effective technique for studying optimal trade off solutions that balance several criteria. The fundamentals and applications of MOO have been already explored in great detail [

To solve multi-objective linear programming problems, various types of methods have been proposed by various scholars, such as Mean and median method by Sulaiman and Sadiq [

On the other hand, Linear fractional programming problem has been solved by different researchers by different techniques, for example, A new procedure proposed by Tantawy [

Many research scholars have solved multi-objective quadratic programming problem by applying several methods. We include some of them. Optimal cutting plane procedure [

The larger the size of the problem, the greater the number of inefficient solution generated and thus the slower the convergence of the algorithm. To overcome this problem, we propose an advanced transformation technique. We test the capabilities of this proposed technique drawing a comparison with other techniques.

In this paper, we focus our interest on multi-objective quadratic programming problem (MOQPP) where several quadratic objectives are to be optimized subject to a set of linear constraints and nonnegative integer variables. The optimization software package, namely AMPL has been employed in the computation.

Sen proposed a method of multi-objective programming for achieving several conflicting objectives simultaneously [

This study has presented MOQPP and proposed an advanced transformation technique to solve it. The result is compared with two different techniques such as harmonic average technique and modified harmonic average technique. The comparison table shows the effectiveness of the proposed method. The proposed technique is easier to realize and less time consuming. No matter how complex the problem, this proposed method can be applied. Physical interpretations have been presented and data analysis has been discussed for more convenience.

Multi-objective optimization is an area of multiple criteria decision making that is concerned with mathematical optimization problems involving more than one objective function to be optimized simultaneously.

Mathematically, multi-objective decision making problems can be expressed as:

Max / Min [ f 1 ( x ) , f 2 ( x ) , ⋯ , f k ( x ) ]

Subject to

x ∈ X = { x | g h ( x ) : { ≥ , = , ≤ } 0 , h = 1 , 2 , ⋯ , m }

where, f j ( x ) = Objective for maximization , j ∈ J

f i ( x ) = Objective for minimization , i ∈ I

The problem consists of n decision variables, m constraints and k objectives. f j ( x ) , f i ( x ) and g h ( x ) ∀ i , j , h might be linear or nonlinear.

Mathematically, the multi-objective linear programming problem (MOLPP) can be defined as:

Max / Min f i = C i x + α i ,

And mathematically the multi-objective quadratic programming problem (MOQPP) can be stated as:

Max / Min f i = 1 2 x T P i x + C i T x

Subject to

A x [ ≤ = ≥ ] B

x ≥ 0

i = 1 , ⋯ , r for maximization and i = r + 1 , ⋯ , s for minimization

where x is an n-dimensional vector of decision variables, P is a ( n × n ) symmetric matrix of coefficients. A is ( m × n ) matrix of coefficients, B and C are n-dimensional vector of constants. α i ( i = 1 , ⋯ , s ) are scalar constants. All vectors are assumed to be column vectors unless transposed.

A multi-objective programming (MOP) is formulated and optimized under common constraints. The mathematical form of MOP is described as:

Optimize Z = [ Max z 1 , Max z 2 , ⋯ , Max z r , Min z r + 1 , ⋯ , Min z s ]

Subject to

A x [ ≤ = ≥ ] b

x ≥ 0 (3.1)

In this method, all objective functions need to be maximized or minimized individually by Simplex method or by any other method. By doing this the individual optima are obtained for each objective function separately as:

z optima = { α 1 , α 2 , ⋯ , α s }

The optimum value of the objective function α i ( i = 1 , 2 , ⋯ , s ) may be positive or negative.

These values are used to form a single objective function by adding (maximum values) and subtracting (minimum values) of each result then dividing each z i by α i . The function is formulated as:

Max Z = ∑ i = 1 r z i α i − ∑ i = r + 1 s z i α i

Subject to the same constraints as Equation (3.1).

To make the objective function dimension free, the integrated objective function was summarized by weighting each objective function by inverse of its optima. Hence the integrated objective function is formulated without facing any complex with objective functions of different dimensions.

Then the single objective optimization problem is solved by simplex method. This method is known as Chandra Sen’s approach.

Harmonic Mean: Harmonic mean of a set of observations is defined as the reciprocal of the arithmetic average of the reciprocal of the given values. If x 1 , x 2 , ⋯ , x n are n observations then

Harmonic Mean (HM) = n ∑ i = 1 n ( 1 x i )

It provides a more reliable result when the results to be achieved are the same for the various mean adopted.

The steps to calculate the harmonic mean are as follows:

Step 1: Finding the reciprocal of the given values.

Step 2: Calculating the average for the reciprocals obtained in step 1.

Step 3: Finally calculate the reciprocal of the average obtained from step 2.

Multi-objective optimization problem given in (3.1) can be translated by harmonic average technique as:

Max Z = ∑ i = 1 r z i H M 1 − ∑ i = r + 1 s z i H M 2

where, H M 1 = r ∑ i = 1 r ( 1 / α i ) , H M 2 = s − r ∑ i = r + 1 s ( 1 / α i ) .

Subject to same constraints as Equation (3.1).

H M 1 is the value of harmonic mean of maximized α i ( i = 1 , 2 , ⋯ , r ) and H M 2 is the value of harmonic mean of minimized α i ( i = r + 1 , ⋯ , s ) . The values of H M 1 and H M 2 may be positive or negative. If they are negative we consider the absolute values of H M 1 and H M 2 .

Some difficulties occur when calculating with harmonic mean. The harmonic mean is greatly affected by the values of the extreme items. It can’t be able to calculate if any of the item is zero. This calculation is cumbersome as it involves the calculation using reciprocals of the items.

According to modified harmonic average technique multi-objective optimization problem given in (3.1) can be converted into a single objective function as:

Max Z = ∑ i = 1 r z i − ∑ i = r + 1 s z i H M

where

H M = 2 1 H m 1 + 1 H m 2

and

H m 1 = min { α i ; ( i = 1 , 2 , ⋯ , r ) } ,

H m 2 = min { α i ; ( i = r + 1 , ⋯ , s ) }

Subject to same constraints as Equation (3.1).

H m 1 is the minimum value of maximized α i ( i = 1 , 2 , ⋯ , r ) and H m 2 is the minimum value of minimized α i ( i = r + 1 , ⋯ , s ) . The steps to calculate the harmonic mean are as follows:

Step 1: Find the minimum optimal value of the maximization problems.

Step 2: Find the minimum optimal value of the minimization problems.

Step 3: Calculate the average for the reciprocals obtained in step 1 and step 2.

Step 4: Finally calculate the reciprocal of the average obtained from step 3.

Modified harmonic average technique gives better solution than harmonic average technique.

Multi-objective optimization problem can be defined as:

Max / Min [ z 1 , z 2 , ⋯ , z s ]

Subject to

A x { ≥ , = , ≤ } b , x ≥ 0 (4.1)

Suppose we optimize all the objective functions individually and obtain the values

Max z 1 = α 1

Max z 2 = α 2

⋮

Max z r = α r

Min z r + 1 = α r + 1

⋮

Min z s = α s

where α i are the values of objective functions.

We require the common set of decision variables to be the best compromising optimal solution. Here we can determine the common set of decision variables from the following combined objective function.

By our proposed Advanced transformation technique, we can obtain the single objective function as follows:

Max Z = ∑ i = 1 r z i − ∑ i = r + 1 s z i O A T

where O A T = 1 1 / m and m = min { m 1 , m 2 } .

where m 1 = min { α i } , ∀ i = 1 , ⋯ , r .

m 2 = min { α i } , ∀ i = r + 1 , ⋯ , s

Subject to the same constraints as mentioned in (4.1).

Step 1: Find the value of each objective function which is to be maximized or minimized.

Step 2: Solve the first objective function by mathematical programming language AMPL.

Step 3: Assign a name to the optimum value of first objective function z 1 by α 1 .

Step 4: Repeat step-2 for i = 2 , 3 , ⋯ , s .

Step 5: Select m 1 = min { α i } , ∀ i = 1 , ⋯ , r and m 2 = min { α i } , ∀ i = r + 1 , ⋯ , s .

Step 6: Select m = min { m 1 , m 2 } and calculate O A T = 1 1 / m .

Step 7: Optimize the combined objective function as Max Z = ∑ i = 1 r z i − ∑ i = r + 1 s z i O A T .

Under the same constraints by repeating Steps 2 & 3.

Consider the following Multi-Objective Quadratic Programming problem with linear constraints:

Max Z 1 = 4 x 1 + 2 x 2 − x 1 2 − x 2 2 + 5

Max Z 2 = 2 x 1 + x 2 − x 1 2

Min Z 3 = 6 − 6 x 1 + 2 x 1 2 − 2 x 1 x 2 + 2 x 2 2

Min Z 4 = 2 x 1 + 3 x 2 − 2 x 1 2

s/t x 1 + 4 x 2 ≤ 9

x 1 + x 2 ≤ 3

3 x 1 + 2 x 2 ≤ 8

x 1 , x 2 ≥ 0

• AMPL:

After finding the value of each of individual objective functions by using AMPL, the numerical results are given in

i | Z i | x i | φ i | O A i | O L i |
---|---|---|---|---|---|

1 | 10 | (2, 1) | 10 | 10 | |

2 | 3.0156 | (0.875, 2.0313) | 3.0156 | 3.0156 | |

3 | 15 | (0, 2.25) | 15 | 15 | |

4 | 6.9453 | (0.3125, 2.1719) | 6.9453 | 6.9453 |

• Chandra Sen’s Techniques:

By Chandra Sen’s Approach,

Max Z = ∑ k = 1 r Z k | φ k | − ∑ k = r + 1 s Z k | φ k |

Max Z = Z 1 φ 1 + Z 2 φ 2 − Z 3 φ 3 − Z 4 φ 4 = 4 x 1 + 2 x 2 − x 1 2 − x 2 2 + 5 10 + 2 x 1 + x 2 − x 1 2 3.0156 − 6 − 6 x 1 + 2 x 1 2 − 2 x 1 x 2 + 2 x 2 2 15 − 2 x 1 + 3 x 2 − 2 x 1 2 6.9453 = 1.1734 x 1 + 0.0968 x 2 − 0.2751 x 1 2 − 0.2333 x 2 2 + 0.1333 x 1 x 2 + 0.1

Using Chandra Sen’s Approach, the system becomes,

Max Z = 1.1734 x 1 + 0.0968 x 2 − 0.2751 x 1 2 − 0.2333 x 2 2 + 0.1333 x 1 x 2 + 0.1

Subject to

x 1 + 4 x 2 ≤ 9

x 1 + x 2 ≤ 3

3 x 1 + 2 x 2 ≤ 8

x 1 , x 2 ≥ 0

After solving we get,

Z max = 1.50957 with x 1 = 2.18077 & x 2 = 0.728841

• Harmonic Average Technique:

Using Harmonic Average Approach,

H . M ( 10 , 3.0156 ) = 2 1 10 + 1 3.0156 = 4.6338

H . M ( 15 , 6.9 ) = 2 1 15 + 1 6.9 = 9.4521

Max Z = 1 4.6338 ( Z 1 + Z 2 ) − 1 9.4521 ( Z 3 + Z 4 ) = 1.718 x 1 + 0.33 x 2 − 0.4316 x 1 2 − 0.7448 x 2 2 + 0.2116 x 1 x 2 + 0.4442

Using Harmonic Average Approach, the system becomes,

Max Z = 1.718 x 1 + 0.33 x 2 − 0.4316 x 1 2 − 0.7448 x 2 2 + 0.2116 x 1 x 2 + 0.4442

Subject to

x 1 + 4 x 2 ≤ 9

x 1 + x 2 ≤ 3

3 x 1 + 2 x 2 ≤ 8

x 1 , x 2 ≥ 0

Solving this, we get,

Z max = 2.35006 with x 1 = 2.11834 & x 2 = 0.522449

• Modified Harmonic Average Technique:

Using Modified Harmonic Average Approach,

H . A V = 2 1 m 1 + 1 m 2 = 2 1 3.0156 + 1 6.9 = 4.1969

Max Z = 1 H . A V ( Z 1 + Z 2 − Z 3 − Z 4 ) = 2.3827 x 1 − 0.4765 x 1 2 − 1.4296 x 2 2 + 0.4765 x 1 x 2 − 0.2383

Thus the QPP becomes,

Max Z = 2.3827 x 1 − 0.4765 x 1 2 − 1.4296 x 2 2 + 0.4765 x 1 x 2 − 0.2383

Subject to

x 1 + 4 x 2 ≤ 9

x 1 + x 2 ≤ 3

3 x 1 + 2 x 2 ≤ 8

Solving this, we get,

Z max = 2.85616 with x 1 = 2.16219 & x 2 = 0.25671

• Advanced Transformation Technique:

Using proposed technique, select

m 1 = min { 10 , 3.0156 } = 3.0156 and m 2 = min { 15 , 6.9453 } = 6.9453

then m = min { m 1 , m 2 } = 3.0156.

Now, we get, O A T = 1 1 / m = 3.0156.

Thus the QPP becomes,

Max Z = 1 O A T ( Z 1 + Z 2 − Z 3 − Z 4 ) = 1 3.0156 ( 10 x 1 − 2 x 1 2 − 3 x 2 2 + 2 x 1 x 2 − 1 ) = 3.3 x 1 − 0.66 x 1 2 − 0.99 x 2 2 + 0.66 x 1 x 2 − 0.33

The system,

Max Z = 3.3 x 1 − 0.66 x 1 2 − 0.99 x 2 2 + 0.66 x 1 x 2 − 0.33

Subject to

x 1 + 4 x 2 ≤ 9

x 1 + x 2 ≤ 3

3 x 1 + 2 x 2 ≤ 8

After solving, we get the result,

Z max = 4.3 with x 1 = 2.29 & x 2 = 0.55

Chandra Sen’s Approach | Harmonic Average Technique | Modified Harmonic Average Technique | Advanced Transformation Technique |
---|---|---|---|

Z = 1.5 x 1 = 2.18 x 2 = 0.73 | Z = 2.35 x 1 = 2.11 x 2 = 0.52 | Z = 2.85 x 1 = 2.16 x 2 = 0.26 | Z = 4.3 x 1 = 2.29 x 2 = 0.55 |

It shows that the solution of the objective functions improved when we used the proposed technique. Advanced transformation technique gives better solutions than others.

Physical InterpretationIn this optimization problem, a process is going to search a better procedure to find maximum value of a given MOQPP.

For more convenience, it can be shown in

Consider, some set of numerical examples of multi-objective optimization problems:

Example 6a.

max z 1 = − 3 x 1 2 − 3 x 2 2 − 6 x 1 x 2 + 30 x 1 + 30 x 2 − 48

max z 2 = − 4 x 1 2 − 4 x 2 2 − 8 x 1 x 2 + 38 x 1 + 38 x 2 − 48

min z 3 = 2 x 1 2 + 2 x 2 2 + 4 x 1 x 2 − 20 x 1 − 20 x 2 + 32

min z 4 = 5 x 1 2 + 5 x 2 2 + 10 x 1 x 2 − 42 x 1 − 42 x 2 + 34

s/t x 1 + 2 x 2 ≤ 7

5 x 1 + 2 x 2 ≤ 11

3 x 1 + 2 x 2 ≤ 10

x 1 , x 2 ≥ 0

Example 6b.

max z 1 = − 3 x 2 2 + 36 x 1 + 34 x 2

max z 2 = − 2 x 1 2 + 32 x 1 + 32 x 2

min z 3 = 4 x 1 2 − 36 x 1 − 32 x 2

min z 4 = 2 x 1 2 − 34 x 1 − 30 x 2

min z 5 = 3 x 2 2 + 6 x 1 x 2 − 32 x 1 − 32 x 2

s/t x 1 + 2 x 2 ≤ 7

5 x 1 + 2 x 2 ≤ 11

3 x 1 + 2 x 2 ≤ 10

x 1 , x 2 ≥ 0

Example 6c.

max z 1 = 0.5 x 1 + 0.66 x 2 + 0.833 x 3

max z 2 = 0.25 x 1 + 0.33 x 2 + 0.415 x 3

min z 3 = 0.2 x 1 − 0.34 x 2 − 0.3 x 3

min z 4 = 0.3 x 1 − 0.32 x 2 − 0.32 x 3

s/t 3 x 1 + 4 x 2 + 2 x 3 ≤ 60

2 x 1 + x 2 + 2 x 3 ≤ 40

x 1 + 3 x 2 + 2 x 3 ≤ 80

Example 6d.

max z 1 = x 1

max z 2 = 2 + x 1 + 2 x 2

max z 3 = 3 + x 2

min z 4 = − 3 x 2

min z 5 = − x 1 − 3 x 2

s/t 2 x 1 + 3 x 2 ≤ 6

x 1 ≤ 4

x 1 + 2 x 2 ≤ 2

Solving examples (6a), (6b), (6c), (6d) by using Chandra Sen’s technique, Harmonic average technique, modified harmonic average technique and Advanced transformation technique we get

Techniques Examples | Chandra Sen’s technique | Harmonic average technique | Modified harmonic average technique | Advanced transformation technique |
---|---|---|---|---|

6a | z max = 3.99 | z max = 4.93 | z max = 7.05 | z max = 8.375 |

6b | z max = 5.15 | z max = 5.28 | z max = 6 | z max = 6.872 |

6c | z max = 3.39 | z max = 3.66 | z max = 5.21 | z max = 5.82 |

6d | z max = 4 | z max = 4.67 | z max = 5.83 | z max = 7 |

According to above table we can conclude that, Advanced transformation technique gives better optimal solution than other techniques whether the functions are linear or quadratic.

This paper discusses the importance of the proposed advanced transformation techniques to solve multi-objective optimization problems. This is a quick safe technique which makes large and complex problems more tractable and accurate. The structural analysis of three different techniques for finding a basic feasible solution is compared throughout performed numerical test examples. The study shows that the proposed method has better performance than other methods. Different data analysis and visual presentation ensure its perfection.

The authors declare no conflicts of interest regarding the publication of this paper.

Yesmin, M. and Alim, Md.A. (2021) Advanced Transformation Technique to Solve Multi-Objective Optimization Problems. American Journal of Operations Research, 11, 166-180. https://doi.org/10.4236/ajor.2021.113010