6 - Multi-Objective & Robust Optimization

Today begins with a disagreement. One teammate wants the cheapest plan, another wants the safest plan, and the client insists that service quality cannot fall. Nobody is necessarily wrong. The modeling mistake would be to hide that disagreement inside one unexplained score.

This blog develops two related ideas. Multi-objective optimization makes conflicting goals visible instead of pretending they are one. Robust optimization asks whether a chosen decision survives reasonable errors in the data. Our real competition case comes from 2024 MCM Problem A, where Outstanding papers modeled how environmentally responsive sex ratios alter sea-lamprey populations and surrounding ecosystems. It is a natural multi-objective problem: suppress an invasive population, preserve ecosystem stability, and avoid an intervention so aggressive that it creates a new failure.

Two promises, two tests

A multi-objective model promises that the trade-off has been exposed. A robust model promises that feasibility or performance survives a declared uncertainty set. Neither promise is fulfilled by adding the words “comprehensive” or “robust” to a weighted score.

1. Why One Objective Is Often Dishonest

Suppose a city chooses bus frequency . Annual cost decreases when buses are removed, passenger waiting decreases when buses are added, and emissions depend on both fleet use and congestion. There is no physically meaningful unit in which dollars, minutes, and tonnes can simply be added.

Write the vector objective

contains hard rules such as fleet size, driver hours, and minimum coverage. The optimizer no longer returns “the” smallest vector because vectors are only partially ordered. A plan can be cheaper but slower. The result we need is a set of efficient compromises, followed by a transparent decision rule.

Separate hard constraints from soft objectives. If every district must receive at least one bus per hour, that is usually a constraint, not another weighted preference. Turning a legal or safety minimum into a small penalty permits the optimizer to violate it whenever another term pays enough.

2. Pareto Dominance and the Efficient Frontier

For minimization, decision dominates if

and at least one inequality is strict. A feasible point is Pareto efficient if no other feasible point dominates it.

Consider four plans with (cost, average wait):

dominates : it is cheaper and faster. None of dominates another, so they form the discrete Pareto set. Removing is a mathematical conclusion; choosing among is a value judgment.

For a smooth continuous frontier , the slope is the local exchange rate: how many minutes of waiting can be reduced by accepting one more unit of cost. A “knee” is a region where small improvement in one objective suddenly requires a large sacrifice in another. Knee points are useful candidates, not automatic answers.

Stop and compare

If Plan P costs 2% more than Plan Q but cuts worst-district waiting by 30%, which plan is better? You cannot answer until you know whether equity is a hard requirement, whose waiting is measured, and how much budget flexibility exists. Write those missing facts before choosing weights.

3. Weighted Sums and Their Limits

Normalize objectives before weighting. A common formulation is

Without normalization, the objective with the largest numerical scale controls the result. Weights then express relative importance on the chosen normalized ranges; they are not discovered by the solver.

For convex feasible objective sets, varying positive weights can recover supported Pareto points. For a nonconvex frontier, some efficient points lie in concave regions and cannot minimize any weighted sum. This is why a sweep over weights is not always a complete frontier.

Weights should be tested, not merely announced. Draw a weight simplex or vary one weight across a grid. Record when the chosen plan changes. If selects one plan and selects a completely different one, report the decision boundary instead of presenting one set of weights as objective truth.

4. Epsilon Constraints, Goal Programming, and Minimax Regret

The epsilon-constraint method selects one primary objective and turns the rest into bounds:

Sweeping can recover non-supported efficient points. It also matches stakeholder language: “minimize cost while keeping average wait below eight minutes and emissions below the current level.”

Goal programming introduces positive and negative deviations from targets :

The objective penalizes only the deviations that matter. For a maximum emissions cap, is undesirable while performing better than the cap need not be rewarded. Lexicographic goal programming optimizes priority levels sequentially so a tiny improvement in a lower-priority goal cannot purchase a large violation of a higher-priority one.

Under scenarios , regret compares a decision with the scenario-specific best:

Minimax regret solves . It does not seek the best average outcome; it seeks the decision whose worst hindsight disappointment is smallest.

5. What Exactly Is Uncertain?

Do not use “uncertainty” as one undifferentiated word. At least four forms matter:

• measurement error: observed input differs from the true quantity;
• parameter uncertainty: a fitted coefficient is estimated from finite data;
• process variability: arrivals, weather, or demand genuinely vary;
• structural uncertainty: the equations omit a mechanism or use the wrong causal form.

