J. Software Engineering & Applications, 2009, 2: 237-247
doi:10.4236/jsea.2009.24031 Published Online November 2009 (http://www.SciRP.org/journal/jsea)
237
A New Interactive Method to Solve Multiobjective
Linear Programming Problems
Mahmood REZAEI SADRABADI1, Seyed Jafar SADJADI2
1Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, Netherlands; 2Department of
Industrial Engineering, Iran University of Science & Technology, Tehran, Iran.
Received May 20th, 2009; revised June 19th, 2009; accepted June 29th, 2009.
ABSTRACT
Multiobjective Programming (MOP) has become famous among many researchers due to more practical and realistic
applications. A lot of methods have been proposed especially during the past four decades. In this paper, we develop a
new algorithm based on a new approach to solve MOP by starting from a utopian point, which is usually infeasible,
and moving towards the feasible region via stepwise movements and a simple continuous interaction with decision
maker. We consider the case where all objective functions and constraints are linear. The implementation of the pro-
posed algorithm is demonstrated by two numerical examples.
Keywords: Multiobjective Linear Programming, Multiobjective Decision Making, Interactive Methods
1. Introduction
During the past four decades, many methods and algo-
rithms have been developed to solve Multiobjective Pro-
gramming (MOP), in which some objectives are con-
flicting and the utility function of the Decision Maker
(DM) is imprecise in nature. MOP is believed to be one
of the fastest growing areas in management science and
operations research, in that many decision making prob-
lems can be formulated in this domain. For some engi-
neering applications of MOP problems the interested
reader is referred to [1,2]. Decision making problems
with several conflicting objectives are common in prac-
tice. Hence, for such problems, a single objective func-
tion is not sufficient to seek the real desired solution.
Because of this limitation, an MOP method is needed to
solve many real world optimization problems [3].
Although different solution procedures have been in-
troduced, the interactive approaches are generally be-
lieved to be the most promising ones, in which the pre-
ferred information of the DM is progressively articulated
during the solution process and is incorporated into it [4].
The purpose of MOP in the mathematical programming
framework is to optimize r different objective functions,
subject to a set of systematic constraints. A mathematical
formulation of an MOP is also known as the vector
maximization (or minimization) problem. Generally,
MOP can be divided into four different categories.
The first and the oldest group of MOP need not to get
any information from DM during the process of finding
an efficient solution. These types of algorithms rely
solely on the pre-assumptions about DM's preferences. In
this category, L-P Metric methods are noticeable, algo-
rithms whose objectives are minimization of deviations
of the objective functions from the ideal solution. Since
different objectives have different scales, they must be
normalized before the process of minimization of devia-
tions starts. Therefore, a new problem is minimized
which has no scale [5].
The second group of MOP includes gathering cardinal
or ordinal preferred information before the solving proc-
ess initiates. In the method of utility function [6], for
example, we determine DM's utility as a function of ob-
jective functions and then we maximize the overall func-
tion under the initial constraints. The other method in this
group, which is extensively used by many researchers, is
Goal Programming (GP) [7] in which DM determines the
least (the most) acceptable level of Max (Min) functions.
Since attaining these values might lead to an infeasible
point, the constraints are allowed to exceed, but we try to
minimize these weighted deviations.
The third group of MOP provides a set of efficient so-
lutions in which DM has the opportunity to choose his
preferred solution among the efficient ones. Although
finding an efficient solution in MOP is not difficult, but
finding all efficient solutions to render DM is not a trivial
task. Many papers have discussed this important issue
[8–11]. The set of all efficient feasible solutions in a
Multiobjective Linear Programming (MOLP) can be
represented by convex combination of efficient extreme

A New Interactive Method to Solve Multiobjective Linear Programming Problems 238
points and efficient extreme rays in the feasible region.
Therefore, the set of efficient extreme points and effi-
cient extreme rays can be regarded as the solution set for
an MOLP problem. Ida [8] develops an algorithm to find
the structure of efficient solutions in an MOLP using all
efficient extreme points and extreme rays. Pourkarimi et
al. [9] represent the structure of efficient solutions as
maximal efficient faces. Youness and Emam [11] inves-
tigate the relationships among some efficient solutions in
the objective space and then obtain all efficient solutions
of the MOLP and their structure in the constraint space.
Steuer and Piercy [10] use regression analysis to estimate
the number of efficient extreme points in MOLP. Even
though the final solution among the efficient solutions is
usually chosen by DM, but Gass and Roy [12] propose a
mathematical method for ranking the set of efficient ex-
treme solutions in an MOLP. The idea is to enclose the
given efficient solutions within an annulus of minimum
width, where the width is determined by a hypersphere
that minimizes the maximum deviation of the points
from the surface of the hypersphere.
Finally, the last group of MOP problems provides so-
lutions based on a continuous interaction with DM and
tries to reach the preferred solution at the end of the al-
gorithm. Based on this sound idea, there are many de-
veloped methods categorized in this group [13–21]. Dif-
ferent procedures may be better suited for different types
of decision makers, for different types of decision situa-
tions, or for different stages in the decision making proc-
ess [22]. Homburg [16], for instance, proposed a hierar-
chical procedure which consists of two levels, a top-level
and a base-level. The main idea is that the top-level only
provides general preference information from DM. Tak-
ing this information into account, the base-level then
determines a compromise solution via interaction with
DM by using an interactive procedure. As another exam-
ple, Tchebycheff metric based approaches have become
popular in this category for sampling the set of efficient
solutions in a continuous interaction with DM to narrow
his choices down to a single most preferred efficient so-
lution. The interaction with DM proceeds by generating
smaller subsets of the efficient set until a final solution is
located [19]. The proposed method by Engau [14] de-
composes the original MOP problem into a collection of
smaller-sized subproblems to facilitate the evaluation of
tradeoffs and the articulation of preferences. A priori
preferences on objective tradeoffs are integrated into this
process, and DM is supported by an interactive procedure
to coordinate any remaining tradeoffs.
There are many advantages on using interactive
methods such as:
- There is no need to get any information from DM
before the solving process initiates,
- The solving process helps DM learn more about the
nature of the problem,
- Only minor preferred information are needed during
the solving process,
- Since DM continuously contributes via analyst to the
problem, he is more likely to accept the final solution,
- There are fewer restricting assumptions involved in
these types of problems in comparison with other groups
of MOP methods.
However, there are some drawbacks associated with
these types of algorithms that the most important ones
are as follows:
- The accuracy of the final solution depends entirely
upon DM's precise answers. In other words, if DM does
not carefully interact with the analyst, the outcome(s) of
the final solution may be undesirable,
- There is no guarantee to reach a desirable solution
after a finite number of iterations,
- DM needs to make more effort during the process of
these algorithms in comparison with other groups.
During the past decades, many researchers have tried
to review or to discuss the strengths, the weaknesses, and
the comparative studies on the existing methods. Borges
and Antunes [23] deal with the sensitivity analysis of the
weights in MOLP. Buchanan [24] has an excellent paper
that reviews and comments on ten famous methods in-
cluding [25–27]. Each description is followed by a de-
tailed analysis of the method which consists of comments
about the underlying approach, technical aspects and
practical considerations. All methods are compared in
terms of some important features such as applicability,
convergence, and difficulty of questions. Also, Buchanan
and Daellenbach [24] describe a laboratory experiment
which compares the performance from the user’s point of
view of four different methods for MOP problems.
Reeves and Gonzalez [22] compare the computational
performance and the quality of the solutions generated by
two similar and yet contrasting interactive procedures.
Sun [4] investigates the solution quality in interactive
MOP. They include value functions used, weights as-
signed to the objective functions in the value functions,
the size of the efficient set, and the number of objective
functions. The feasibility and existence of the ideal and
nadir points are also discussed. The work of Vander-
pooten [28] is a very good reference to review the main
concepts in interactive procedures. After briefly intro-
ducing the interactive procedures, a general technical
framework for the understanding of existing methods is
presented.
The main goals of the mentioned papers are to intro-
duce some criteria to measure the efficiency of various
algorithms and to introduce the characteristics of a good
method. According to Reeves and Franz [29], the main
characteristics of a proper interactive algorithm can be
numerated as follows:
1) Minimum amount of information be required from
DM,

