13 Multi-Objective Optimization

Contents | ‹ Previous | Next › | Download EPUB | PDF

Chapter 13
Multi-Objective Optimization

Learning Outcomes

Define multi-objective optimization problems
Discuss solutions in terms of the Pareto Frontier
Explore approaches for finding the Pareto Frontier
Use software to solve for or approximate the Pareto Frontier

You are shopping for a used car. One is $4,000 and twelve years old; another is $9,000 and three years old; a third is $11,000 and eight years old. The third can be dismissed at a glance: the second is cheaper and newer. But between the first two, no calculation can declare a winner: it depends on what a year of age is worth to you, and that is a judgment, not an optimization. Multi-objective optimization is the study of exactly this situation: ruling out the options nobody should ever choose, and mapping the trade-offs among the ones that remain.

13.1 Introduction to Multi-Objective Optimization

Decision makers must often balance competing objectives. Rather than optimizing a single quantity, we seek solutions that trade off different goals, such as cost against quality or efficiency against equity. This leads to the field of multi-objective optimization (MOO), a framework for identifying and analyzing such trade-offs.

To illustrate this, consider a simple inventory and production planning problem over a fixed horizon of $T = 10$ periods. Let $x_{t}$ denote the quantity produced in period $t$ , $s_{t}$ the inventory carried over after period $t$ , and $d_{t}$ the demand to be satisfied during that period. The system begins with $s_{0} = 5$ units of initial inventory. Production costs $c_{t}^{p}$ vary by time, while holding inventory incurs a fixed per-unit cost $c^{h}$ .

The inventory balance constraint for each period is:

s_{t} = s_{t - 1} + x_{t} - d_{t} for all t = 1, \dots, T

The objective function (single-objective version) is to minimize total cost:

\min \sum_{t = 1}^{T} (c_{t}^{p} x_{t} + c^{h} s_{t})

However, holding inventory is not just costly; it also introduces risk. Products may be damaged, stolen, or become obsolete. To capture this additional concern, we define a risk function that models the expected loss due to stored inventory:

r (s_{t}) = c_{r} (1 - e^{- β s_{t}})

where $c_{r}$ is the maximum risk cost and $β$ is a sensitivity parameter. This function grows quickly at first, but saturates as inventory increases, reflecting that the marginal risk of storing more units diminishes with protective measures (e.g., insurance, security systems).

Plot of the inventory risk function r(s) = c_r(1 - exp(-beta*s)) versus inventory level s: a smooth concave curve rising sharply from zero and saturating toward the maximum risk cost c_r, illustrating that marginal risk diminishes as inventory grows. — Figure 13.1: Inventory risk cost as a function of inventory level.

Now we face a multi-objective problem: we want to minimize both total cost and maximum risk incurred across the planning horizon. These objectives are in tension: reducing risk requires keeping inventory low, which often means producing more frequently at higher cost.

To explore the trade-off, we solve the problem repeatedly with varying upper bounds on inventory (i.e., limiting $s_{t} \leq R$ ), and for each value compute:

The optimal total cost (production + holding),
The maximum risk experienced across all periods, computed as $\max_{t} r (s_{t})$ .

This sweep is the $𝜀$ -constraint method, which we define later in the chapter (Section 13.2). The parameter values in this example are illustrative; the computational resources at the end of the chapter (Section 13.3), such as pymoo, make it easy to experiment with instances of your own.

The resulting plot shows the Pareto frontier (defined precisely in Section 13.2) of non-dominated solutions, those for which no other solution achieves both a lower cost and lower risk.

Pareto frontier curve for the multi-objective inventory problem, plotting total cost (horizontal axis) against maximum inventory risk (vertical axis). The downward-sloping non-dominated trade-off curve shows that lower risk can only be achieved by accepting higher cost. — Figure 13.2: Trade-off between total cost and maximum inventory risk.

This example illustrates the essence of multi-objective optimization: generating and analyzing a spectrum of solutions that offer different balances between competing goals. In practice, decision makers select among these using domain knowledge, regulatory limits, or stakeholder preferences.

13.2 Multi-Objective Optimization and the Pareto Frontier

We now make these ideas precise. The central concept is the Pareto Frontier (or Pareto Front), which consists of all solutions for which no objective can be improved without worsening at least one other.

