Norm-Based Approximation in Bicriteria Programming.
An algorithm to approximate the nondominated set of continuous and discrete bicriteria programs is proposed. The algorithm employs block norms to find an approximation and evaluate its quality. By automatically adapting to the problem's structure and scaling, the approximation is constructed objectively without interaction with the decision maker. Mathematical and practical examples are included.
Introduction
In view of increased computational power and enhanced graphic capabilities
of computers, approximation of the solution set for bicriteria programming
has been a research topic of special interest. Since bicriteria programs feature
only two criteria, their solution set can be visualized graphically which
signicantly faciliates decision making. In this vein, researchers have given
This work was partially supported by ONR Grant N00014-97-1-0784.
Research Assistant, Department of Mathematical Sciences, Clemson University, Clem-
son, SC.
3 Associate Professor, Department of Computer Science and Mathematics, University
of Applied Sciences Dresden, Dresden, Germany.
4 Associate Professor, Department of Mathematical Sciences, Clemson University,
special attention to developing approximation methods that yield a representation
or description of the solution set rather than to further studying
scalarization approaches that had been extensively examined earlier.
Below we review approximation approaches specically developed for bi-criteria
programs. We focus on methods that are based on exact algorithms
for the solution of scalarization problems and were applied to example problems

Cohon (1978) and Poliscuk (1979) independently develop similar approximation
approaches for linear and convex bicriteria problems, respectively.
The weighted-sum scalarization is employed to nd nondominated points
and the l 2 norm is used as an estimate of the accuracy of the approxima-
tion. Fruhwirth et al. (1989) propose a sandwich algorithm to approximate
a convex curve in IR 2 and apply it to the bicriteria minimum cost
ow
problem. The curve is approximated by two piecewise linear functions, one
above and one below the curve. The curve's derivative is used to partition
a coordinate axis. Yang and Goh (1997) use the derivative of the upper approximation
instead. For both algorithms the approximation error decreases
quadratically with the number of approximation points. Jahn and Merkel
(1992) propose a reference-point-approach for general bicriteria programs
and give attention to avoid nding local optima. The approach produces
a piecewise linear approximation of the nondominated set. Payne (1993)
proposes to approximate the nondominated set of a general bicriteria problem
by rectangles, each dened by two nondominated points. Das (1999)
brie
y discusses an approach based on the Normal-Boundary Intersection
technique. A direction orthogonal to a line dened by two nondominated
points is used to nd a new nondominated point. The identied point has
the maximal l 1 distance from the approximation in the considered region.
The following two approaches are, to our knowledge, the only ones that
give a closed-form formula for an approximating function of the nondominated
set rather than a set of approximating points or a piecewise linear
approximation of the nondominated set. Approximating the nondominated
set of a convex bicriteria problem by a hyper-ellipse is proposed in Li et al.
(1998) and Li (1999). The technique requires three nondominated points
and their choice aects the quality of approximation. In Chen et al. (1999)
and Zhang et al. (1999), quadratic functions are used to locally approximate
the nondominated set of a general bicriteria problem in a neighborhood of
a nondominated point of interest. By performing the procedure for several
nondominated points, a piecewise quadratic approximation of the whole
nondominated set can be generated.
In this paper, we propose to approximate the solution set of bicriteria
programs by means of block norms. Using block norms to generate nondominated
points has several implications: the norm's unit ball approximates
the nondominated set and, at the same time, the norm evaluates the feasible
points as well as the quality of the current approximation.
y.
We consider the following general bicriteria program:
s. t. x 2 X;
(1)
is the feasible set and f 1 (x) and f 2 (x) are real-valued func-
tions. We dene the set of all feasible criterion vectors Z and the set of all
globally nondominated criterion vectors N of (1) as follows
t. ~
z  zg;
T . We assume that the set Z is closed and
nonempty, and that there exists a point u so that Z  u
0g. It follows that the set N is nonempty, see, for
example, Sawaragi et al. (1985, pp. 50{51).
The point z  2 IR 2 with
z
is called the utopia (ideal) criterion vector where the components of
are small positive numbers.
The point z  2 IR 2 with
z
is called the nadir point.
In Section 2, we present the methodological tools we use to construct the
approximation. Section 3 contains the approximation algorithm featuring
specic procedures depending on the structure of the problem. Examples
and case studies illustrating the performance of the algorithm are presented
in Section 4, and Section 5 concludes the paper.
In this section, we discuss approaches to generating nondominated points
used in the proposed approximation algorithm. Furthermore, the algorithm
relies on the usage of block norms, a well-known concept in convex analysis.
Block norms are norms with a polyhedral unit ball. A cone generated by
two neighboring extreme points of a unit ball is called a fundamental cone.
The partition of the unit ball into fundamental cones is used extensively in
our methodology.
Let
be an oblique norm 5 with the unit ball B. Given a
reference point z 0 (without loss of generality z
program yields a globally nondominated point, see Schandl (1999):
s. t. z 2 Z \ (z 0 IR 2
(2)
In the algorithm, the norm
with the center at z 0 , as used in (2), is being
constructed and used to generate new nondominated points.
Solving (2) requires a calculation of the norm
. As shown in Hamacher
and Klamroth (1997), it is su-cient to know in which fundamental cone
5 An oblique norm is a block norm where no facet of the unit ball is parallel to any
coordinate axis. For details see Schandl (1999).
a point z is located to calculate its norm
(z). Let
be a polyhedral
norm with the unit ball B  IR 2 . Let z 2 C where
a fundamental cone, that is, C is generated by the two extreme points v i
is the unique representation
of z in terms of v i and v j then
Let z i and z j be two nondominated points in z 0 IR 2
. To guarantee that
a point z is in the cone su-cient to require
Using (3), the general norm problem (2) restricted to a cone can be
formulated as:
s. t.
Given an optimal solution (
z) of (4),
z is globally nondominated. Observe
that problem (4) generates a nondominated point independently of
the existence of a norm.
Besides the norm-based approach described above, we use two other
techniques to generate globally nondominated solutions. Following Steuer
and Choo (1983), we reformulate the lexicographic Tchebyche method for
the cone
lex min kz ~
z  k w
z  k 1
s. t.
where ~ z  is the local utopia point for the cone, see Section 3.4. We rst
minimize the weighted Tchebyche norm between the local utopia point
and a feasible point. If there is no unique solution in this rst step, we
minimize the l 1 distance among all the solutions of the rst step. Given
an optimal solution (
z) of (5),
z is globally nondominated, see Schandl
(1999).
A direction method introduced in Pascoletti and Serani (1984) is mod-
ied in Schandl (1999). We use this method to search for globally nondominated
points in the entire set Z. Let z
1. Then the problem
lex
s. t.
has a nite solution (;
q), where
z is a globally nondominated point.
3 Approximation Algorithm
In this section, the algorithms for an IR 2
-nonconvex and discrete
feasible set Z are proposed. The algorithms in all three cases are very
similar, so we rst present the general algorithm and then point out special
features of the dierent cases.
3.1 General Strategy
The approximation algorithm is based on the successive generation of non-dominated
points using the methods described in Section 2. The basic idea
is to generate points in the areas where the nondominated set is not yet well
approximated. The approximation quality is evaluated using the approximation
itself by interpreting it as part of the unit ball of a block norm.
We explain the algorithm for the IR 2
case using Figure 1. To
start, we need a reference point z
. This might be a currently
implemented (not nondominated) solution or just a (not necessarily feasible)
6 A set Z is called
is convex.
guess. Without loss of generality, we assume throughout the section that
the reference point is located at the origin.
z 0
(a)
z 0
(b)
z 0
z 3
(c)
z 0
z 3
(d)
z 0
z 3
z 4
z 0
z 3
z 4

Figure

1: The steps of the approximation algorithm
To approximate the nondominated set in z 0 IR 2
, we rst explore the
feasible set along the directions ( 1; 0) and (0; 1) to nd z 1 and z 2 using the
direction method (6). These two points together with the reference point z 0
are used to dene a cone and a rst approximation, see Figure 1(b).
In a cone we search for a new candidate point to add to the approxima-
tion. Constructing new cones within the rst cone, we get a ner approximation
of the nondominated set while generating nondominated points and
updating the norm. Depending on the structure of the feasible set Z (IR 2
we use the norm method (4) and/or the
lexicographic Tchebyche method (5). For more details see Sections 3.3,
3.4 and 3.5. Interpreting the approximation as the lower left part of the
unit ball of a norm with z 0 as its center, we can calculate the distance of a
point
z from the current approximation as dev(z) := j
(z) 1j, which we
call the deviation of
z. Whenever possible, we add a point of worst approximation
by substituting two new cones for the cone in which this new point
is located.
3.2 Description of the Algorithm
The algorithm accepts the following input.
1. A reference point z
can be specied. If it is not given then
z 0 := z  is used as a default.
2. Initial search directions can be given. There are three possibilities:
(a) At least two directions d
are given.
(b) An integer randDirNo  2 is given, which denes the number of
random directions in IR 2
which are generated.
(c) No directions are given; then the default directions d 1 := (
and d 2 := (0; 1) are used.
The directions are sorted in counterclockwise order. Let the number
of directions be k  2.
3. There are two possible stopping criteria; usually, at least one of them
must be given. The rst one is an upper bound  > 0 on the maximal
deviation. As soon as we get dev(z) <  for a point that should be
added next, the algorithm stops. The other possibility is to give an
integer maxConeNo  1, which species the maximum number of cones
to be generated.
The algorithm starts by solving the direction method (6) for all directions
d i and dening l initial cones. Note that l is not necessarily equal
to k 1 because two directions may generate the same nondominated point.
Now we nd a candidate to add in each cone, each having a deviation
from the current approximation associated with it. How this candidate is
found diers for the three types of problems and is described in the subsections
below.
Finally the main loop of the algorithm starts. If the maximum number
of cones maxConeNo was already constructed, the loop stops. Otherwise, the
candidate
z with the maximum deviation is considered. If this deviation is
smaller than , the loop stops. Otherwise, two new cones are constructed in
place of the cone containing
z, candidate points for the new cones together
with their deviations are calculated and the points are added to the list of
candidates.
At the end of the loop the sorted list of r nondominated points is printed
and can be used to visualize the approximated nondominated set. In the
-convex case, the approximation is in the form of an oblique norm's unit
ball with an algebraic description Az 5 e, where A is an (r 1)  n matrix
and e is the vector of ones.
The algorithm is summarized in Figure 2. The procedure Calculate
Candidate depends on the structure of the feasible set. Suitable procedures
for
-nonconvex and discrete feasible sets are given in

Figures

3 and 5.
3.3 Convex Case
For the IR 2
-convex case, the candidate in a cone is found by the norm
method (4). By taking the candidate with the maximal deviation, we globally
maximize the norm and the resulting point is guaranteed to be globally
nondominated. Note that the deviation is implicitly given by the solution
of (4) because, due to (3), the optimal objective value of (4) is equal to the
candidate's norm, that is,
Given the set of extreme points of the approximation, we can easily nd
Procedure: Bicriteria Approximation
Read/generate z 0 , d i , , maxConeNo
for all d i do
Solve direction method
end for
Construct cones
for all cones do
Call Calculate Candidate
end for
while #cones < maxConeNo and dev(next point)   do
Add next point
Construct new cones
for all new cones do
Call Calculate Candidate
end for
while
Output approximation

Figure

2: Pseudo code of the approximation algorithm
a representation of the approximation in the form Az 5 e. Since z
line connecting two neighboring extreme points includes the origin. Given
two points z i and z i+1 , we calculate row i of the matrix A as follows:
a
z i+1and a
The procedure to calculate a candidate is summarized in Figure 3.
Procedure: Calculate Candidate
Solve norm method to nd  z and dev(z)

Figure

3: Finding a candidate in a cone for an IR 2
Setting the stopping criteria to can lead to an
innite running time for a general IR 2
considering numerical
problems). On the other hand, these settings can be useful for the special
case of a polyhedral set Z, since in this case our algorithm is able to nd
the exact nondominated set.
Consider a polyhedral feasible set Z. There are two cases for the location
of the points z i and z j when solving (4). Either both extreme points of the
approximation are on the same facet or they are on dierent (not necessarily
neighboring) facets.
Since (4) is a linear program if Z is polyhedral, its optimal solution is an
extreme point or a facet of the feasible set. We thus either nd a new point to
add to the approximation or the identied point has a deviation of 0 in which
case the cone is not considered anymore. The necessary number of iterations
is O(k) where k is the number of extreme points of the nondominated set
because in each iteration we either nd an extreme point or we eliminate a
cone from further consideration.
3.4 Nonconvex Case
Finding a candidate in a cone for an IR 2
-nonconvex feasible set is a two-stage
procedure. We rst try to nd a candidate \outside" the approxima-
tion; if this fails, we look for a candidate \inside". Thus we give a priority
to constructing the convex hull of the nondominated set before we further
investigate nonconvex areas.
Finding a candidate \outside" is done with the same method as for
-convex sets, that is, we use problem (4) exercising its applicability in
the absence of a norm. If the deviation of the candidate found by this
method is too small, that is, smaller than , we switch to a method using
the Tchebyche norm in order to investigate whether the nondominated set
is
-convex in this cone and its approximation is already good enough or
whether the nondominated set is IR 2
-nonconvex and a candidate has to be
found in the interior of the approximation. For a cone dened by the two
points z i and z i+1 , we rst calculate the local utopia and the local nadir
point:
~
z
z
Using these two points, we calculate the weights for a Tchebyche norm
whose unit ball's center is ~ z  and whose upper right corner is ~
z  , see

Figure

4.
The weights thus are
~
z
z
2:
z 0
z
~
z
~
z

Figure

4: The Tchebyche norm for a nonconvex area
We then use the lexicographic Tchebyche method (5) to nd a candidate
for this cone. Having found a candidate
z, its deviation is calculated
using (3). The norm can also be calculated using the equality constraint
of (5) because
Note that the candidate found using this two-stage procedure is not
necessarily the point of worst approximation. If the candidate has already
been found using program (4), it is the point of worst approximation among
all points \outside" the current approximation in this cone. Finding a point
with the lexicographic Tchebyche method|that is, in the second stage|
does not imply anything about how well this point is currently approximated
in comparison with other points. So it might happen that we miss a point
with a larger deviation than the candidate
z we are considering. But unless
the deviation of  z is so small that the cone is not further considered, there
is a good chance that the point with the larger deviation is found in a later
iteration. The procedure to calculate a candidate is summarized in Figure 5.
Procedure: Calculate Candidate
Solve norm method to nd  z and dev(z)
if dev(z) <  then
Calculate ~
z  and ~ z
Use lexicographic Tchebyche method to nd  z
Calculate dev(z)

Figure

5: Finding a candidate in a cone for an IR 2
3.5 Discrete Case
The approach for the discrete case is exactly the same as for the IR 2
nonconvex case, that is, we rst use the norm method to search for a candidate
\outside" the approximation; if we nd none (or only one with a small
deviation), we search \inside" using the Tchebyche method.
Since using the Tchebyche method might lead to NP-hard problems,
see, for example, Warburton (1987) or Murthy and Her (1992), we develop an
alternative approach for the discrete case that uses cutting planes and does
not need two stages. Since this approach is not used in our implementation,
we only give a brief outline and refer the reader to Schandl (1999) for more
details. This approach might lead to NP-hard problems as well but there
are cases where the Tchebyche method leads to NP-hard problems while
the approach based on cutting planes does not.
The idea of the cutting-plane-approach is to restrict the feasible region
to an open rectangle dened by the two generators of the cone because this
is the only area within this cone where nondominated points can be located.
Then the norm method (4) is used to identify a candidate for this cone. If we
nd a candidate \outside" the current approximation, that is, a candidate
with a deviation large enough, we have a point of worst approximation and a
suitable point to add to the approximation. But if a point is found \inside"
the approximation, it is actually a point of best approximation. Therefore it
may happen quite often that a cone is excluded from further consideration
too early.
Independently of the choice of an approach to examine the interior of
the approximation, the algorithm enumerates all nondominated points if we
use the stopping criteria
The procedure to calculate a candidate using the Tchebyche method is
the same as for the IR 2
-nonconvex case, see Figure 5.
3.6 A Note on Connectedness
While the nondominated set of an IR 2
set is always connected, see
Bitran and Magnanti (1979) or Luc (1989), the nondominated set of an
-nonconvex problem might be disconnected. An indicator for disconnectedness
is the fact that we do not nd any new nondominated point in a
cone, neither in the interior nor in the exterior of the approximation. Since
we are able to identify disconnectedness in this way, we can remove such a
cone so that the resulting nal approximation is a disconnected set as well.
Thus our approximation is suitable for problems with connected and with
disconnected nondominated sets.
3.7 Properties of the Algorithm
The approximation algorithm for general bicriteria problems presented in
this section has many desirable properties some of which are, to our knowl-
edge, not available in any other approximation approach.
In each iteration, the subproblems (4) and/or (5) are only solved in
two new cones. Thus results from previous iterations are reused and no
optimization over the whole approximated region is necessary. Instead of
adding an arbitrary point in each iteration, our goal is to add the point of
worst approximation and to maximize the improvement in each iteration.
While this property does not always hold in the IR 2
-nonconvex and discrete
cases, it always holds in the IR 2
case. If the algorithm is interrupted
or stopped at a particular point (for example because the maximum allowed
number of cones has been constructed), the approximation has a similar
quality for the whole nondominated set.
While the points of the approximation are in general not nondominated
or even not feasible, all extreme points of the approximation are nondom-
inated. Even in the IR 2
case, points of the approximation may be
infeasible if the feasible set Z is \very thin" or even only a line. If all points
of the approximation are feasible though, we have constructed an inner approximation
of the nondominated set.
Using a norm induced by the problem (or, more precisely, by the approximation
of its nondominated set) avoids the necessity to choose, for
example, an appropriate norm, weights or directions to evaluate or estimate
the quality of the current approximation. The induced norm evaluates
the approximation quality and simultaneously generates suitable additional
points to improve the approximation. Since the quality of the approximation
is evaluated by the norm, the stopping criterion  for the maximal deviation
is independent of the scaling. Indeed, the norm automatically adapts to the
given problem and yields a scaling-independent approximation.
Additionally, the constructed norm can be used to evaluate and compare
feasible points in z 0 IR 2
. A nondominated point has a norm greater or
equal while a norm between 0 and 1 for a point
z indicates that there is
a \better" point in the direction from z 0 to
z. The norm of a point
z can
be interpreted as a measure of quality relative to the maximal achievable
quality in the direction of
z.
While it is often convenient to have the reference point generated by
the algorithm, which is then the nadir point, choosing a specic reference
point can be used to closely explore a particular region of the nondominated
set. The automatically generated reference point can be used to construct
a global approximation of the entire nondominated set while a manually
chosen reference point helps to examine the structure and trade-os of the
nondominated set in a specic region. Thus the choice of the reference point
can be used to \zoom into" regions of interest. For examples see Section 4.
Finally, the algorithm works essentially in the same way for
and
problems. If the structure of the feasible set Z is un-
known, we can apply the algorithm described in Section 3.4. However, if the
problem is in fact
additional (unnecessary) computation
have to be performed. Not nding a candidate with a large enough deviation
in the exterior of the approximation in the IR 2
-convex case is an indicator
that the approximation is already good enough in the corresponding cone.
In the IR 2
case though, the Tchebyche method is used to search
for a candidate in the interior of the approximation which is unnecessary in
the
case because there cannot be a nondominated point in the
interior of the approximation. But the disadvantage of performing some
additional calculations is clearly outweighed by the fact that no information
concerning the structure of the feasible set Z is necessary. If the information
that the feasible set is IR 2
-convex is available, the specialized algorithm
presented in Section 3.3 should be used of course.
4 Examples and Case Studies
The approximation algorithm presented in Section 3 was implemented using
C++, AMPL, CPLEX, MINOS and gnuplot. The C++ program keeps lists of
points and cones and formulates mathematical programs which are solved
by AMPL, CPLEX and MINOS. Finally, the results are written to text les
which gnuplot uses to create two-dimensional plots.
4.1 Convex Example
Consider the following
t.
The solutions for 10 and 40 cones are shown in Figure 6. The approximation
is already very good for 10 cones and improves only slightly for 40 cones.
A small cusp can be seen at f(3; in both gures. At this point,
the rst two constraints hold with equality. The rst constraint denes the
nondominated set to the left of the cusp, the second one to the right of the
cusp.
The corresponding matrix for 10 cones, rounded to two decimals, looks
as follows:

0:49 0:48 0:463 0:45 0:42 0:39 0:25 0:19 0:12 0:04
0:03 0:03 0:04 0:04 0:04 0:05 0:06 0:06 0:06 0:06
All entries are positive, because A denes the oblique norm in the quadrant
. The rows of A dene the facets of the approximation from the
right to the left.1216202428
z 0

Figure

Approximation of (7)
4.2 Nonconvex Example
We present an IR 2
example taken from Zhang (1999):
s. t. x 1
Two interesting properties of our approximation algorithm can be seen in

Figure

7, depicting the approximation for dierent numbers of cones.
The approximation rst constructed by the algorithm is similar to the
convex hull of the nondominated set. Even when using cones for the
approximation it is not yet apparent that the problem is
The reason is that the algorithm uses only the norm method as long as it
nds candidates with a deviation larger than  (which was set to 0:0001 in
this example). When it does not nd such a candidate in a cone, it switches
to the Tchebyche method to examine the interior of the approximation
and \discovers" the nonconvexity in the big cone, see Figures 7(c) and 7(d).
This illustrates that the choice of  can in
uence the approximation process.
As in the IR 2
-convex example above, we see that areas with a big curvature
induce numerous cones so that the linear approximation adapts to
the nonlinear nondominated set. Our results agree with those obtained by
Zhang (1999) using the Tchebyche scalarization.
4.3 Case Study: Evaluation of Aircraft Technologies
We now present a bicriteria model to evaluate aircraft technologies for a
new aircraft. The model was proposed in Mavris and Kirby (1999) and the
data was provided by the Aerospace Systems Design Laboratory at Georgia
Institute of Technology. They can be found in Schandl (1999).
The model is a bicriteria problem of the form
t. 1  x
The functions f 1 (x) and f 2 (x) are modeled as Response Surface Equations:
where the coe-cients b i and b ij are found by regression. The Hessian of
z 0
(c)
z 0
z 0

Figure

7: Approximation of (8)
neither of the functions f 1 (x) and f 2 (x) is positive or negative (semi)denite.
The decision variable in the problem is a vector of nine so-called \k" fac-
tors. The impact of a technology is mapped to such a vector, so every
technology has a specic vector assigned to it. Not all technologies aect
all components of the vector. While the problem is thus discrete, the goal
of this model is to identify the values of \k" factors that are benecial for
the objective functions. Then technologies with corresponding vectors can
be further investigated. All \k" factors are normalized to the range [
and represent a change from the value of the currently used technologies.
The two criteria are the life cycle cost (including research cost, production
cost, and support cost) to be minimized and the specic express power
(measure of maneuverability) to be maximized.
The results of the approximation algorithm for 10 and 29 cones are shown
in

Figure

8. Our approximation agrees with the simulation results obtained
at the Aerospace Systems Design Laboratory, see Schandl (1999).
z 0
(b) 29 cones

Figure

8: Approximation of
There are two areas with an accumulation of constructed points in Figure
8(b). We examine these areas more closely by manually setting the
reference point to (0:671; 728) and (0:652; 683), respectively. The corresponding
approximations are shown in Figures 9(a) and 9(b). In Figure 9(a),
no reason for the accumulation of constructed points is apparent. Figure 9(b)
on the other hand shows a small nonconvex area of the nondominated set.
z 0
(a) 13 cones, z
z 0
(b) 19 cones, z

Figure

9: Approximation of
Being able to choose the reference point in this way demonstrates a
strength of our approximation approach. By simply resetting this point, we
are able to closely examine \suspicious" areas or areas of special interest.
Thus the approximation approach can be used both to get a general impression
of the entire nondominated set and to \zoom into" areas of interest
without changing the underlying algorithm.
An extended model includes a constraint and is discussed in Schandl
(1999).
4.4 Case Study: Choosing Aordable Projects
We now consider the problem of selecting the most aordable portfolio of
projects so that two criteria are maximized subject to a budgetary con-
straint. The model and data were taken from Adams et al. (1998) and
Hartman (1999).
There are 24 projects in which the decision maker can invest. Depending
on the model, the decision maker can invest in each project exactly once
(binary variables) or a positive number of times (integer variables). The goal
is to maximize the net present value (NPV) of investment and to maximize
the joint application or dual use (JA/DU) potential of the chosen projects.
The latter is a score assigned to each project by an expert. The investment
has to be made with respect to a budgetary constraint. The problem is
formulated as a bicriteria knapsack problem:
c 1i x i
c 2i x i
s. t.P
a
x binary or nonnegative integer,
where the parameters are explained in Table 1. The values of the parameters
are given in Schandl (1999).
Parameter Explanation
c 1i NPV of investment for project i in millions of dollars,
c 2i JA/DU score for project i,
a i Total cost of project i over three years in hundreds of
thousands dollars,
Total budget in hundreds of thousands of dollars

Table

1: Explanation of parameters in (10)
The approximation for the binary variable x is shown in Figure 10(a).
Our approximation algorithm nds all twelve nondominated solutions given
in Hartman (1999).
Allowing the variable x to be a nonnegative integer instead of binary
yields many more solutions. The approximation of (10) for the nonnegative
integer variable x is shown in Figure 10(b). In fact, the approximation nds
all 54 nondominated solutions that, according to personal communications,
Hartman found using her implementation of a dynamic-programming-based
algorithm generating all nondominated points.
z 0
(a) Binary variables10002000300040005000
z 0
(b) Integer variables

Figure

10: Approximation of (10)
Conclusions
In this paper we introduced a new approximation approach for bicriteria pro-
grams. Block norms are used to construct the approximation and evaluate
its quality.
The algorithm combines several desirable properties. Whenever possi-
ble, the approximation is improved in the area where \it is needed most"
because in each iteration, a point of worst approximation is added. The
algorithm is applicable even if the structure and convexity of the feasible
set is unknown. Given this knowledge though, more e-cient versions can
be applied. Using the approximation or a norm induced by it to improve
the approximation releases the decision maker from specifying preferences
(in the form of weights, norms, or directions) to evaluate the quality of the
approximation.
The algorithm yields a global piecewise linear approximation of the non-dominated
set which can easily be visualized. For
a closed-form description of the approximation can be calculated. For all
problems, the trade-o information provided by the approximation can be
used in the decision-making process. While the approximation is carried out
objectively, the subjective preferences must be (and should be) applied to
single out one (or several) nal result(s).
In the future, we plan to employ global optimization techniques for the
single objective subproblems in order to handle problems with disconnected
nondominated set and/or local minima.



--R


The Structure of Admissible Points with Respect to Cone Dominance.
Quality Utility
Multiobjective Programming and Planning.
An Improved Technique for Choosing Parameters for Pareto Surface Generation Using Normal-Boundary Intersection
Approximation of convex curves with application to the bicriterial minimum cost ow problem.
European Journal of Operational Research
Planar Location Problems with Barriers under Polyhedral Gauges.
Implementation of Multiple Criteria Dynamic Programming Procedures for A

Reference Point Approximation Method for the Solution of Bicriterial Nonlinear Optimization Problems.
Approximating the Pareto Set of Convex Bi-Criteria Optimization Problems to Aid Decision Making in Design
Approximating Pareto Curves Using the Hyper-Ellipse

Technology
Solving Min-Max Shortest-Path Problems on a Network



Theory of Multiobjective Optimization

An Interactive Weighted Tchebyche
Approximation of Pareto Optima in Multiple- Objective
A method for convex curve approximation.
European Journal of Operational Research
An Interactive Multiobjective Robust Design Proce- dure
Local Approximation of the E-cient Frontier in Robust Design
--TR

--CTR
Bernd Schandl , Kathrin Klamroth , Margaret M. Wiecek, Introducing oblique norms into multiple criteria programming, Journal of Global Optimization, v.23 n.1, p.81-97, May 2002
nondominated points;block norms;approximation;bicriteria programs