A New Interactive Method to Solve Multiobjective Linear Programming Problems 239
2) The nature of decision making be simple,
3) If DM provides his answers improperly in some in-
teractions, he can have the opportunity to compensate it
in the following interactions,
4) The number of iterations to reach the final solution
be reasonable,
5) DM be familiar with the nature of judgments he is
asked for,
6) The algorithm be suitable for solving large scale
problems.
In this paper, we propose a new algorithm which is
mainly in the group of interactive methods. However, we
also need to get some information from DM before
problem solving initiates; therefore, this algorithm is
neither a pure interactive method nor a pure method in
the second category. In addition, the proposed algorithm
is based upon a novel approach to the problem, starting
from an infeasible utopian point and moving towards the
feasible region and then the final efficient point. The
remaining of this paper is organized as follows. Section 2
provides some of the necessary definitions we need to
use in this paper. In section 3, the problem statement and
the proposed algorithm are explained. Two numerical
examples are demonstrated in section 4 to illustrate the
proposed algorithm. Finally, conclusion remarks appear
in section 5 to summarize the contribution of the paper.
2. Definitions
Consider an MOLP problem defined as follows,
},...,2,1;0;|{
..
},...,2,1;)(max{
miXbXARXM
ts
rkXCXfZ
ii
n
T
kk


(1)
where,
)(Xfk: is the kth objective function,
k
C: is the vector of coefficients in the kth objective
function,
X: is an n-dimensional vector of decision variables,
i
A: is the ith row of technological coefficients,
i
b: is the RHS of the ith constraint, and
M: is the feasible region.
A solution
M
X
 is efficient if and only if there
does not exist another
M
X
 such that )()(XfXf kk 
for all and rk ,...,2,1)()(XfkXfk for at least one k.
Then, the vector,
},...,2,1);({ rkXfZ k (2)
is called a non-dominated criterion vector. All efficient
solutions in M form the efficient set E. Although some
interactive algorithms search the entire feasible region M,
the majority of them are designed to search only the effi-
cient set E. The vector,
},...,2,1);(max)(|)({ *** rkXfXfXfZ kkk  (3)
is called the ideal point or the ideal criterion vector. It
should be mentioned that the ideal criterion vector, and
so the ideal solution , does not usually exist. The
vector,
*
X
},...,2,1);(max)(|)({ ****** rkXfXfXfZ kkk  (4)
is called a utopian vector or a utopian point. Unlike the
ideal criterion vector, there exist many utopian vectors.
Nevertheless, their corresponding **
X
’s are most likely
infeasible.
3. Problem Statement
The majority of methods proposed in the domain of in-
teractive procedures search the feasible region M or the
efficient set E through interaction with DM in order to
attain the final solution. Here, we develop a new algo-
rithm to solve MOLP problems by starting from a uto-
pian point **
X
(which is usually infeasible) and mov-
ing towards the feasible region M and then the efficient
set E via stepwise movements and a plain continuous
interaction with DM in order to be in line with his pref-
erences. Since there are many utopian points outside the
M, we choose the clst ** ose
X
to M as the start point, by
considering the least sum of weighted deviations from
the constraints.
3.1 The Proposed Algorithm
The proposed algorithm attains an efficient solution of an
MOLP through the following steps:
Algorithm:
Step 1. Ask DM to determine, the maximum ac-
ceptable reduction in the amount of in any interac-
tion. Also, ask him to determine, a penalty for devia-
tion of each unit from the ith constraint. In the next step,
we find a utopian point allowing some deviations from
the constraints , in that the utopian point maybe a
point with some negative’s. However, we also con-
sider a big penalty,
k
a
i
w
k
f
0
j
x
w
j
x

, for each unit of such deviations.
Step 2. Maximize each with consideration of
the feasible set M as follows,
)(Xfk
},...,2,1;0;|{
..
)(max
miXbXARXM
ts
XCXf
ii
n
T
kk


(5)
Step 3. Let be the optimal solution for )(* Xfk

A New Interactive Method to Solve Multiobjective Linear Programming Problems 240
each . Solve the following GP prob-
lem,
rkXfk,...,2,1);( 
1;,...,2,1
;
min{
1
jmi
xdbXA
wdw
jiii
m
i
ii





i
d
},...,2,1;,...,2,
;0;
);()(|*
1
rkn
dd
XfXfd
j
kk
n
j
j







(6)
where, represents the deviation from the ith con-
straint. In this step, we allow our solution to go outside
the feasible region. Suppose X is the solution for (6). Set
X
X

ik
0 and go to step 4.
Step 4. Let

be the angle between and .
Calculate
i
fk f
ik

sin as follows,
||.||
.
1
ki
ki
CC
CC
sinik   (7)
Now, we can determine a small step δ by which we
move towards the feasible region in each iteration as,
};,...,2,1,;
sin||
min{ kirki
C
a
iki
i

 (8)
Step 5. Consider constraints which
remain active. Now ask DM to see which active objec-
tive has the least desirability. Let l be the index for the
which has the least desirability.
)()( *0 XfXf kk 
l
f
Step 6. Solve the following optimization problem in
which we take a step δ from 0
X
towards the feasible
region while we keep the amount of ,
l
f
},...,2,1;,...,2,1
;0;;||;
);()(|min{
0
0
11
njmi
ddxXXdbXA
XfXfdwdw
jjiii
ll
n
j
j
m
i
ii






 
 (9)
where, |.| is the 2-norm. In this step there is no change
in the value of but we usually expect that the other
objective functions get worse, but not necessarily. In
other words, we might encounter a situation in which the
values of some active or inactive get better.
l
f
k
f
Step 7. If then go to step 8,
otherwise set
0
11


 
n
j
j
m
i
ii dwdw
X
X

0, calculate the new values of
, and go to step 5.
)( 0 Xfk
Step 8. implies that we are in-
side the feasible region, but most likely not on the
boundary. Therefore, we take a smaller step to be
stopped on the boundary by solving,
0
11


 
n
j
j
m
i
ii dwdw
},...,2,1;,...,2,1;,...,2,1
;0;);()(| |min{|00
rknjmi
xbXAXfXfXX jiikk

(10)
There is no guarantee that the solution of step 8 is a
non-dominated one. So, we move on the boundary to
reach a non-dominated solution. Set
X
X

0,
},...,2,1{ rS

, and go to step 9.
Step 9. Ask DM to see which objective in S has the
least desirability. Let l be the index for the which
has the least desirability. Solve the following optimiza-
tion problem in which we take a step at most with the
amount of δ from
l
f
0
X
on the boundary of the feasible
region while we keep the amounts of , rkfk1; ,...,2,
},...,2,1;,...,2,1;,...,2,1;0
;||;);()(|)(max{ 00
rknjmix
XXbXAXfXfXf
j
iikkl

 
(11)
Step 10. If then set
)()( 0 XfXfll },...,2,1{ rS

and go to step 9, otherwise set and go to step
11.
lSS
Step 11. If


S then choose X as the final efficient
solution, otherwise set
X
X

0 and go to step 9.
End.
It should be noted that steps 1-8 help us to reach to the
feasible region M by starting from the closest utopian
point in line with DM’s preferences, whereas steps 9-11
guarantee that the final solution is an efficient one, i.e.,
the final solution is in E.
3.2 Some Lemmas to Determine δ
Here, we show how to choose δ in Step 4 of the proposed
algorithm with the following three lemmas.
Lemma 1: Any step δ along gradient vector will
result a decrease (or increase) of
k
C
|| k C

in .
k
f
Proof: Let kj

be the angle between and axis
k
C
j
x
. Therefore,
||
1||
)0,...,1,...,0).(,...,,...,(
||||
.
cos 1
k
kj
k
knkjk
jk
jk
kj
C
c
C
ccc
xC
xC


 
(12)
where, is the jth unique vector in an n-dime-
nsional space. The angle between
j
x
k
C
and j
x
helps us
to compute the projection of k
C
over the axis j
x
, i.e.,

A New Interactive Method to Solve Multiobjective Linear Programming Problems 241
if we take a step δ along vector k
C
, the amount of
change in each element of j
x
is kj


cos or
)cos( kj



 depending on the direction we choose.
Figure 1 depicts the gradient vector k
C
and its projec-
tion in a 2-dimensional space.
Therefore,
|
k
kj
|C
c
cos kjj x   (13)
or
||
cos

)cos(
k
kj
kj C
c
  kjj
x
k
f
 (14)
Therefore, we can compute the change in the amount
of as follows,
||.|
|
..||
2
1
2
11
kk
k
n
j
kj
k
n
j
kj
n
j
jkjk
CC
C
c
C
cxcf





  
|.
||
||
k
kj 
l
|C
c
C
(15)
We now present a generalized form of Lemma (1).
Lemma 2: Any step δ along which makes the
angle lk

with will result a decrease (increase) of
k
C
lkk
C


cos|| in .
k
f
Proof: It is clear that taking a step δ along which
makes the angle
l
C
lk

with is the same as taking a
k
C
Figure 1. The gradient vector k
C
and its projection
(a) (b)
Figure 2. Demonstration of taking a step δ on in a
2-dimensional space
l
H
step lk


cos along . Using the results of Lemma(1)
yields,
k
C
||cos|| klkk Cf




(16)
Lemma 3: Let be a hyperplane which is or-
thogonal to l and makes the angle
l
H
l
CC lk

with .
Any step δ on the hyperplane in any direction will
result a decrease (increase) of
k
C
l
H
sin|| klk C


in .
k
f
Proof: We prove this lemma in two steps. In the first
step, let 2/0




lk , then taking any step δ on
l
H in any direction is the same as taking a step δ in
the direction whose angle with is
l
C2/

and there-
fore makes the angle lk


2/ with . Figure 2(a)
demonstrates the situation in a 2-dimensional space.
k
C
According to lemma (2), taking any step δ along the
direction which makes the angle lk


2/ or lk



2/
with will result a change with the amount of
k
C
2/ ||)cos(klk C




or ||)2/ lk cos( k C



 in .
Since
k
f
2/0




lk , we have,
||sin||)2/cos( klkklk CC







(17)
or
||sin||)2/cos( klkklk CC







(18)
Finally, we have,
||sin|| klkk Cf




(19)
Now, in the second step, suppose





lk
2/
k
C
.
Taking any step δ on in any direction is the same as
taking a step δ in the direction whose angle with is
l
H
2/



lk or lk



2/3 . Figure 2(b) demonstrates the
situation in a 2-dimensional space. Using similar argu-
ment used in the first step yields,
||sin||)2/cos( klkklk CC







(20)
or
||sin||)2/3cos(klkklk CC







(21)
Finally, we have,
||sin|| klkk Cf




(22)
Now, we are ready to determine the amount of δ prop-
erly. Suppose DM determines that he wouldn't expect
any reduction more than in the amount of in
any interaction. When we perform step (4) in the algo-
rithm, actually we keep unchanged. In order to
k
a
l
f
k
f

A New Interactive Method to Solve Multiobjective Linear Programming Problems 242
achieve this goal, we have to take step δ on . Ac-
cording to lemma (3), the step leads to an increase (de-
crease)
l
H
||sin klkC


in . There is no problem in
our approach in case increases. However, we must
ensure that the step δ would not worsen more than
, which suggest to keep the following condition,
k
f
kak
k
f
k
f
l
k
a
krCklk

| ;,...,1;|sin


(23)
or
lkr;,...,1k
lk
;
C
a
k
k
|| 
l
f
sin 
k
a
k
(24)
Holding (19) in all interactions throughout the algo-
rithm guarantees that there would be no reduction in any
more than . Since DM is entitled to keep
the amount of any , the following condition must
hold in order to obtain an appropriate δ,
kfk;
lk rl ;,...,1,k
lk
;

C
a
k
|| 
k
sin (25)
Finally, we are about to determine the best amount of
δ with consideration of DM’s intentions and concurrently
reaching to the feasible solution by doing as fewer inter-
actions as possible. Thus, we have,
}l;kr,...,1,; lk 
sin lk
k

0
5
15
4
5
2
2
2
1





x
x
x
x
x
|
a
k
.6
9
2
1
2
1



x
|
min{ C 

,
22
7
..
1
1
1
1


x
x
x
x
x
ts
Maxz
Maxz
(26)
4. Numerical Examples
In this section we demonstrate implementation of the
proposed method using two numerical examples.
4.1 Example 1
Consider the following MOLP problem with two objec-
tive functions,
165
63
20
2
6
21
2



x
x
(27)
We first ask DM to specify his sensitivity about the
constraints and the objectives. As we already defined,
’s are the penalties associated with the constraints and
’s are the permitted amounts of reduction on the ob-
jective functions in each iteration. For the sake of sim-
plicity suppose that all constraints have equal sensitivity,
i.e.,
i
w
k
a
4,...,1;1


iwi. Next, we have to determine the
acceptable amount of reduction on the objectives 1
z
and 2
z
. For this example, suppose DM specifies 2 and 3
for and , respectively. The appropriate value for
δ can be determined as the following,
1
a2 a
3761||) 22
1 C6,1(
1C
2925||) 22
2 C2,5(
2C
52.0
29.37
)2,5).(6,1(
||.||
cos 12 C 
.
21
21 
C
CC
85.0)52.0(1sin12 
2
38.0}
)85.0(29
3
,
)85.0(
2
}
sin||
,
sin| 212
2
121
1

 C
