Robust goal programming
by
Dorota Kuchta
Institute of Industrial Engineering
Wroclaw University of Technology
Smoluchowskiego 25, 50-371 Wroc
Abstract: In the paper a new approach to goal programming is
presented: the robust approach, applied so far to a single-objective
linear programming. It is a ”pessimistic” approach, meant to ?nd
a solution which will be reasonably good even in a bad case, but it
is based on the assumption that almost never everything goes bad -
the decision maker can control and simulate the pessimistic aspect
of the decision situation. The pessimism refers here to uncertain
coe?cients in the goal functions. It is assumed that in each case only
a certain number of them can take on unfavourable values - but we
do not know which ones. A robust solution, i.e. the one which will
be good even in the most pessimistic case among those considered
to be possible - is determined, using only the linear programming
methods.
Keywords: multiobjective programming, robust solution, inter-
val optimisation.
1. Introduction
Goal programming has been known in the literature and has been applied suc-
cessfully in practice for many years. But like in case of any other modelling
and optimisation technique, its application encounters some problems when the
decision situation is marked by uncertainty and/or is likely to change. In such
a case the model has to be rede?ned and adopted to a given situation, to the
needs of the de?nite decision maker.
There are several possible approaches to modelling uncertainty and change.
The best known are the stochastic approach and the fuzzy approach. The
author, together with the late Stefan Chanas, has dealt quite a lot with the
fuzzy approach to goal programming. Chanas and Kuchta (2002) carried out
an overview of the existing approaches and their systematisation and categori-
sation. Chanas and Kuchta (2001, 2002) o?er three new fuzzy approaches to
goal programming, which ?ll up several of the existing gaps.
502 D. KUCHTA
The present paper is the ?rst - to the author’s knowledge - attempt to apply
another quite promising approach, called robust approach, to goal programming
and to multicriteria programming in general. The term ”robust solution” refers
in the literature to several di?erent notions and here we concentrate only on
one of them. But, generally, ”robust optimal solution” means such a solution,
which will be optimal even if there are changes in the parameters of the decision
situation. Of course, it has to be clari?ed each time what kind of changes is
meant here.
We start with a short review of the goal programming itself and de?ne what
kind of uncertainty in goal programming we will consider here. Then we present
the robust approach known in the literature and ?nally we apply it to the goal
programming in a situation of uncertainty.
2. The goal programming problem considered
If we were to provide a general de?nition of goal programming, it might be
formulated e.g. as follows: goal programming comprises decision problems in
which we have classical mathematical programming constraints and more than
one objective function (more than one goal), while for each objective function
the decision maker gives a target value (a goal) and its type (maximisation,
minimisation, equality). In case of maximisation objective function the decision
maker will be totally satis?ed if the objective function value is equal or greater
than the corresponding target value, for minimisation objective functions the
total satisfaction will be achieved for objective function values equal or less than
the corresponding target value, for objective functions of equality type - only
for objective function equal to the target value. However, as it is often impossi-
ble to attain fully the satisfactory values simultaneously, undesirable objective
function values (less than the target value for maximisation, greater that the
target value for maximisation, di?erent than the target value for equality) are
also accepted by the decision maker, but only to a certain extent.
In the following general goal programming formulation, (1) corresponds to
the objective functions (of minimisation, maximisation and equality type re-
spectively), and (2) to the classical constraints.
C i(x) = d i (i = 1, ..., k 1)
C i(x) = d i (i = k 1+ 1, ..., k 2) (1)
C i(x) = d i (i = k 2+ 1, ..., k 3)
A(x) = B (2)
x = 0.
n
In the above formulation x = (x j) 1 is a vector of non-negative decision vari-
ables, C i is the objective function (non necessarily linear) representing the j-th
goal, (2) is the canonical representation of the classical mathematical program-
Robust goal programming 503
ming constraints (not necessarily linear ones), and d i (i = 1, ..., k 3) stand for
the target values.
The inequality and equality signs in (1) have the “ ” sign over them, which
means that the corresponding relation does not have to be ful?lled completely,
that certain deviations in the undesired direction(s) are allowed.
The deviations from the target values (all of them, for the moment we do
not di?erentiate between the undesired and desired deviations) will be denoted
in the following way:
+ -
d = max(C (x) - d , 0), d = max(d - C (x), 0) (i = 1, ..., k ). (3)
i i i i i i 3
In the classical approach to goal programming it is assumed that the decision
maker wants to minimise the sum (possibly a weighted one) of all the undesired
deviations. Thus, the following objective function is formulated:
k i k 2 k 3
+ + ' - -
w id i + (w id i + w id i ) + w id i ? min (4)
i=1 i=k 1+1 i=k 2+2
'
where w i (i = 1, ..., k 3) and w i (i = k 1+ 1, ..., k 2) are positive weights.
Then, the problem with the objective function (4) and the constraints (2)
and (3) is solved, or rather its equivalent form with n + 2k 3 positive decision
variables:
k i k 2 k 3
+ + ' - -
w id i + (w id i + w id i ) + w id i ? min
i=1 i=k 1+1 i=k 2+2
+ -
C i(x) - d + d = d i, i = 1, ..., k 3 (5)
i i
A(x) = B
+ -
x = 0, d , d = 0 (i = 1, ..., k 3).
i i
Classical goal programming includes also problems with a hierarchy of goals.
Dennis and Dennis (1991) discuss the problem, we will not do it here.
In the paper we will consider a special case of the general model (1). The
limitations introduced to this special case are as follows:
a) we consider only goals of the minimisation type (which comprises the
maximisation case because of the possibility of multiplication by -1)
b) we consider only linear objective functions.
Thus, we consider the following model:
n
c ijx j= d j (i = 1, ..., k 1)
j=1
A(x) = B (6)
x = 0.
504 D. KUCHTA
The corresponding one-objective formulation is:
k i
+
w id i ? min
i=1
j
+ -
c ijx j- d i + d i = d i, i = 1, ..., k 1 (7)
i=1
A(x) = B
+ -
x = 0, d , d = 0 (i = 1, ..., k ).
i i 1
As for the uncertainty, we consider that the coe?cients c ij, i = 1, ..., k 1;
j = 1, ..., n may vary, in?uencing the attainment of goals in a negative way: the
coe?cient of the j-th variable in the i -th constraint will probably take on an
assumed value c , (i = 1, ..., k ; j = 1, ..., n), but it may also happen that it
ij 1
¯
will take on any value from the interval ?c ijc ¯ij?, (i = 1, ..., k 1; j = 1, ..., n). Let
¯
? ij = ¯ c ij, (i = 1, ..., k 1; j = 1, ..., n).
Before we pass on to the next point, let us present an example, based in its
crisp version on an example presented by Dennis and Dennis (1991), which will
accompany us throughout the paper.
Example 2.1 A company manufactures three divisible products. Let x j, j =
1, 2, 3 denote the amount of the respective products to be manufactured in the
coming period. Here is the matrix c ij, i = 1, ..., 4; j = 1, ..., 3, where
a) c 1 (j = 1, ..., 3) represent the most possible (normal) amount of material
j
¯
needed to manufacture the j-th product
b) c 2 (j = 1, ....3) represent the most possible (normal) amount of human
j
¯
work needed to manufacture the j-th product
c) c (j = 1, ..., 3) represent the most possible (normal) amount of machine
3 j
¯
time needed to manufacture the j-th product
d) c 4 (j = 1, ..., 3) represent the most possible (normal) selling price of the
j
¯
j-th product multiplied by -1.
j=1,2,3
Table 1. Matrix [c ij] i=1,2,3,4 for the example
¯
j=1 j=2 j=3
i=1 3 7 5
i=2 6 5 7
i=3 3 6 5
i=4 -28 -40 -32
The right-hand sides of the constraints (7), i.e. the goals (target values)
for the total amount of material used, the total amount of human work used,
the total amount of machine time used and the total turnover multiplied by -1
are, respectively, as follows: 200, 200, 200, -1500. These values should not be
Robust goal programming 505
exceeded, and thus we get the following one-objective problem (we assume that
the weights are equal to 1):
+ + + +
d + d + d + d ? min
1 2 3 4
- +
3x 1+ 7x + 5x 3+ d 1 - d 1 = 200
- +
6x 1+ 5x 2+ 7x 3+ d 2 - d 2 = 200
- +
3x 1+ 6x 2+ 5x 3+ d 3 - d 3 = 200
- +
-28x 1- 40x 2- 32x 3+ d 4 - d 4 = -1500
- +
x 1, x 2, x 3= 0; d , d = 0 (i = 1, 2, 3, 4).
i i
The optimal solution of this problem is as follows: x 1=20.8, x 2=23, x 3=0,
+ + + +
d =23, d =39.5, d =0, d =0.
1 2 3 4
Let us assume that the possible variations of the coe?cients are equal ap-
proximately to 10% of the ”normal” value (see Table 2).
j=1,2,3 j=1,2,3
Table 2. Matrices [¯ c ij] i=1,2,3,4 and [? ij] i=1,2,3,4 for the example
j = 1 j = 1 j = 1
c ¯ij ? ij c ¯ij ? ij c ¯ij ? ij
i = 1 3.3 0.3 7.7 0.7 5.5 0.5
i = 2 6.6 0.6 5.5 0.5 7.7 0.7
i = 3 3.3 0.3 6.6 0.6 5.5 0.5
i = 4 -25.2 2.8 -36 4 28.8 3.2
In case of materials’ usage, the variations may be due to material quality or
the workers’ experience (inexperienced workers produce more waste). In case of
human work the ”normal” values can change because of the lack of experience
or of motivation, and the machine hours needed to manufacture one product
may be in?uenced by the machine failure frequency. The unit prices may go
down (which means an increase of the numbers multiplied by -1) because of the
uncertain market situation.
Now we will present the proposal for a robust optimal solution of the goal
programming problem (6) with variations ? ij (i = 1, ..., k 1; j = 1, ...n) in the
left-hand sides of the goals. These variations can be called ”negative” in the
sense that they in?uence negatively the achievement of goals.
3. Robust solution of the goal programming problem with
possible negative variations in the left-hand sides of
goals
We adopt here the concept of robustness of an optimal solution proposed by
Bertsimas and Sim (2003). They apply it to a mixed integer linear programming
problem with possible variations in the objective function coe?cients and in the
506 D. KUCHTA
left-hand side coe?cients of the constraints. Their idea can be summarized as
follows:
a) A robust optimal solution is such a solution which would be optimal for
the worst possible values of the coe?cients within the assumed variation
possibilities (intervals) - where the worst means minimal for the maximi-
sation of the objective function and for the ”greater-or-equal” constraints
and maximal in the other cases.
b) By applying strictly the above de?nition, we would obtain a ”pessimistic”
case, which would reduce to solving the corresponding problem with coef-
?cients being set at their worst possible values; such a robust solution is
of course very easy to obtain, but its quality (the value of the objective
function) may be not very good; in many cases such an approach may be
too pessimistic, as it assumes that everything may go wrong, that all the
coe?cients may vary in the negative direction simultaneously.
c) Thus, the authors propose, justifying their approach with the behaviour
of nature, to assume that only some coe?cients will indeed change (e.g.
the price of only some products will go down, not of all of them); of
course, we cannot know which ones and in the proposed approach it is
not necessary to choose the coe?cients which we suspect to change; the
only thing required is to say, for the objective function and for each of
the constraints individually, what is in our opinion the maximal number
of coe?cients that may change with respect to the ”normal” value.
By applying this approach to problem (6), with c ij ? ?c ij, c ¯ij?, (i = 1, ..., k 1;
¯
j = 1, ..., n), c being the ”normal” value, we can introduce the notion of the
ij
¯
M-robust solution, where
k 1
M = (m i) i=1 and m i (i = 1, ..., k 1) is an integer number not exceeding n,
chosen by the decision maker, which expresses how many coe?cients in the i -th
constraint can change at the most. If m i = 0 (i = 1, ..., k 1), we assume that
nothing will go wrong and obtain the normal optimal solution. On the other
hand, if m i = n (i = 1, ..., k 1), we get the pessimistic, ”fully robust” solution
mentioned above.
Now we will show how to determine the M-robust solution of (6) for a given
vector M.
4. The single-criterion linear programming problem for
the M-robust solution of the goal programming prob-
lem
As we adopt the model from Bertsimas and Sim (2003) to our needs, we obtain
the following model whose solution will constitute the M-robust solution of (6)
Robust goal programming 507
(|X| denotes the power of set X)
n
c x + max ? x =d (i = 1, ..., k ) (8)
ij j ij j i 1
¯ S i ? {1, ..., n}
j=1 j?S j
|S i| = m i
A(x) = B.
By reformulating the problem (8) in the same way as in the classical goal
programming, we can arrive at the following problem:
k 1
+
w id i ? min
j=1
n
+ -
c ijx j+ max ? ijx j- d i + d i = d i (i = 1, ..., k 1) (9)
¯ S i ? {1, ...n}
j=1 j?S j
|S i| = m i
A(x) = B
+ -
x = 0, d , d = 0 (i = 1, ..., k 1).
i i
The optimal value of the objective function obtained in this way will be the
worst optimal value of the total deviation - when in each goal i (i = 1, ...k 1)
the m i coe?cients are allowed to take on the least favourable (the maximal
possible) values. By changing the values of m i, we can see how this in?uences
the optimal value of the total deviation.
Of course, the above problem is not linear. However, we will transform it
to a linear problem by means of the following lemma proved by Bertsimas and
Sim (2003).
Lemma 4.1 Let ß i(x 1, x 2, ..., x n) = max ? ijx j(i = 1, ...k 1). For each
S i ? { , ...n} 1
j?S j
|S i| = m i
vector (x 1, x 2, ..., x n) and i = 1, 2, ..., k 1, ß i(x 1, x 2, ..., x n), is the optimal objec-
tive function value of the following linear programming problem
n
p ij+ m iz i? min
j=1
z i+ p ij = ? ijx j (j = 1, ..., n) (10)
p ij = 0 (j = 1, ..., n), z i = 0 .
Let us now formulate the following linear programming problem, which, as
we will show afterwards, will give us the M-robust solution of (6):
k 1
+
w 1d i ? min
j=1
508 D. KUCHTA
n n
+ -
c x + p + m z - d + d = d (i = 1, ..., k )
ij j ij i i i i i 1
¯
j=1 j=1
z i+ p ij = ? ijx j (j = 1, ..., n) (i = 1, ..., k 1) (11)
p ij = 0 (j = 1, ..., n), z i = 0 (i = 1, ..., k 1)
A(x) = B
+ -
x = 0, d , d = 0 (i = 1, ..., k ).
i i 1
Theorem 4.1 The optimal function values of (9) i (11) coincide.
-
n + k 1
Proof. If (x j) j=1, (d i , d i ) i=1 is a feasible solution of (9), it is obviously also
(together with the corresponding values of p ij (j = 1, ..., n), z i) a feasible so-
lution of (11). This shows that the objective function value of (11) does not
exceed the objective function value of (9).
n
n
On the other hand, for a ?xed (x j) j=1, from the obvious relation ijc ijx j+
¯
n n
max ? ijx j = c ijx j+ p ij+m iz i, i = 1, ..., k 1, p ij > 0, z i > 0,
S i ? { , ...n} 1 ¯
j?S j j=1 j=1
|S i| = m i
-
n + k 1
it follows that for each feasible solution (x j) j=1, (d i,0, d i,0) i=1 of (9) and for
-
n + k 1 n + +
each feasible solution (x j) j=1, (d i,1, d i,1) i=1, (p ij, z j) j=1 we have (d i,0 = d i,1
(i = 1, ..., k 1).
From this it follows that the optimal function value of (9) does not exceed
the optimal function value of (11), which completes the proof.
5. Computational example
Now we will apply the proposed approach to Example 1. Problem (11) for the
example becomes:
+ + + +
d + d + d + d ? min
1 2 3 4
- +
3x 1+ 7x 2+ 5x 3+ p 11+ p 12+ p 13+ m 1z 1+ d 1 - d 1 = 200
- +
6x 1+ 5x 2+ 7x 3+ p 21+ p 22+ p 23+ m 2z 2+ d 2 - d 2 = 200
- +
3x 1+ 6x 2+ 5x 3+ p 31+ p 32+ p 33+ m 3z 3+ d 3 - d 1 = 200
- +
-28x 1- 40x 2- 32x 3+ p 41+ p 42+ p 43+ m 4z 4+ d 4 - d 4 = -1500
z 1+ p 11= 0.3x 1; z 1+ p 12= 0.7x 2; z 1+ p 13= 0.5x 3;
z 2+ p 21= 0.6x 1; z 2+ p 22= 0.5x 2; z 2+ p 23= 0.7x 3;
z 3+ p 31= 0.3x 1; z 3+ p 32= 0.6x 2; z 3+ p 33= 0.5x 3;
z 4+ p 41= 2.8x 1; z 4+ p 42= 4x 2; z 4+ p 43= 3.2x 3;
-
x i, z i, d i , p ij = 0 (i = 1, 2, 3, 4; j = 1, 2, 3)
where m 1,m 2,m 3,m 4 are parameters - integer numbers less than or equal 3,
selected by the decision maker to ?x his degree of pessimism with respect to
each goal. For the i -th goal, m i expresses how many of the left hand side
Robust goal programming 509
coe?cients of this goal can reach their least favourable value. Here are the
results - the worst optimal value of the total deviation for various values of
m 1,m 2,m 3,m 4, see Table 3.
Table 3. Computational results for the example
m 1,m 2,m 3,m 4 0,0,0,0 0,0,0,3 1,1,1,1 1,1,1,3 2,2,2,2 3,3,3,3
the worst optimal
62.5 125 136.18 172.15 187.33 187.5
total deviation
This approach allows us to evaluate what is the worst possible optimal value
of the total deviation from the goals according to the given situation, i.e. ac-
cording to how ”malicious” the market (the 4th goal) or the machines (the 3rd
goal) may happen to be or how uncertain the material (the 1st goal) or the
human being (the 2nd) goal may turn out. In our example we can see e.g. that
if the market is very uncertain, this in?uences the worst optimal total deviation
very strongly (compare the ?rst two columns of Table 3).
6. Conclusions
To the author’s knowledge, the paper presents the ?rst approach to multiob-
jective programming making use of one of the robust models proposed in the
literature. The approach proposed here might also be called a pessimistic ap-
proach, as it searches for the worst possible optimal value of the total deviation
from the goal - the worst in the assumed (by the decision maker) framework of
possible variations. In other words, the decision maker can ?nd solutions for
various degrees of pessimism or uncertainty, simply by changing one parame-
ter per goal. The solution can be obtained by means of a linear programming
problem, if the goal functions and the other constraints of the original model
are linear.
The research will continue to examine other models of goal programming,
not considered in this paper, but it would be very interesting to see what other
robust approaches (e.g. the one proposed by Ben-Tal and Nemirovsky, 1999
might contribute to multiple objective optimisation.
References
Ben-Tal, A. and Nemirovsky, A. (1999) Robust solutions to uncertain pro-
grams. Oper. Res. Lett. 25, 1-13.
Bertsimas, D. and Sim, M. (2003) Robust discrete optimization and net-
work ?ows. Math. Program. Ser. B 98, 49-71.
Dennis, T.L. and Dennis, L.B. (1991) Management Science. West Publish-
ing Company, St. Paul.
510 D. KUCHTA
Chanas, S. and Kuchta, D. (2002) On a certain approach to fuzzy goal pro-
gramming. In: Trzaskalik T., Michnik J., eds., Multiple Objective and Goal
Programming, Recent Developments. Physica-Verlag, 15-30.
Chanas, S. and Kuchta, D. (2001) A new approach to fuzzy goal program-
ming. In: Proceedings Eus?at 2001 An International Conference in Fuzzy
Logic and Technology, Leicester, UK.
Chanas, S. and Kuchta, D. (2002) Fuzzy goals and crisp deviations - a new
approach to fuzzy goal programming. In: Trzaskalik T., ed., Modelowanie
Preferencji a ryzyko. Akademia Ekonomiczna, Katowice, 61-74.
Chanas, S. and Kuchta, D. (2002) Fuzzy Goal Programming - one notion,
many meanings. Control and Cybernetics 31, 4, 871-890.
.jpg)