Motivating Example: Furniture Manufacturer Consider a high-end furniture manufacturer that builds dining tables and chairs from expensive bocote and rosewood. The manufacturer receives 960 board-feet (bdft) of bocote and 200 bdft of rosewood per month. Each table requires 80 bdft of bocote and 12 bdft of rosewood; each chair requires 20 bdft of bocote and 10 bdft of rosewood. Let $x$ denote the number of tables and $y$ the number of chairs produced. The feasible production set $P$ is given by:

\begin{aligned} P = {(x, y) \in ℝ^{2} : & 80 x + 20 y \leq 960, \\ 12 x + 10 y \leq 200, \\ x, y \geq 0} . \end{aligned}

Shaded feasible region in the plane of tables (x) and chairs (y), bounded by two blue constraint lines that intersect near (10, 8), with intercepts at 20 chairs and 12 tables. — Figure 13.3: Feasible region for the furniture production problem.

Suppose each table earns $8000 and each chair earns $2000. The goal is to maximize revenue:

Maximize 8000 x + 2000 y subject to (x, y) \in P .

Scaling the objective to $w = 4 x + y$ , the feasible region remains the same but is easier to visualize. Solving this LP reveals multiple optimal solutions on the boundary from $(12, 0)$ to $(10, 8)$ . These all yield the same profit, but they may differ in other criteria.

Now, suppose a new manager wants to minimize material waste, specifically 10 bdft wasted per table and 2 bdft per chair:

Minimize 10 x + 2 y subject to maximum revenue .

Restricting attention to the profit-optimal frontier and minimizing waste identifies $(10, 8)$ as preferable. This is an example of the lexicographic method: optimize a primary objective, then refine solutions with a secondary one.

Alternatively, the manager may be willing to sacrifice some revenue. If they accept at least 70% of maximum profit, they solve:

\begin{aligned} Minimize & 10 x + 2 y \\ subject to & 8000 x + 2000 y \geq 0.7 \times 96000, \\ (x, y) \in P . \end{aligned}

The furniture feasible region with red dashed revenue level lines and a darker shaded strip along the upper-right boundary marking the plans whose revenue is at least 70 percent of the maximum. — Figure 13.4: Feasible set with revenue constrained to at least 70% of the maximum.

This $𝜀$ -constraint method provides flexibility to explore trade-offs, generating new points on the Pareto frontier.

Pareto Optimality Many feasible solutions exist, but only some are Pareto optimal. A solution is Pareto optimal if no other feasible solution improves one objective without worsening another.

Definition 13.1: Pareto Optimal

Given a feasible set $P$ and objective functions $f_{i} : P \to ℝ$ to maximize, a point $x \in P$ is Pareto Optimal if there is no $\bar{x} \in P$ such that:

\begin{aligned} f_{i} (\bar{x}) > f_{i} (x) for some i, \\ f_{j} (\bar{x}) \geq f_{j} (x) for all j \neq i . \end{aligned}

That is, no objective can be strictly improved without sacrificing performance in at least one other. The Pareto Frontier is the set of all such efficient points.

Objective-space plot of rosewood waste f2=10x+2y against revenue f1=8000x+2000y (in thousands of dollars). Blue dots connected by a line mark Pareto optimal plans (the Pareto frontier); red squares lying above the line mark dominated plans, each labeled with its production plan (x, y). — Figure 13.5: The furniture problem in objective space: each point is a production plan $(x, y)$ plotted by its revenue $f_{1}$ (maximize) and rosewood waste $f_{2}$ (minimize). The blue points are non-dominated: no feasible plan earns more revenue without creating more waste, and none creates less waste without giving up revenue. The red points are dominated; for example, $(12, 0)$ earns the same $96,000 as $(10, 8)$ but wastes 120 bdft instead of 116, and $(4, 4)$ matches the revenue of $(0, 20)$ with more waste. The frontier consists of the plans along $x = 0$ and along the rosewood constraint from $(0, 20)$ to $(10, 8)$ .

Summary of Multi-Objective Optimization Methods

Table 13.1: Summary of Multi-Objective Optimization Methods


Method	Key Idea	Pros	Cons

