Advanced Transformation Technique to Solve Multi-Objective Optimization Problems ()
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:
Subject to
where,
The problem consists of n decision variables, m constraints and k objectives.
and
might be linear or nonlinear.
Mathematically, the multi-objective linear programming problem (MOLPP) can be defined as:
And mathematically the multi-objective quadratic programming problem (MOQPP) can be stated as:
Subject to
for maximization and
for minimization
where x is an n-dimensional vector of decision variables, P is a
symmetric matrix of coefficients. A is
matrix of coefficients, B and C are n-dimensional vector of constants.
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:
Subject to
(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:
The optimum value of the objective function
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
by
. The function is formulated as:
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
are n observations then
Harmonic Mean (HM) =
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:
where,
,
.
Subject to same constraints as Equation (3.1).
is the value of harmonic mean of maximized
and
is the value of harmonic mean of minimized
. The values of
and
may be positive or negative. If they are negative we consider the absolute values of
and
.
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:
where
and
,
Subject to same constraints as Equation (3.1).
is the minimum value of maximized
and
is the minimum value of minimized
. 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:
Subject to
(4.1)
Suppose we optimize all the objective functions individually and obtain the values
where
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:
where
and
.
where
.
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
by
.
Step 4: Repeat step-2 for
.
Step 5: Select
and
.
Step 6: Select
and calculate
.
Step 7: Optimize the combined objective function as
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:
• 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,
Using Chandra Sen’s Approach, the system becomes,
Subject to
After solving we get,
• Harmonic Average Technique:
Using Harmonic Average Approach,
Using Harmonic Average Approach, the system becomes,
Subject to
Solving this, we get,
• Modified Harmonic Average Technique:
Using Modified Harmonic Average Approach,
Thus the QPP becomes,
Subject to
Solving this, we get,
• Advanced Transformation Technique:
Using proposed technique, select
then
Now, we get,
Thus the QPP becomes,
The system,
Subject to
After solving, we get the result,
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.
s/t
Example 6b.
s/t
Example 6c.
s/t
Example 6d.
s/t
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.