Multiobjective optimization

Goal programming is one way of dealing with conflicting objectives, but it requires the assessment of weights and targets. Unfortunately, it may be very difficult, or even unethical, to figure out weights. As an example, consider the tradeoff between the cost of a production process and its pollution level. Sometimes, we would like to visualize the tradeoff between conflicting requirements. Moreover, it would be nice to see which solutions can be safely ruled out, in a sense that we can illustrate by a small example.

Example 12.13 Consider a problem involving two objectives, f₁(x) and f₂(x), that we wish to minimize. Solutions are best visualized on a plane illustrating how solutions score with respect to both objectives. Consider the three alternative solutions x_a, x_b, and x_c depicted in Fig. 12.10. If we compare x_a and x_b, which solution is the better one? Actually, it depends on our point of view: x_a is better in terms of the second objective, since 4 < 9, but x_b is preferable in terms of the first objective, since 5 < 10. Unless we assign some priority or weight to objectives, there is no way to rank the two alternatives. However, if we compare x_b against x_c, the answer should be obvious: x_b is better from both points of view, so no decision maker interested in objectives f₁ and f₂ should choose x_c, which is a “dominated” solution.

From a mathematical perspective, each feasible solution is characterized by a vector of objective values; hence, we could consider a “vector” optimization problem:

However, stated as such, the problem has no meaning, and this is why we use “min.” As the example above illustrates, vectors are not a well-ordered set. Given any pair of distinct points on the real line, we may say which one is larger, but we cannot rank vectors on a plane in the same way: The number 5 is larger than the number 2, but we cannot compare vectors [10 4]^T and [5 9]^T that easily. True, we can say that a vector is longer than another one by referring, e.g., to the Euclidean concept of vector length. However, this means that we are aggregating different components of the vector into a single number, using the Euclidean norm. In multiobjective optimization we could consider, e.g., weighted sums to transform a vector of objectives into a single one; this operation is called scalarization, as it transforms a multidimensional vector into a scalar, i.e., a single number. Choosing a scalarization is easy, if we can sensibly aggregate several objectives into a single one. However, this may be very difficult to do because:

• Objectives may be associated with different stakeholders, and assigning weights may be a tough “political” decision.
• Some objectives may be difficult to express and compare on a common ground, e.g., money.

Of course, in the end, we must choose one solution, and this choice may involve qualitative and political considerations that do not lend themselves to a quantitative assessment; nevertheless, we might try at least to spot the reasonable solutions to evaluate the tradeoffs between them. If anything, this should ease conflicts, or make them more transparent and objective. The intuition from Fig. 12.10 is that we may not be able to spot one “optimal” solution, but at least we may eliminate unreasonable alternatives from further consideration. In other words, we should just concentrate on efficient solutions.

DEFINITION 12.9 Given the vector optimization problem (12.45), a feasible solution x* is said to be an efficient²⁴ or nondominated solution, if there is no other solution  such that

Fig. 12.11 Schematic illustration of the concept of efficient solution.

Fig. 12.12 The efficient frontier in the continuous case.

with a strict inequality for at least one of the two objectives. The set of nondominated solutions is called the efficient frontier.

The idea may be easily grasped by having a look at Fig. 12.11. We see that there is not necessarily one optimal solution, but rather a set of “reasonable” solutions to which we may restrict the choice, ruling out dominated alternatives. In a continuous mathematical program, the efficient frontier might be a continuous curve, as illustrated in Fig. 12.12. What we can do to help the decision maker is to generate the set of efficient solutions, which is a subset of the whole set of feasible solutions. To this aim, we can scalarize the problem according to some strategy, boiling the vector problem down to a family of single-objective optimization problems depending on one or more parameters. By changing the parameters, we may trace the efficient frontier.

Fig. 12.13 A trivial scalarization may not be able to detect all of the efficient solutions.

The first and perhaps more intuitive approach is to devise a weighted linear combination of the two objectives. We introduce a parameter λ, bounded by 0 and 1, which expresses the relative importance of the objectives; letting λ span its range, we solve a sequence of problems

Note that the parameter λ has no precise economic meaning, as it is just a tool for spanning the efficient frontier. This approach is clearly intuitive and related to the idea of varying a set of weights. We have the guarantee that all of the solutions we generate this way are efficient; however, there is no guarantee that all of the efficient solutions will be generated. The issue is illustrated in Fig. 12.13, where the dotted lines correspond to level curves of the scalarized objective, for different values of weights. It is easy to see that two of the three efficient solutions can be detected by changing weights, but one cannot. This does not occur in Fig. 12.12, where the plot of the efficient frontier looks essentially like a convex function. In a discrete optimization case, we cannot be sure to generate the whole efficient frontier by a trivial scalarization based on a linear combination of objectives. More complicated scalarizations have been proposed to overcome this difficulty.

An alternative approach is based on the idea of transforming one objective into a constraint. In other words, we can optimize f₁, subject to the constraint that f₂ cannot exceed some limit (or vice versa):

Solving a family of scalar problems for varying values of , we may trace the efficient frontier. It is worth noting that this second approach does not suffer from the aforementioned difficulty with the weighted combination approach, but the most important feature, arguably, is that it is more “readable” for a decision maker.²⁵ While the parameter λ has no obvious managerial meaning, the value of  is much more readable; it is a threshold level, which might be chosen by having a look at what competitors do. For instance, if we have to trade off service level against inventory holding cost, having an idea of what service level is offered by competitors helps a lot in choosing a sensible threshold.