Weighted Sum	Combine objectives into a single scalar using a weighted sum	Simple and computationally efficient	May miss Pareto-optimal solutions in non-convex regions

Lexicographic	Prioritize objectives in strict order	Matches real-world decision hierarchies	Does not explore trade-offs or the full frontier

Epsilon-Constraint	Optimize one objective, treat others as constraints	Finds non-convex parts of the frontier	Requires repeated solves, hard to set $𝜀$

Goal Programming	Minimize deviation from target values	Useful when goals are known	Sensitive to target and weight choices

Elbow (Knee Point)	Pick the frontier point where trade-offs deteriorate fastest	Yields a single balanced compromise	Requires computing the frontier first; not every frontier has a clear knee

Scalarization (Weighted Sum) Method The weighted sum method transforms a multi-objective optimization problem into a single-objective one by combining the objectives linearly. For two objectives $f_{1} (x)$ and $f_{2} (x)$ (both to be minimized), the scalarized problem takes the form:

\begin{array}{l} \min_{x \in X} & w_{1} f_{1} (x) + w_{2} f_{2} (x) \\ s.t. & x \in X, w_{1}, w_{2} \geq 0, w_{1} + w_{2} = 1 . \end{array}

Here, $w_{1}$ and $w_{2}$ represent the relative importance of each objective. Varying the weights traces out the convex portions of the Pareto frontier: each weight vector corresponds to a supporting hyperplane to the feasible region in objective space. While simple and computationally efficient, the method cannot produce Pareto-optimal points lying in non-convex regions of the frontier. Objectives should be normalized before weighting to ensure that units and scales do not distort the trade-off.

Lexicographic Method The lexicographic method ranks the objectives in strict order of priority and optimizes them sequentially: first optimize the most important objective, then optimize the second over the set of solutions that are optimal for the first, and so on. This is what the furniture manufacturer did above: maximize revenue first, then minimize rosewood waste among the revenue-optimal plans, which selected $(10, 8)$ . The method fits settings with a clear hierarchy of goals, but it returns a single solution rather than a picture of the trade-offs.

Goal Programming Goal programming incorporates explicit target values for each objective, seeking solutions that minimize the deviations from these goals. Let $g_{j}$ be the desired goal for objective $f_{j} (x)$ . Introduce positive and negative deviation variables $d_{j}^{+}$ and $d_{j}^{-}$ such that:

\begin{array}{l} f_{j} (x) + d_{j}^{-} - d_{j}^{+} = g_{j}, d_{j}^{+}, d_{j}^{-} \geq 0 . \end{array}

A weighted goal programming model minimizes a weighted sum of deviations:

\begin{array}{l} \min_{x, d^{+}, d^{-}} & \sum_{j = 1}^{m} w_{j} (d_{j}^{+} + d_{j}^{-}), \\ s.t. & x \in X, and the above deviation equations hold. \end{array}

The weights $w_{j}$ reflect the relative penalty for missing each goal. In preemptive (lexicographic) goal programming, objectives are ranked in priority and optimized sequentially, ensuring higher-priority goals are satisfied as well as possible before addressing lower-priority ones.

Elbow (Knee Point) Method When the Pareto frontier is plotted, some decision makers prefer to choose a single compromise point where further improvement in one objective would cause a disproportionately large loss in another. This elbow or knee point is often found where the curvature of the frontier is largest. For discrete Pareto points, a common heuristic is:

1.: Identify the extreme solutions (best in each objective).
2.: Draw the straight line connecting these extremes in objective space.
3.: Compute the perpendicular distance of each Pareto point to this line.
4.: Select the point with the largest distance as the elbow.

In more formal terms, for a smooth frontier $(f_{1} (t), f_{2} (t))$ , the knee corresponds to the value of $t$ maximizing the curvature:

\begin{array}{l} κ (t) = \frac{| f_{1}^{'} (t) f_{2}^{″} (t) - f_{2}^{'} (t) f_{1}^{″} (t) |}{{[{(f_{1}^{'} (t))}^{2} + {(f_{2}^{'} (t))}^{2}]}^{3 ∕ 2}} . \end{array}

Not all Pareto fronts have a clear elbow, and objectives should be normalized to avoid scale bias.