Robust optimization handles declared parameter sets well. It cannot repair a missing mechanism. If the bus model ignores passengers abandoning long queues, widening a demand interval does not correct the structure.

An interval creates a box uncertainty set. An ellipsoid , , captures correlated directions. A finite scenario set is appropriate when the uncertainty is naturally described by named futures. The set must be large enough to include plausible errors but not so large that it represents physically impossible combinations.

6. Deriving Robust Counterparts

Consider uncertain resource usage

For a box and , the worst case independently raises every coefficient:

For signed , introduce through , giving

The robust counterpart remains linear.

For ellipsoidal uncertainty , ,

So the robust constraint is

an SOCP. The price of protection is visible: larger shrinks the feasible set.

Budgeted uncertainty avoids assuming every coefficient reaches its worst value simultaneously. With normalized deviations and , the parameter controls how many coefficients may be adverse together. Plot objective value and constraint violations across rather than hiding the protection choice.

7. Robust Is Not the Same as Stochastic

Stochastic optimization requires probability distributions and optimizes expectations, chance constraints, or risk measures. Robust optimization requires an uncertainty set and protects against every member. Distributionally robust optimization protects against every distribution in an ambiguity set.

A chance constraint

permits violation with probability at most . It can be less conservative than worst-case robustness, but only if the probabilistic model is credible. Scenario testing after optimization is not the same as embedding the probability statement in the optimization.

Use robustness when feasibility failure is costly and only ranges are defensible. Use stochastic models when repeated outcomes and probability estimates are meaningful. Use both when appropriate: optimize expected service while robustly protecting a safety constraint.

8. Outstanding-Paper Case: 2024 MCM Lamprey Ecology

The 2024 MCM Problem A concerns a population whose larval sex ratio can respond to food availability. Outstanding papers in COMAP’s results archive analyze stage dynamics and ecological effects. Recast the decision as an intervention intensity over time. A simplified state model is

where contains lamprey stages and ecosystem indicators, and contains survival, fecundity, food response, and interaction coefficients.

A policy may minimize three outcomes:

rewards control, limits intervention burden, and protects ecosystem balance. Instead of selecting weights immediately, generate a frontier between control and ecological deviation while imposing an intervention budget as a hard constraint.

Food-response uncertainty matters. Let the female-share response be

The slope and midpoint may be poorly known. Define plausible ranges or a jointly plausible ellipse, then require population safety thresholds for all selected parameter scenarios. A nominal policy may exploit a precise response threshold that disappears when shifts. A robust policy intervenes earlier or more gradually.

Validation should compare four objects: the no-action baseline, the nominal optimum, a robust compromise, and a deliberately adverse parameter scenario. Report population reduction, ecosystem deviation, intervention effort, and the number of tested scenarios violating thresholds. The model is useful when it clarifies which protection costs little and which requires a genuine policy choice.

9. Frontier Stability and Decision Validation

A beautiful frontier can be numerically or statistically fragile. Recompute it under data resampling, alternative normalizations, and plausible uncertainty sets. Match points by decision or objective neighborhood and display bands rather than one precise curve.

Check dominance with tolerances; solver noise can make nearly identical points appear to dominate each other. Remove infeasible points before ranking. For discrete models, a frontier can contain gaps and jumps; do not connect points with a smooth line that suggests unattainable intermediate compromises.

Perform an out-of-sample stress test. The uncertainty set used during optimization is part of the model; the stress scenarios used for evaluation should also include surprises outside that set. Robustness is not immunity. State where protection was guaranteed, where performance was only simulated, and which structural failures remain untested.

10. Writing the Recommendation

A responsible report shows the frontier before choosing a point, explains normalization and weights, identifies hard constraints, and quantifies the cost of protection. A useful final sentence sounds like this:

Plan B costs 3.2% more than the nominal minimum but keeps all service constraints feasible across the declared demand set and reduces worst-scenario regret by 41%; beyond this point, each additional 1% of cost buys less than 0.2% regret reduction.

That statement tells the reader what was traded, over what uncertainty, and why the selected point is defensible.

For the easter egg, look back at plans in Section 2. Add a fifth plan —identical to . The Pareto set has not changed, but a careless program may report two “different” solutions. Decide whether duplicates should be merged by objective values or retained because their underlying decisions differ. That tiny choice becomes important when a frontier contains several operationally distinct ways to achieve the same score.

Sources

• COMAP 2024 MCM/ICM results and Outstanding papers .
• COMAP previous contests archive .
• CUMCM official archive .
• Boyd and Vandenberghe, Convex Optimization.