Advanced Transformation Technique to Solve Multi-Objective Optimization Problems

Abstract

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 indicates 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.

Share and Cite:

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

1. Introduction

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 [1]. The main limitation of MOO is that its computational burden grows in size with the number of objectives. Various types of solution procedure have been already developed for solving MOO problems [2] - [21]. Some of them deal with theory and some of them concern with solution methods and applications.

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 [17], Optimal transformation technique by Sulaiman and Ameen [4], Harmonic mean by Sulaiman and Mustafa [9], New statistical average method by Nahar and Alim [12].

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 [3] and by Guzel [5], An improved method by Mehdi, Chergui and Abbas [7], Arithmetic average technique by Sulaiman, Sadiq and Rahim [8], A new approach presented by Akter and Modi [10], New geometric average technique proposed by Nahar and Alim [11].

Many research scholars have solved multi-objective quadratic programming problem by applying several methods. We include some of them. Optimal cutting plane procedure [19] and Arithmetic average transformation technique [20] had been used by Sulaiman and Rahim. Optimal average maximum-minimum technique and Optimal geometric average technique had been used by Sulaiman-Nawkhass [6] and by Sulaiman-Abdull [21] gradually to solve multi-objective quadratic programming problem.

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 [1] [15]. Multi-objective linear programming problem (MOLPP) has been solved by many research scholars. Sulaiman and Sadiq had solved MOLPP by using mean and median [17]. Hamad-Amin used arithmetic average technique to solve it [18]. New statistical (arithmetic, geometric, harmonic) average techniques had been proposed by Nahar and Alim for solving MOLPP. Sulaiman and Rahim used optimal cutting plane procedure to solve MOQPP [19]. Arithmetic average transformation technique and Geometric average technique had been used by Sulaiman, Rahim and Sulaiman, Abdullah to generate efficient solutions of MOQPP [20] [21]. Yesmin and Alim suggested a modified harmonic average technique to get more accurate solution by solving MOQPP [15].

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.

2. Multi-Objective Optimization Problem

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.

3. Techniques for Solving MOOP

3.1. Chandra Sen’s Approach

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.

3.2. Harmonic Average Technique

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.

3.3. Modified Harmonic Average Technique

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.

4. Advanced Transformation 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).

4.1. Algorithm

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.

4.2. Flow Chart

5. Numerical Example

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 Table 1.

Table 1. Numerical results for given example.

• 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

Table 2 summarizes the solutions of the MOQPP using different approaches.

Table 2. Comparison table for given example.

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 Interpretation

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

Figure 1 shows that, how the optimized results have improved after applying different techniques. Physical interpretation of the given MOQPP after applying different techniques.

Figure 1. Physical interpretation of given example.

For more convenience, it can be shown in Figure 2.

Figure 2. Comparison with different techniques.

6. Data Analysis

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 Table 3.

Table 3. Comparison table for different data values.

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.

7. Conclusion

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.

Conflicts of Interest

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

References