Epsilon-Constraint Method The $𝜀$ -constraint method selects one objective as the primary optimization target and converts all other objectives into constraints with adjustable bounds. For two objectives $f_{1} (x)$ and $f_{2} (x)$ (both to be minimized), one might solve:

\begin{array}{l} \min_{x \in X} & f_{1} (x) \\ s.t. & f_{2} (x) \leq 𝜀, \\ x \in X, \end{array}

where $𝜀$ is varied across a range of values to generate the Pareto frontier. This method can find both convex and non-convex portions of the frontier, unlike the weighted sum approach. The main practical challenge is choosing meaningful $𝜀$ values and step sizes. Graphically, this corresponds to sweeping a horizontal (or vertical) constraint across the feasible objective region and optimizing within each slice.

13.2.1 Applications of Pareto Frontiers

Although our furniture example was small, multi-objective optimization arises naturally in many fields. In each case below, the decision-maker faces competing objectives and must choose a preferred trade-off along the Pareto frontier.

Portfolio Optimization

In finance, the classical Markowitz model seeks portfolios that trade off expected return against risk (variance of return). Given $n$ assets with expected return vector $μ \in ℝ^{n}$ and covariance matrix $Σ \in ℝ^{n \times n}$ , the bi-objective problem is

\max μ^{⊤} w, \min w^{⊤} Σ w, subject to 1^{⊤} w = 1, w \geq 0 .

The Pareto frontier of this problem is the well-known efficient frontier: a curve in the risk–return plane. Every portfolio on this curve is Pareto optimal; portfolios below it are dominated (higher risk for the same return, or lower return for the same risk).

Engineering Design

Mechanical and aerospace engineers routinely face multi-objective trade-offs. For example, in aircraft wing design the objectives might include minimizing weight (for fuel efficiency), minimizing drag (for speed), and minimizing manufacturing cost, all subject to structural safety constraints. The Pareto frontier reveals which designs are non-dominated, allowing the engineer to select a final design that best matches operational priorities. Similar trade-offs arise in automotive design, where ride comfort, fuel economy, and acceleration performance compete.

Healthcare Staff Scheduling

Hospitals scheduling nurses and physicians must balance staffing cost against quality-of-care and workload fairness. Adding staff to a shift reduces patient-to-nurse ratios and overtime fatigue but increases cost; concentrating shifts among fewer workers saves money but hurts fairness and increases burnout risk. A bi-objective model minimizing total staffing cost and, say, the maximum number of undesirable shifts assigned to any one nurse produces a Pareto frontier of schedules. Administrators can then see exactly how much each improvement in fairness costs, rather than committing to a single weighting in advance.

Supply Chain and Sustainability

Firms increasingly aim to minimize both cost and environmental impact in their supply chains. A manufacturer might seek to minimize total logistics cost while also minimizing carbon emissions from transportation. Cheaper shipping routes (e.g., by truck over longer distances) may produce more emissions than costlier alternatives (e.g., rail). The Pareto frontier shows the achievable trade-offs, helping firms meet sustainability targets at the lowest additional cost.

13.3 Computational Tools for Multi-Objective Optimization

Resources

For problems with more than two or three objectives, or with large numbers of decision variables, the exact methods discussed above (weighted sum, $𝜀$ -constraint) can become computationally expensive. In practice, multi-objective evolutionary algorithms (MOEAs) are widely used to generate high-quality approximations of the Pareto frontier.

Several well-known algorithms are available for this purpose:

NSGA-II: (Non-dominated Sorting Genetic Algorithm II) is one of the most widely used MOEAs. It maintains a population of candidate solutions and uses non-dominated sorting together with a crowding distance metric to preserve diversity along the Pareto front. NSGA-II is effective for problems with two or three objectives.
NSGA-III: extends NSGA-II to handle many-objective problems (four or more objectives) by using reference directions instead of crowding distance to maintain a well-distributed set of solutions across the Pareto frontier.
MOEA/D: (Multi-Objective Evolutionary Algorithm based on Decomposition) decomposes the multi-objective problem into a collection of single-objective subproblems using weight vectors, solving them simultaneously. This approach is particularly effective when the Pareto frontier has a regular structure.