aa
37
min{
|
min{



C
Then, we must find and . Solving two distinct
LP problems with consideration of and yields
*
1
z*
2
z
1
z2 z
)
49.1(,(1.5,95)
2

xx with 86.34
*
1
z
and)47.1,50), 2.6(( 1

xx
with , respectively. In the next step, we ob-
tain the utopian point in which both objectives are satis-
fied at least with their optimal values, while we reach to
a common point. Hence, we have,
43.
;0
:
2
6
5.6
9
4
2
2
1








i
x
d
d
x
x
x
)
**
2
35
*
2
z
(*
1
6,...,1
,
43.355
86.34
1651522
637
20
..
)(1000
1
62
51
21
1
41
32
221
121
654321









d
signinfreex
x
x
x
x
dx
dxx
dx
dxx
ts
ddddddMinD
i
(28)
The optimal solution for (28) is
with
)96.4,10.5(),( **
2
**
1xx
)43.35,86.34(,
*

z
2
z
z and . In the
next step, the DM is asked to select the objective which
has the least desirability for him. Suppose in the first
interaction the DM adopts . Therefore, we must solve
the following problem,
02.39
** D

A New Interactive Method to Solve Multiobjective Linear Programming Problems 243
6,...,1;0
:,
38.0)96.4()10.5(
43.3525
5.6
1651522
6397
204
..
)(1000
21
2
2
2
1
21
62
51
41
321
221
121
654321










id
signinfreexx
xx
xx
dx
dx
dx
dxx
dxx
dxx
ts
ddddddMinD
i
(29)
The optimal solution for (29) is
with and . Table 1
summarizes the results of implementation of the pro-
posed algorithm during the next iterations.
)61.4,24.5(),( 21 xx
65.34D)43.35,89.32(),(22 zz
As one can observe, we have reached to the feasible
region after 8 iterations. The final step by which we
reach to the feasible region is from

12
,xx

(4.04,
4.10) to with feasible amounts
. So, in order to reach to the fea-
sible region by a smaller step we solve,
)75.3,18.4(),( 21xx
)38.28,65.26(),( 21 zz
Table 1. The detailed information for implementation of the
proposed method for example 1
Iteration Objective x1 x2 D z1 z2
0 max z1 1.95 5.49 0 34.8620.73
0 max z2 6.5 1.47 0 15.3235.43
0 utopian 5.1 4.96 39.02 34.8635.43
1 keep z2 5.24 4.61 34.65 32.8935.43
2 keep z2 5.38 4.25 30.27 30.8835.43
3 keep z1 5.01 4.32 20.9 30.8833.69
4 keep z2 5.17 3.91 15.87 28.6333.69
5 keep z1 4.8 3.97 6.5 28.6331.94
6 keep z1 4.42 4.04 4.28 28.6330.18
7 keep z1 4.04 4.1 2.14 28.6328.38
8 keep z2 4.18 3.75 0 26.6528.38
9 min delta 4.17 3.75 0 26.6928.38
10 max z1 4.17 3.75 0 26.6928.38
11 max z2 4.17 3.75 0 26.6928.38
2,1;0
5.6
1651522
6397
204
38.2825
65.266
..
)10.4()04.4(
1
21
21
21
21
21
2
2
2
1








jx
x
xx
xx
xx
xx
xx
ts
xxMinD
j
(30)
Problem (30) leads to, with )75.3,17.4(),(21 xx
)38.28,69.26(),( 21

zz and 37.0

, which is the first
feasible point on the boundary of the feasible region.
Then, the DM is asked to determine the objective func-
tion which has the least desirability. Suppose he
adopts , so we solve,
1
z
2,1;0
5.6
1651522
6397
204
38.2825
38.0)75.3()17.4(
..
6
1
21
21
21
21
2
2
2
1
211








jx
x
xx
xx
xx
xx
xx
ts
xxMaxz
j
(31)
Problem (31) leads to with )75.3,17.4(),(21 xx
)38.28,69.26(),( 21

zz
}2{
. As one can see, cannot be
improved by moving from . So, we
have
1
z
)75.3,17.4(), 21 xx(

S2 z and is chosen to get improved. We
solve,
2,1;0
5.6
1651522
6397
204
69.266
38.0)75.3()17.4(
..
25
1
21
21
21
21
2
2
2
1
212








jx
x
xx
xx
xx
xx
xx
ts
xxMaxz
j
(32)
Problem (32) leads to with )75.3,17.4(),(21 xx
)38.28,69.26(),( 21

zz . As one can see, cannot be
improved by moving from . So,
2
z
)75.3,17.4(),(21 xx

A New Interactive Method to Solve Multiobjective Linear Programming Problems 244

S
21,zz
and with
is the final efficient feasible solution.
)75.3,17.4(),( 21 xx
0,...,
2516
103
401320
2572
576
..
58
76
8010
41
321
321
321
321
321
213
212
11









xx
xxx
xxx
xxx
xxx
xxx
ts
xxMaxz
xxMaxz
xMaxz
321 ,,, www
1000

w
3
z
)38.28,69.26(),(21 zz
228
15
800
320
142
4
8
1625
4
43
43
43








x
xx
xx
xx
5
w
4.2 Example 2
Consider the following MOLP problem with three objec-
tive functions,
80
24
16
9
3
12
25
4
4
4
4
2




x
x
x
x
x
(33)
Suppose that the values 12, 5, 45, 2, and 6 are speci-
fied by the DM for , and , respectively
and we consider . Also, 300, 50, and 30 are
determined as the acceptable amount of reduction for
, and . The optimal value for δ is determined as
follows,
4
w
7350||)15,25,80,10( 11 CC
774||)8,25,7,6(22 C C
249||)4,12,5,8( 23 C C
82.0)57.0(1sin
57.0
774.7350
)8,25,7,6).(15,25,80,10(
||.||
.
2
12
21
21
12




CC
CC
cos

1)03.0(1sin
03.0
249.7350
)4,12,5,8).(15,25,80,10(
||.||
.
2
13
31
31
13






CC
CC
cos

62.0)79.0(1sin
79.0
249.774
)4,12,5,8).(8,25,7,6(
||.||
.
2
23
32
32
23






CC
CC
cos

90.1
,90.1,90.2,19.2,50.3,27.4min{}
sin||
,
,
sin||
,
sin||
,
sin||
,
sin||
min{
323
3
31
232
2
212
2
131
1
121
1



C
a
C
a
C
a
C
a
C
a
}07.3
sin|| 3
3

 
C
a
Now, , and must be found. Solving three
LP problems with consideration of , and sepa-
rately yields
*
2
*
1,zz * 3
z
,
2
21,zz
.35,22.
3
z
)0,0,0517(),,( 431

xx
20.10,.16(),,( 41
xx
,32
with
, 87.2975
*
1z)0,52.4,66

xxx
3,0,0),,( 43xx
x
,21xx
with
, and with
, respectively. Then, we obtain the utopian
point in which three objectives are satisfied at least with
their optimal values while we reach to a common point.
Therefore, we have,
64.386
*
2z)98.,82.36(
45.310
*
3z
;0
:,...,
58
76
8010
516
103
1320
72
76
..
(1000
41
94
83
72
61
21
21
1
1
1
1
21
1
6















id
xx
dx
dx
dx
dx
xx
xx
x
xx
xx
x
xx
x
ts
d
MinD
i
,( **
1
9,...,1
45.310412
64.386825
87.29751625
228802
1524
8001640
320925
14235
)
6245512
43
43
432
5432
4432
3432
243
1432
987
54321










signinfree
xx
xx
xxx
dxx
dxx
dxxx
dx x
dxxx
ddd
ddddd
(34)
The optimal solution is
with
)0,0,30,56.57(),,,( **
4
**
3
**
2
**
1xxxx
)48.310,36.555,60.2975(), **
3
**
2

z
43
and
zz
.33380
**

D
1
z3 z
. In the next step, the DM is asked to
select the objective which has the least desirability for
him. Since the constraint associated with 2 is not ac-
tive, the DM is allowed to select one of the objectives
or to keep its value. Suppose in the first iteration
the DM adopts . Therefore, the following problem
should be solved,
z
3
z
9,...,1;0
:,...,
9.1
)0()0()30()56.57(
48.31041258
228802516
1524103
80016401320
32092572
1423576
..
)(1000
6245512
41
2
4
2
3
2
2
2
1
4321
94
83
72
61
54321
44321
34321
24321
14321
9876
54321















id
signinfreexx
xxxx
xxxx
dx
dx
dx
dx
dxxxx
dxxxx
dxxxx
dxxxx
dxxxx
ts
dddd
dddddMinD
i
(35)

A New Interactive Method to Solve Multiobjective Linear Programming Problems 245
Table 2. The detailed information for implementation of the proposed method for example 2
Iteration Objective x1 x2 x3 x4 D z1 z2 z3
0 max z1 17.22 35.05 0 0 0 2976.2 348.67 -37.49
0 max z2 16.66 4.52 10.2 0 0 783.2 386.6 233.08
0 max z3 36.82 0 0 3.98 0 431.88 252.76 310.48
0 utopian 57.56 30 0 0 33380.43 2975.6 555.36 310.48
1 keep z3 56.74 28.29 -0.17 0 31484.82 2826.35 534.22 310.48
2 keep z3 55.92 26.58 -0.33 0 29613.44 2677.35 513.33 310.48
3 keep z1 54.4 27.09 -1.35 0 27726.82 2677.35 482.28 283.55
4 keep z3 53.58 25.38 -1.52 0 25860.25 2528.2 461.14 283.55
5 keep z3 52.76 23.67 -1.68 0 23988.88 2379.2 440.25 283.55
6 keep z3 51.94 21.96 -1.85 0 22118.36 2229.95 419.11 283.55
7 keep z3 51.12 20.25 -2.02 0 20244.01 2080.7 397.97 283.55
8 keep z1 49.6 20.76 -3.04 0 18351.77 2080.7 366.92 256.52
9 keep z1 48.08 21.27 -4.06 0 16465.06 2080.7 335.87 229.57
10 keep z3 47.26 19.56 -4.23 0 14599.55 1931.65 314.73 229.57
11 keep z3 46.44 17.85 -4.39 0 12728.18 1782.65 293.84 229.57
12 keep z3 45.62 16.14 -4.56 0 10857.66 1633.4 272.7 229.57
13 keep z1 44.1 16.65 -5.58 0 8965.42 1633.4 241.65 202.59
14 keep z1 42.58 17.16 -6.6 0 7078.71 1633.4 210.6 175.64
15 keep z3 41.12 16.21 -5.83 0 5830.92 1562.25 214.44 177.95
16 keep z3 39.75 15.32 -4.86 0 4855.56 1501.6 224.24 183.08
17 keep z3 38.38 14.43 -3.88 0 3882.43 1441.2 234.29 188.33
18 keep z2 37.01 13.54 -2.91 0 2906.67 1380.55 244.09 193.46
19 keep z2 35.64 12.65 -1.93 0 1933.53 1320.15 254.14 198.71
20 keep z1 33.95 12.59 -1.07 0 1066.54 1320.15 265.08 195.81
21 keep z1 32.26 12.53 -0.2 0 203.27 1320.15 276.27 193.03
22 keep z1 30.45 12.59 0 0.52 0 1320.15 274.99 182.73
23 min delta 31.86 12.52 0 0 0 1320.2 278.8 192.28
24 max z1 31.86 12.52 0 0 0 1320.2 278.8 192.28
25 max z2 31.85 12.52 0 0 0 1320.2 278.8 192.28
26 max z3 31.86 12.52 0 0 0 1320.2 278.8 192.28
The optimal solution for (35) is
with
),,,(4321 xxxx
)0,17.0,29.28,74.56(
)43.310,22.534,35.2826(),,(321 zzz and . 82.31484D
Table 2 summarizes the results of implementation of
the proposed algorithm for example 2. Note that the con-
straint associated with is not active till iteration 8.
Therefore, he is allowed to choose
2
z
2
z
as the objective
whose desirability is the least amount from iteration 8.
According to Table 2, we reach to the feasible region
in iteration 22. So, solving the following problem helps
us to attain the boundary of the feasible region, 4,...,1;0
228802516
1524103
80016401320
32092572
1423576
73.18241258
99.27482576
02.132016258010
..
)0()2.0()53.12()26.32(
4321
4321
4321
4321
4321
4321
4321
4321
2
4
2
3
2
2
2
1










jx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
ts
xxxxMinD
j
(36)

A New Interactive Method to Solve Multiobjective Linear Programming Problems 246
The optimal solution for (36) is ),,,( 4321

xxxx
)28.192,8.278,2. with
and
)0,0,52.12,86.31(
44.0
1320(),,( 321 zzz

.
Suppose the DM adopts as the objective to get
improved. Hence,
1
z
4,...,1;0
228802516
1524103
80016401320
32092572
1423576
73.18241258
99.27482576
9.1)0()2.0()53.12()26.32(
..
16258010
4321
4321
4321
4321
4321
4321
4321
2
4
2
3
2
2
2
1
43211










jx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
ts
xxxxMaxz
j
(39)
The optimal solution for (39) is ),,,( 4321

xxxx
)28.192,8.278, )with .
Since
0,0,52.12,86.31(
1
2.1320(),,( 321 zzz
z
does not change, we have . Then, }3,2{S
2
z
is adopted by the DM to get improved, which leads
to,
4,...,1;0
228802516
1524103
80016401320
32092572
1423576
73.18241258
2.132016258010
9.1)0()2.0()53.12()26.32(
..
82576
4321
4321
4321
4321
4321
4321
4321
2
4
2
3
2
2
2
1
43212










jx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
ts
xxxxMaxz
j
(40)
The optimal solution for (40) is ),,,( 4321

xxxx
)28.192,8.278,2. with .
Obviously,
)0,0,52.12,86.31(
2
1320(),,(321 zzz
z
remains unchanged; so, . The
only remaining objective is and we have,
}3{S
3
z
4,...,1;0
228802516
1524103
80016401320
32092572
1423576
8.27882576
2.132016258010
9.1)0()2.0()53.12()26.32(
..
41258
4321
4321
4321
4321
4321
4321
4321
2
4
2
3
2
2
2
1
43213










jx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
xxxx
ts
xxxxMaxz
j
(41)
The optimal solution for (41) is ),,,( 4321

xxxx
)28.192,8.278,2.
3
z
) with .
Since similar to and , the amount of remains
unchanged, we have
0,0,52.12,86.31(1320(),,( 321 zzz
2
z
1
z


S
(),,,( 4321 xxxx
)28.192,8.278,2.1320
. Therefore, the final efficient
feasible solution is
with
)0,0,52.12,86.31
(),,( 321

zzz .
5. Conclusions
We have proposed a new interactive algorithm to solve
MOLP in which we need some initial information about
DM's preferences. Unlike the majority of interactive
methods, the proposed method starts from the utopian
point, which is usually infeasible, and moves towards the
feasible region and the efficient set. Based on the results
of some proved lemmas, we are able to specify the
amount of steps towards the feasible region. Our method
satisfies most of the characteristics that a good interac-
tive method needs, such as simplicity of the nature of
judgments for DM, having the opportunity to compensate
improper decisions in previous interactions, and handling
his nonlinear utility. Implementation of the proposed
method has been demonstrated by using two numerical
examples.
REFERENCES
[1] F. B. Abdelaziz, “Multiple objective programming and
goal programming: New trends and applications,” Euro-
pean Journal of Operational Research, Vol. 177, pp.
1520–1522, 2007.
[2] M. M. Wiecek, “Multiple criteria decision making for
engineering,” Omega, Vol. 36, pp. 337–339, 2008.
[3] J. Kim and S. K. Kim, “A CHIM-based interactive Tche-
bycheff procedure for multiple objective decision mak-
ing,” Computers & Operations Research, Vol. 33, pp.
1557–1574, 2006.
[4] M. Sun, “Some issues in measuring and reporting solu-
tion quality of interactive multiple objective programming
procedures,” European Journal of Operational Research,
Vol. 162, pp. 468–483, 2005.
[5] M. Zeleny, “Multiple criteria decision making,” MC
Graw-Hill, New York, 1982.
[6] R. Kenney and H. Raiffa, “Decisions with multiple objec-
tives: Preferences and value trade-offs,” J. Wiley, New
York, 1976.
[7] C. Romero, “Handbook of critical issues in goal pro-
gramming,” Pergamon Press, Oxford, 1991.
[8] M. Ida, “Efficient solution generation for multiple objec-
tive linear programming based on extreme ray generation
method,” European Journal of Operational Research, Vol.
160, pp. 242–251, 2005.
[9] L. Pourkarimi, M. A. Yaghoobi and M. Mashinchi, “De-
termining maximal efficient faces in multiobjective linear
programming problem,” Journal of Mathematical Analy-

A New Interactive Method to Solve Multiobjective Linear Programming Problems 247
sis and Applications, Vol. 354, pp. 234–248, 2009.
[10] R. E. Steuer and C. A. Piercy, “A regression study of the
number of efficient extreme points in multiple objective
linear programming,” European Journal of Operational
Research, Vol. 162, pp. 484–496, 2005.
[11] E. A. Youness and T. Emam, “Characterization of effi-
cient solutions for multi-objective optimization problems
involving semi-strong and generalized semi-strong
e-convexity,” Acta Mathematica Scientia, Vol. 28B(1), pp.
7–16, 2008.
[12] S. I. Gass and P. G. Roy, “The compromise hypersphere
for multiobjective linear programming,” European Jour-
nal of Operational Research, Vol. 144, pp. 459–479,
2003.
[13] J. Chen and S. Lin, “An interactive neural network-based
approach for solving multiple criteria decision making
problems,” Decision Support Systems, Vol. 36, pp.
137–146, 2003.
[14] A. Engau, “Tradeoff-based decomposition and deci-
sion-making in multiobjective programming,” European
Journal of Operational Research, Vol. 199, pp. 883–891,
2009.
[15] L. R. Gardiner and R. E. Steuer, “Unified interactive mul-
tiple objective programming,” European Journal of Op-
erational Research, Vol. 74, pp. 391–406, 1994.
[16] C. Homburg, “Hierarchical multi-objective decision mak-
ing,” European Journal of Operational Research, Vol. 105,
pp. 155–161, 1998.
[17] C. L. Hwang and A. S. M. Masud, “Multiple objective
decision making methods and applications,” Springer-
Verlag, Amsterdam, 1979.
[18] B. Malakooti and J. E. Alwani, “Extremist vs. centrist
decision behavior: Quasi-convex utility functions for in-
teractive multi-objective linear programming problems,”
Computers & Operations Research, Vol. 29, pp. 2003–
2021, 2002.
[19] G. R. Reeves and K. R. MacLeod, “Some experiments in
Tchebycheff-based approaches for interactive multiple
objective decision making,” Computers & Operations
Research, Vol. 26, pp. 1311–1321, 1999.
[20] R. E. Steuer, J. Silverman, and A. W. Whisman, “A com-
bined Tchebycheff/aspiration criterion vector interactive
multi-objective programming procedure,” Computers &
Operations Research, Vol. 43, pp. 641–648, 1995.
[21] M. Sun, A. Stam, and R. E. Steuer, “Interactive multiple
objective programming using Tchebycheff programs and
artificial neural networks,” Computers & Operations Re-
search, Vol. 27, pp. 601–620, 2000.
[22] G. R. Reeves and J. J. Gonzalez, “A comparison of two
interactive MCDM procedures,” European Journal of
Operational Research, Vol. 41, pp. 203–209, 1989.
[23] A. R. P. Borges and C. H. Antunes, “A visual interactive
tolerance approach to sensitivity analysis in MOLP,”
European Journal of Operational Research, Vol. 142, pp.
357–381, 2002.
[24] J. T. Buchanan and H. G. Daellenbach, “A comparative
evaluation of interactive solution methods for multiple
objective decision models,” European Journal of Opera-
tional Research, Vol. 29, pp. 353–359, 1987.
[25] A. A. Geoffrion, J. S. Dyer, and A. Feinberg, “An inter-
active approach for multi-criterion optimization with an
application to the operation of an academic department,”
Management Science, Vol. 19, pp. 357–368, 1972.
[26] R. E. Steuer and E. U. Choo, “An interactive weighted
Tchebycheff procedure for multiple objective program-
ming,” Mathematical Programming, Vol. 26, pp. 326–344,
1983.
[27] S. Zionts and J. Wallenius, “An interactive multiple ob-
jective linear programming method for a class of under-
lying nonlinear utility functions,” Management Science,
Vol. 29, pp. 519–529, 1983.
[28] D. Vanderpooten, “The interactive approach in MCDA: A
technical framework and some basic conceptions,”
Mathematical and Computer Modelling, Vol. 12, pp.
1213–1220, 1989.
[29] G. R. Reeves and L. Franz, “A simplified interactive mul-
tiple objective linear programming procedure,” Com-
puters and Operations Research, Vol. 12, pp. 589–601,
1985.