[1] Sen, C. (1983) A New Approach for Multi Objective Rural Development Planning. The Indian Economic Journal, 30, 91-96.
[2] Caramia, M. and Dell’Olmo, P. (2008) Multi-Objective Management in Freight Logistics. Springer-Verlag, London.
https://doi.org/10.1007/978-1-84800-382-8
http://www.springer.com/978-1-84800-381-1
[3] Tantawy, S.F. (2008) A New Procedure for Solving Linear Fractional Programming Problem. Mathematical and Computer Modelling, 48, 969-973.
http://www.elsevier.com/locate/mcm
https://doi.org/10.1016/j.mcm.2007.12.007
[4] Sulaiman, N.A. and Hamadameen (2008) Optimal Transformation Technique to Solve Multi Objective Linear Programming Problem. Journal of Kirkuk University-Scientific Studies, 3, 96-106.
[5] Guzel, N. (2013) A Proposal to the Solution of Multi Objective Linear Fractional Programming Problem. Abstract and Applied Analysis, 2013, Article ID: 435030.
https://doi.org/10.1155/2013/435030
[6] Sulaiman, N.A. and Nawkhass, M. (2013) Transforming and Solving Multi Objective Quadratic Fractional Programming Problem by Optimal Average of Maximin and Minimax Techniques. American Journal of Operation Research, 3, 92-98.
https://doi.org/10.14419/ijamr.v2i2.838
[7] Mehdi, M., Chergui, M. and Abbas, M. (2014) An Improved Method for Solving Multi Objective Integer Linear Fractional Programming Problem. Advances in Decision Science, 2014, Article ID: 306456.
https://doi.org/10.1155/2014/306456
[8] Sulaiman, N.A., Sadiq, G.W. and Rahim, A. (2014) New Arithmetic Average Technique to Solve Multi Objective Linear Fractional Programming Problem and Comparison with Other Techniques. New Arithmetic Average Technique, 18, 122-131.
[9] Sulaiman, N.A. and Mustafa, R.B. (2016) Using Harmonic Mean to Solve Multi Objective Linear Programming Problem. American Journal of Operation Research, 6, 25-30.
https://doi.org/10.4236/ajor.2016.61004
[10] Akter, H. and Moodi, G. (2017) An Approach for Solving Multi Objective Linear Fractional Programming Problem and Comparison with Other Techniques. International Journal of Scientific and Innovative Mathematical Research, 5, 1-5.
https://doi.org/10.20431/2347-3142.0511001
[11] Nahar, S. and Alim, A. (2017) A New Geometric Average Technique to Solve Solve Multi Objective Linear Fractional Programming Problem and Comparison with New Arithmetic Average Techniques. IOSR Journal of Mathematics, 13, 39-52.
[12] Nahar, S. and Alim, A. (2017) A New Statistical Average Method to Solve Multi Objective Linear Programming Problem. International Journal of Science and Research, 6, 623-629.
[13] Sulaiman, N.A. and Mustafa, R.B. (2016) Transform Extreme Point Multi Objective Linear Programming Problem to Extreme Point Single Objective Linear Programming Problem Using Harmonic Mean. Applied Mathematics, 6, 95-99.
[14] Sohag, Z.I. and Asadujjaman, M. (2018) A Proposed New Average Method for Solving Multi Objective Linear Programming Problem Using Various Kinds of Mean Technique. Mathematics Letter, 4, 25-33.
https://doi.org/10.11648/j.ml.20180402.11
[15] Sen, C. (2018) Sen’s Multi Objective Programming Method and Comparison with Other Techniques. American Journal of Operation Research, 8, 10-13.
[16] Yesmin, M. and Alim, A. (2020) A New Quadratic Formulation to Ensure Maximum Profit of a Textile Industry and a Modified Harmonic Average Technique to Solve MOQPP. International Journal of Science and Research, 9, 937-943.
[17] Sulaiman, N.A. and Sadiq, G.W. (2006) Solving the Linear Multi-Objective Programming Problems: Using Mean and Median Value. Al-Rafiden Journal of computer sciences and mathematics, University of Mosul, 3, 69-83.
https://doi.org/10.33899/csmj.2006.164037
[18] Hamad-Amin, A.O. (2008) An Adaptive Arithmetic Average Transformation Technique for Solving MOOPP. MSc. Thesis, University of Koya, Koya.
[19] Sulaiman, N.A. and Abdul-Rahim, B.K. (2011) Optimal Cutting Plane Procedure for Multi-Objective Quadratic Programming Problem. Journal of Koya University, No. 20, 119-130.
[20] Sulaiman, N.A. and Abulrahim, B.K. (2013) Arithmetic Average Transformation Technique to solve Multi-Objective Quadratic Programming Problem. Journal of Zankoy Sulaimani-Part A, 15, 57-69.
https://doi.org/10.17656/jzs.10233
[21] Sulaiman, N.A., Abdullah, R.M. and Abdull, S.O. (2016) Using Optimal Geometric Average Technique to solve Extreme Point Multi-Objective Quadratic Programming Problem. Journal of Zankoy Sulaimani-Part A, 18, 63-72.
https://doi.org/10.17656/jzs.10535

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.