The Python library pymoo provides implementations of these algorithms and many others, along with built-in test problems, performance metrics, and visualization tools for Pareto fronts. It offers a convenient way to experiment with multi-objective optimization without implementing algorithms from scratch.

For small problems like the furniture example, the $𝜀$ -constraint method needs nothing more than an ordinary LP solver. The following PuLP script maximizes revenue while sweeping the bound on rosewood waste, recovering points on the Pareto frontier:

import pulp

for eps in [40, 60, 80, 100, 116]:
   prob = pulp.LpProblem("furniture", pulp.LpMaximize)
   x = pulp.LpVariable("tables", lowBound=0)
   y = pulp.LpVariable("chairs", lowBound=0)
   prob += 8000*x + 2000*y # revenue (primary objective)
   prob += 80*x + 20*y <= 960 # bocote
   prob += 12*x + 10*y <= 200 # rosewood
   prob += 10*x + 2*y <= eps # waste <= epsilon
   prob.solve(pulp.PULP_CBC_CMD(msg=0))
   print(f"eps={eps}: x={x.value():.2f}, y={y.value():.2f}, "
       f"revenue={pulp.value(prob.objective):.0f}")

Sweeping $𝜀$ from 40 to 116 traces the frontier from the plan $(0, 20)$ with revenue $40,000 up to $(10, 8)$ with revenue $96,000, passing through fractional plans such as $x \approx 5.26$ , $y \approx 13.68$ with revenue $69,474 at $𝜀 = 80$ .

13.4 Exercises

Warm-ups

Exercise 13.2: Defining Pareto Optimality

$⋆$ Define Pareto optimality for a minimization multi-objective problem with two objectives.

[Section 13.2]

Exercise 13.3: Spotting Dominated Designs

$⋆$ Five supplier contracts are scored on two objectives, both to be minimized: $f_{1}$ (cost, in $1000s) and $f_{2}$ (delivery time, in days).

Contract	G	H	I	J	K

$f_{1}$	2	4	5	7	6
$f_{2}$	9	7	8	3	5

Table 13.2: Cost and delivery time for the five supplier contracts.

1.: Which contracts are dominated, and by which contract?
2.: List the Pareto frontier in order of increasing $f_{1}$ .
3.: True or false: a contract that is the unique minimizer of $f_{1}$ can never be dominated. Explain.

[Section 13.2, Exercise 13.5]

Exercise 13.4: Computing Weighted-Sum Scores

$⋆$ Using the contract table from Exercise 13.3, form the weighted score $S = w_{1} f_{1} + w_{2} f_{2}$ (both objectives minimized, so the lowest score wins).

1.: For $(w_{1}, w_{2}) = (0.6, 0.4)$ , compute all five scores and identify the winning contract.
2.: Repeat for $(w_{1}, w_{2}) = (0.2, 0.8)$ . Why does the winner change?
3.: Contract I is dominated by contract H. Show that for every choice of weights $w_{1}, w_{2} > 0$ , contract I scores strictly worse than H, so a dominated point can never win a weighted sum with positive weights.

[Section 13.2]

Core problems

Exercise 13.5: Pareto Frontier, Weighted Sum, and $𝜀$ -Constraint

$⋆ ⋆$ Consider the following feasible set of designs with two objectives to minimize: $f_{1}$ (cost) and $f_{2}$ (emissions). The table lists six candidates from a design study; some may be dominated among this set.

Design	A	B	C	D	E	F

$f_{1}$	6	4	7	3	5	10
$f_{2}$	5	8	4	6	6	3

Table 13.3: Cost and emissions for the six candidate designs.

1.: Identify all Pareto optimal designs from ${A, \dots, F}$ and list the Pareto frontier.
2.: Suppose we use a weighted-sum with weights $(α, 1 - α)$ , $α \in [0, 1]$ . Which designs can be obtained as optimal for some $α$ ? Briefly justify.
3.: Using the $𝜀$ -constraint method minimizing $f_{1}$ subject to $f_{2} \leq 𝜀$ , give a value of $𝜀$ that attains a design on the frontier that cannot be obtained by any weighted sum (if any), or explain why all frontier points are reachable by weighted sums.
4.: Sketch (by hand) the points in the $(f_{1}, f_{2})$ plane, indicate dominated points, and draw the Pareto frontier with arrows showing the direction of improvement.

