Scalarization

Scalarization (also scalarisation) is a family of techniques in multi-objective optimization that reduce a problem with several conflicting objectives to one or more single-objective problems, each of which can be solved by ordinary single-objective methods. A scalarizing function aggregates the objective vector into a single real-valued objective, typically using weights and sometimes a reference point; by varying these parameters, a solver traces out different points of the Pareto-optimal set. Scalarization is one of the most widely used strategies for generating trade-off surfaces because it lets practitioners reuse mature single-objective algorithms, but the choice of scalarizing function determines which parts of the Pareto front are reachable at all.

Background

A multi-objective optimization problem seeks to minimize (or maximize) a vector of objective functions $f(x)=(f_1(x),\dots ,f_k(x))$ over a feasible set. Because the objectives generally conflict, there is usually no single point that optimizes all of them simultaneously; instead one seeks Pareto-optimal (or efficient) solutions, for which no objective can be improved without worsening another. The image of the Pareto-optimal set in objective space is called the Pareto front. A point is termed supported if it lies on the boundary of the convex hull of the attainable objective set, and unsupported otherwise; this distinction is central to understanding which scalarizations can recover which points. Scalarization turns the problem of characterizing this front into a sequence of scalar minimizations, each parameterized differently, so that solving many scalarized problems approximates the whole front.

Weighted-sum scalarization

The simplest scalarization is the weighted sum, which minimizes $\sum _{i=1}^k{w}_i{f}_i(x)$ for nonnegative weights $w_i$ that sum to one. For any strictly positive weight vector, the optimum of the weighted sum is Pareto-optimal, so sweeping the weights produces a set of efficient points. The method is attractive because it preserves convexity and linearity: if the underlying problem is a linear or convex program, the weighted-sum problem is one too, and it can be solved with standard solvers. For convex problems, every Pareto-optimal point can in principle be obtained as the solution of some weighted-sum problem.

Why weighted sums miss concave regions

The weighted sum has two well-documented limitations. First, it can only recover Pareto-optimal points that lie on the convex hull of the attainable objective set—the supported points—so any point in a concave (nonconvex) portion of the front is unreachable no matter how the weights are chosen. Geometrically, minimizing a weighted sum is equivalent to sliding a hyperplane with fixed slope until it first touches the attainable set; on a concave stretch of the front the hyperplane jumps past the interior points and touches only the endpoints. Second, even where the front is convex, an evenly spaced set of weights does not generally yield an evenly spaced set of Pareto points, so the front can be sampled very unevenly. These drawbacks motivated alternative scalarizations that do not rely on convexity.

Weighted Chebyshev (achievement) scalarization

The weighted Chebyshev method (also weighted Tchebycheff) minimizes the weighted $L_{\mathrm{\infty }}$ distance to a reference point, typically an ideal or utopia point $z^{\ast }$ that lower-bounds each objective: it minimizes $\underset{i}{\max }{w}_i|f_i(x)-z_i^{\ast }|$. Unlike the weighted sum, the Chebyshev scalarization can reach every Pareto-optimal point—including those in concave regions—by an appropriate choice of weights, a property that holds for both convex and nonconvex problems. Intuitively, the level sets of the weighted Chebyshev norm are right-angled contours whose corner can be steered into a concavity, so the touching point can fall on an unsupported part of the front where a flat hyperplane could not.

The pure Chebyshev function has a technical drawback: its optimum is guaranteed only to be weakly Pareto-optimal, and some optima may be weakly efficient but dominated. To exclude these, an augmented weighted Chebyshev function adds a small weighted-sum term, $\underset{i}{\max }{w}_i|f_i(x)-z_i^{\ast }|+\rho \sum _i(f_i(x)-z_i^{\ast })$ with a small $\rho >0$, which restores proper Pareto-optimality while retaining the ability to reach nonconvex points. This makes the augmented Chebyshev family a common default when the shape of the front is unknown or suspected to be nonconvex.

Epsilon-constraint method

The ε-constraint (epsilon-constraint) method keeps one objective as the optimization target and converts the remaining objectives into inequality constraints bounded by parameters ${\epsilon }_i$; systematically varying the bounds generates different efficient points. Because it does not aggregate the objectives into a single weighted line, the ε-constraint method can also reach unsupported points in nonconvex regions of the front, unlike the weighted sum. Its main practical costs are that the choice of bounds requires knowledge of sensible objective ranges, and that a naïve grid of bounds can produce infeasible or weakly-efficient subproblems unless the constraints are handled carefully. Ehrgott and colleagues describe generalizations, such as the method of elastic constraints, that unify the weighted-sum and ε-constraint ideas and are guaranteed to generate all Pareto-optimal solutions.

Choosing a scalarization

The practical guidance in the multi-objective literature is that the weighted sum is the cheapest and most solver-friendly option but is safe only when the Pareto front is known to be convex; when the front may be concave, an achievement-type function such as the augmented weighted Chebyshev, or the ε-constraint method, is preferred because either can recover the full front. More general achievement scalarizing functions, which measure distance from a decision-maker's reference point and are central to interactive methods, extend the Chebyshev idea and can produce any Pareto-optimal solution by moving the reference point through objective space.

Relevance to workforce management

Staffing and scheduling problems in workforce management are naturally multi-objective: a schedule trades service level or answer speed against labor cost, and often against fairness, adherence, or agent preference. When such trade-offs are collapsed into a single weighted cost function—for example, a linear penalty combining understaffing cost and overtime cost—the resulting model is a weighted-sum scalarization, and by the reasoning above it can only expose trade-off configurations on the convex hull of the achievable service-versus-cost frontier. If the true frontier has concave stretches, a weighted-sum staffing model will silently skip those roster options regardless of how the penalty weights are tuned, which is one reason planners exploring a full cost–service trade-off curve may prefer an ε-constraint formulation (optimize cost subject to a service-level floor, then sweep the floor) or a Chebyshev-style objective. These are general implications of the scalarization theory rather than claims specific to any one WFM system.

See also

• Pareto efficiency
• Mathematical optimization
• Portfolio optimization
• Conditional value at risk