[Section 13.2, Table 13.1]

Exercise 13.6: Weighted Sum Method

$⋆ ⋆$ A city planner is evaluating three road improvement projects. Each project has a cost (to minimize) and an accessibility score (to maximize):

Project	Cost ($M)	Accessibility Score

P1	2	7
P2	5	9
P3	3	6

Table 13.4: Cost and accessibility score for each road improvement project.

We reformulate as a minimization problem with objectives $f_{1} = cost$ and $f_{2} = - accessibility$ (so both are minimized).

1.: Which projects are Pareto optimal? Justify your answer.
2.: Using the weighted-sum method with weights $w_{1} = 0.5$ for cost and $w_{2} = 0.5$ for negative accessibility, which project is selected?
3.: Is there a set of weights that would select project P3? Explain.

[Section 13.2]

Exercise 13.7: Epsilon-Constraint Method

$⋆ ⋆$ Consider a bi-objective linear program:

\min (f_{1} (x), f_{2} (x)) = (x_{1} + 2 x_{2}, 3 x_{1} + x_{2})

subject to $x_{1} + x_{2} \geq 4$ , $x_{1} \leq 5$ , $x_{2} \leq 5$ , and $x_{1}, x_{2} \geq 0$ .

1.: Apply the $𝜀$ -constraint method: minimize $f_{1}$ subject to $f_{2} \leq 𝜀$ . Write out the resulting single-objective LP.
2.: Find the optimal solution for $𝜀 = 10$ and for $𝜀 = 6$ . Are both solutions Pareto optimal?
3.: Describe what happens as $𝜀$ decreases from a large value toward $f_{2}^{*}$ (the minimum of $f_{2}$ alone).

[Section 13.2, Section 13.3]

Exercise 13.8: Epsilon-Constraint by Hand

$⋆ ⋆$ Consider two objectives to maximize, $f_{1} = 3 x_{1} + x_{2}$ and $f_{2} = x_{1} + 3 x_{2}$ , over the triangle

X = {(x_{1}, x_{2}) \geq 0 : x_{1} + x_{2} \leq 6} .

1.: Evaluate both objectives at the three vertices of $X$ . Which vertex maximizes $f_{1}$ alone? Which maximizes $f_{2}$ alone?
2.: Apply the $𝜀$ -constraint method: maximize $f_{1}$ subject to $f_{2} \geq 𝜀$ and $x \in X$ , for each $𝜀 \in {6, 10, 14, 18}$ . Solve each LP by hand (graphically, or by checking the vertices of the sliced region) and tabulate $(x_{1}, x_{2}, f_{1}, f_{2})$ .
3.: Which part of the boundary of $X$ is the Pareto frontier in decision space? What is the trade-off rate between $f_{1}$ and $f_{2}$ along it?
4.: What happens if $𝜀 > 18$ ?

[Section 13.2, Section 13.3]

Exercise 13.9: Trade-Off Analysis

$⋆ ⋆$ A manufacturing firm faces two conflicting objectives: minimizing production cost ( $f_{1}$ ) and minimizing environmental emissions ( $f_{2}$ ). After solving a series of weighted-sum problems, the following Pareto optimal solutions are found:

Solution	$f_{1}$ (Cost, $1000s)	$f_{2}$ (Emissions, tons)

S1	40	20
S2	45	14
S3	55	10
S4	70	8

Table 13.5: Pareto optimal solutions found by the weighted-sum method.

1.: Plot these points in the objective space. Draw the Pareto frontier.
2.: Compute the marginal rate of substitution (trade-off ratio) between each consecutive pair of solutions. Which jump in cost gives the largest reduction in emissions per dollar?
3.: If the firm is willing to spend at most $50,000, which Pareto optimal solution should it choose?

[Section 13.2]

Concepts and connections

Exercise 13.10: What Weighted Sums Cannot See

$⋆ ⋆$ A design study produces exactly three Pareto optimal outcomes in objective space, both objectives minimized:

P = (0, 4), Q = (3, 3), R = (4, 0) .

1.: Verify that no one of these points dominates another.
2.: For weights $(α, 1 - α)$ with $α \in [0, 1]$ , write the weighted score of each point as a function of $α$ and show that $\min {4 α, 4 - 4 α} \leq 2 < 3$ for every $α$ . Conclude that $Q$ is never a weighted-sum optimum, not even tied.
3.

[Section 13.2, Table 13.1]

Exercise 13.11: Lexicographic versus Weighted Sum

$⋆ ⋆$ In the furniture example of Section 13.2, the lexicographic method (maximize revenue first, then minimize waste among revenue-optimal plans) selects $(10, 8)$ .

1.: A weighted sum with all weight on revenue ( $α = 1$ ) maximizes $8000 x + 2000 y$ alone. Which plans are optimal then, and why does this not reproduce the lexicographic answer?
2.: Argue that any weight $α < 1$ close enough to $1$ selects exactly $(10, 8)$ : the small weight on waste acts as a tie-breaker among revenue-optimal plans while being too small to justify giving up revenue. (Exercise 13.12 computes the exact threshold.)
3.: When do the two methods agree in general? Explain why for a linear program with finitely many vertices there is always a sufficiently extreme weight that reproduces the lexicographic solution, and describe informally what can go wrong if the weight on the secondary objective is not small enough.

[Section 13.2, Table 13.1]

Challenge problems

Exercise 13.12: Weights That Select Each Vertex

$⋆ ⋆ ⋆$ Return to the furniture example of Section 13.2. Measure revenue in thousands of dollars, so the objectives are $f_{1} = 8 x + 2 y$ (maximize) and $f_{2} = 10 x + 2 y$ (minimize, waste in bdft). The weighted-sum method solves

\max_{(x, y) \in P} α f_{1} (x, y) - (1 - α) f_{2} (x, y), α \in [0, 1] .

1.: The optimum is always attained at a vertex of $P$ : $(0, 0)$ , $(0, 20)$ , $(10, 8)$ , or $(12, 0)$ . Write the weighted objective value of each vertex as a linear function of $α$ .
2.: For each Pareto optimal vertex, find the exact interval of $α$ for which it is optimal, and give the breakpoint values of $α$ .
3.: What is optimal exactly at each breakpoint, and at $α = 1$ ? Explain why the dominated vertex $(12, 0)$ shows up at $α = 1$ and what this says about using zero weights.
4.: Repeat part (2) with revenue in raw dollars ( $f_{1} = 8000 x + 2000 y$ ). Where are the breakpoints now? What does this tell you about normalizing objectives before choosing weights?

[Section 13.2, Table 13.1]

Selected Solutions

Solution

(Exercise 13.2) For a problem minimizing $f_{1}$ and $f_{2}$ over a feasible set $P$ , a point $x \in P$ is Pareto optimal if there is no $\bar{x} \in P$ with $f_{i} (\bar{x}) \leq f_{i} (x)$ for both $i = 1, 2$ and $f_{i} (\bar{x}) < f_{i} (x)$ for at least one $i$ . In words: no other feasible point is at least as good in both objectives and strictly better in one.

Solution

(Exercise 13.5) (1) Compare pairs for domination (both objectives minimized). $D = (3, 6)$ dominates $B = (4, 8)$ . $E = (5, 6)$ is dominated by $D$ ( $3 \leq 5$ , $6 \leq 6$ ). $A = (6, 5)$ is not dominated. $C = (7, 4)$ is not dominated. $F = (10, 3)$ is not dominated. The Pareto frontier is ${D, A, C, F}$ with objective vectors $(3, 6), (6, 5), (7, 4), (10, 3)$ .

(2) A design is a weighted-sum optimum for some $α$ exactly when it lies on the lower-left convex hull of the frontier points. Plotting $(3, 6), (6, 5), (7, 4), (10, 3)$ , the lower convex hull is formed by $D$ , $C$ , and $F$ , while $A$ lies above it: $D$ (best $f_{1}$ ) and $F$ (best $f_{2}$ ) are always obtainable, and $C$ lies on the hull between them, but $A$ sits above the segment from $D$ to $C$ (slope check: from $D$ to $C$ , $Δ = (4, - 2)$ ; $A$ at $(6, 5)$ vs. the segment value $6 - \frac{2}{4} (6 - 3) = 4.5 < 5$ ), so $A$ cannot be obtained by any weighted sum.

(3) Choose $𝜀 = 5$ : minimizing $f_{1}$ subject to $f_{2} \leq 5$ selects $A = (6, 5)$ , the frontier point unreachable by weighted sums.

Solution

(Exercise 13.8) (1) At $(0, 0)$ : $(f_{1}, f_{2}) = (0, 0)$ . At $(6, 0)$ : $(18, 6)$ . At $(0, 6)$ : $(6, 18)$ . So $(6, 0)$ maximizes $f_{1}$ alone and $(0, 6)$ maximizes $f_{2}$ alone.

(2) For $𝜀 > 6$ the constraint $x_{1} + 3 x_{2} \geq 𝜀$ is binding at the optimum, and the solution lies where it meets the edge $x_{1} + x_{2} = 6$ : solving the two equations gives $x_{2} = (𝜀 - 6) ∕ 2$ , $x_{1} = (18 - 𝜀) ∕ 2$ .

$𝜀$	$x_{1}$	$x_{2}$	$f_{1}$	$f_{2}$

6	6	0	18	6
10	4	2	14	10
14	2	4	10	14
18	0	6	6	18

Table 13.6: Solutions of the

𝜀

-constraint problem as

𝜀

varies.

(3) Each solution has $f_{2} = 𝜀$ exactly and the largest possible $f_{1}$ given that, so each is Pareto optimal. The frontier is the edge $x_{1} + x_{2} = 6$ from $(6, 0)$ to $(0, 6)$ : parametrizing by $x_{2} = t$ gives $f_{1} = 18 - 2 t$ and $f_{2} = 6 + 2 t$ , a one-for-one trade-off between the objectives.

(4) The maximum of $f_{2}$ over $X$ is $18$ , so for $𝜀 > 18$ the constrained LP is infeasible; the sweep should stop there.

Solution

(Exercise 13.12) (1) The weighted objective $α (8 x + 2 y) - (1 - α) (10 x + 2 y)$ at each vertex:

(0, 0) : 0, (0, 20) : 80 α - 40, (10, 8) : 212 α - 116, (12, 0) : 216 α - 120 .

(2) The optimal value is the upper envelope of these four linear functions of $α$ . Comparing pairs: $(0, 20)$ beats $(0, 0)$ iff $80 α - 40 \geq 0$ , i.e., $α \geq \frac{1}{2}$ ; $(10, 8)$ beats $(0, 20)$ iff $212 α - 116 \geq 80 α - 40$ , i.e., $132 α \geq 76$ , i.e., $α \geq \frac{19}{33} \approx 0.576$ ; and $(10, 8)$ beats $(12, 0)$ iff $4 \geq 4 α$ , which holds for all $α \leq 1$ . Hence

(0, 0) optimal for α \in [0, \frac{1}{2}], (0, 20) for α \in [\frac{1}{2}, \frac{19}{33}], (10, 8) for α \in [\frac{19}{33}, 1] .

A numerical sweep confirms the switch: $α = 0.5757$ returns $(0, 20)$ and $α = 0.5758$ returns $(10, 8)$ .

(3) At $α = \frac{1}{2}$ the entire edge $x = 0$ is optimal (every plan $(0, y)$ scores $0$ there); at $α = \frac{19}{33}$ the whole rosewood edge from $(0, 20)$ to $(10, 8)$ is optimal. At $α = 1$ waste is ignored, so all revenue-optimal plans, the edge from $(10, 8)$ to $(12, 0)$ , are optimal, including the dominated plan $(12, 0)$ . A weighted sum with a zero weight can return points that are not Pareto optimal; any positive weight on waste breaks the tie in favor of $(10, 8)$ .

(4) With $f_{1} = 8000 x + 2000 y$ , the same comparisons give breakpoints $α = \frac{1}{1001} \approx 0.001$ and $α = \frac{19}{14019} \approx 0.00136$ : virtually every weight selects $(10, 8)$ . When objectives live on wildly different scales, the weights lose their intended meaning, which is why objectives should be normalized before weighting (Section 13.2).

Chapter 13Multi-Objective Optimization

Chapter 13
Multi-Objective Optimization