--- name: Multi-Objective Exploration slug: multi-objective-exploration category: Automation description: Multi-Objective Exploration traces and interprets Pareto frontiers for multi-objective optimization problems by orchestrating repeated single-objective cuOpt solves (weighted-sum and ε-constraint). Use it when objectives conflict and the user needs the tradeoff curve, not a single weighted answer. github: "https://github.com/NVIDIA/skills/tree/main/skills/cuopt-multi-objective-exploration" language: Python stars: 2973 forks: 345 install: "npx degit https://github.com/NVIDIA/skills/tree/main/skills/cuopt-multi-objective-exploration ~/.claude/skills/cuopt-multi-objective-exploration" installs_to: ~/.claude/skills/cuopt-multi-objective-exploration source_path: skills/cuopt-multi-objective-exploration/SKILL.md collection_size: 25 category_size: 1523 collection_url: "https://dirskills.com/collections/NVIDIA/skills" added: 2026-08-17T07:09:34.468Z last_synced: 2026-08-17T07:09:34.468Z canonical_url: "https://dirskills.com/skills/multi-objective-exploration" --- # Multi-Objective Exploration Multi-Objective Exploration traces and interprets Pareto frontiers for multi-objective optimization problems by orchestrating repeated single-objective cuOpt solves (weighted-sum and ε-constraint). Use it when objectives conflict and the user needs the tradeoff curve, not a single weighted answer. **Install:** ```bash npx degit https://github.com/NVIDIA/skills/tree/main/skills/cuopt-multi-objective-exploration ~/.claude/skills/cuopt-multi-objective-exploration ``` ## README # Multi-Objective Exploration cuOpt optimizes **one** objective per solve. Many real problems have several objectives that pull against each other — cost vs. service level, return vs. risk, makespan vs. overtime, distance vs. vehicle count. A single solve answers "what's optimal *for one particular weighting*," but it hides the tradeoff the user actually needs to see. This skill turns a sequence of single-objective cuOpt solves into a **Pareto frontier** — the set of solutions where you can't improve one objective without giving up another — and gives the discipline to read it. It adds no solver features; it orchestrates the LP / MILP / QP solves already covered by the formulation and API skills. ## When this applies Reach for this workflow when the problem has **two or more objectives with no agreed-upon weighting**, signalled by language like: - "balance X and Y", "trade off", "as cheap as possible *without* hurting service" - "minimize cost *and* maximize coverage", "I want options, not one answer" - any objective the user is willing to relax in exchange for another If there is a single clear objective (everything else is a hard constraint), this skill does not apply — formulate and solve once. ## Core idea — one solve is one point on a curve A single optimum encodes **one implicit weighting** of the objectives. Change the weighting and the optimum moves. The frontier is the curve traced by all the non-dominated optima. A solution **A dominates** B when A is at least as good on every objective and strictly better on one. Dominated solutions are never worth choosing. The **Pareto frontier** is exactly the non-dominated set; the user's job is to pick a point on it, and yours is to show them the whole curve plus where the tradeoff is sharpest. Do not collapse a multi-objective problem to a single weighted number and report its optimum as "the answer" — that silently makes the tradeoff decision *for* the user. Trace the frontier and let them choose. Objectives and constraints are interchangeable. A requirement currently treated as fixed — a coverage floor, a fairness cap, a budget — is often a latent objective: its level was assumed, not given. Promoting such a constraint to a parametric ε-constraint and sweeping it reveals a tradeoff you'd otherwise hide, so read a single-objective model's hard constraints as candidate objectives, not just limits — but only when the level was an assumption. A genuinely fixed, non-negotiable limit (a hard budget cap, a regulatory minimum) stays a constraint; don't manufacture a tradeoff that isn't there. Express any promoted quantity linearly so it can serve as an ε-constraint (see `cuopt-numerical-optimization-formulation`). ## Step 1 — define the objectives An informative frontier needs objectives that genuinely conflict: if they don't pull against each other, it collapses to a single point with nothing to trade off. And each objective has to be formulated correctly, since a wrong form, sense, or scale distorts the tradeoff and shifts where the knee falls. Formulate each one with `cuopt-numerical-optimization-formulation` before sweeping. ## Step 2 — build a payoff table (anchor each objective) Solve each objective **on its own** first. For *k* objectives this is *k* solves. Record, for each, the value of every objective at that optimum: ```text f1 f2 f3 min f1 → f1* f2(at f1*) f3(at f1*) min f2 → ... f2* ... min f3 → ... ... f3* ``` The diagonal (`f1*`, `f2*`, …) is each objective's best achievable value; the off-diagonals give the **range** each objective spans across the others' optima. This table does double duty: - It sets the **sweep bounds** for the ε-constraint method (the feasible range of each constrained objective). - It supplies the **scales** for normalization — objectives in dollars, percent, and hours can't be weighted meaningfully until divided by their ranges. If any single-objective solve is already infeasible, stop and fix the model before sweeping — the frontier doesn't exist yet. ## Step 3 — choose a scalarization ### Weighted sum Combine the objectives into one and sweep the weights: ```text minimize w1·f1(x) + w2·f2(x) + ... , for a grid of weight vectors w ``` Cheap and trivial with any solver. Two limitations to respect: - **It only finds points on the convex hull of the frontier.** Concave (non-convex) regions of the frontier are unreachable no matter how you choose weights, and for MILP the reachable points can be sparse with large gaps. A frontier that looks suspiciously linear or has only a few clustered points is the symptom. - **Weights are not priorities until the objectives are normalized.** Divide each `f_k` by its payoff-table range first; otherwise the largest-magnitude objective dominates regardless of intent. ### ε-constraint (preferred for a complete frontier) Keep one objective; move the rest to constraints and sweep their right-hand sides: ```text minimize f1(x) subject to f2(x) ≤ ε2 f3(x) ≤ ε3 (original constraints) ``` Sweep each `ε_k` across the range from the payoff table. Each `(ε2, ε3, …)` combination is a single standard cuOpt solve. This recovers the **full** frontier, including the concave regions weighted-sum cannot reach, which is why it's the default when completeness matters. The cost is more solves (a grid over the constrained objectives) and bookkeeping of the ε values. ε-constrain *linear* objectives directly. A quadratic objective (e.g. risk `xᵀΣx`) is simplest kept as the objective `f1` while you ε-constrain the linear ones. A **convex** quadratic objective *can* instead be ε-constrained directly: add it as a quadratic constraint `xᵀQx ≤ ε`, which cuOpt supports. Non-convex or equality quadratic constraints are unsupported, and the MILP path stays linear-constraint only. Spot it in existing code: a hand-coded loop over a target or budget value (a return target, a cost cap) is already the ε-constraint method — name it as such, filter dominated points, and read the swept constraint's dual (LP/QP only). **Read that dual as the local exchange rate.** Where the frontier is smooth, the dual on a swept ε-constraint is its slope — how much the kept objective `f1` moves per unit of the bound — at no cost beyond the solve already run; at a kink it gives only a one-sided rate. A **zero** dual usually means the bound is slack — the sweep has run past the frontier's edge (one-way: a slack bound always shows a zero dual, but under degeneracy a binding bound can too). This reading needs LP/QP and a *linear* ε-constraint (MILP optima and problems with quadratic constraints return no duals) — where duals are unavailable, difference adjacent frontier points instead. **Picking a method:** weighted-sum for a quick convex sketch or when you know the frontier is convex (e.g. a pure-LP/QP tradeoff); ε-constraint when the problem is MILP, when the frontier may be non-convex, or when the user needs a faithful and complete curve. ## Step 4 — sweep, collect, and filter ```text frontier = [] for each weight vector (or ε vector) in the grid: set the combined objective (or ε right-hand sides) solve with cuOpt # reuse the prior solution as a warm start if status is Optimal/Feasible: record (objective values, solution) discard dominated and duplicate points sort the survivors to form the frontier ``` Practical notes: - **Warm-start LP sweeps.** For an LP frontier, carry the previous solve's PDLP warmstart data into the next to cut solve time. Per cuOpt this is **LP-only**: a MILP solve doesn't take a PDLP warmstart (you can optionally seed a MIP start instead). See `cuopt-numerical-optimization-api` for the calls. - **Cap each MILP solve.** Set a per-solve time limit on MILP sweeps (see `cuopt-numerical-optimization-api`) — a sweep is many solves, and branch-and-bound can over-spend certifying optimality past a tiny gap, while cuOpt sets no limit by default and won't warn. Report the points as optimal *to the gap you set*, not certified optimal. - **Filter dominated points.** A correct sweep can still emit dominated points (especially weighted-sum near the hull, or MILP). Drop them; they are not part of the frontier. - **Resolution is a budget.** Curve fidelity trades against solve count. Start coarse to see the shape, then refine the grid only where the curve bends. - **Spend the budget where the slope changes (LP/QP).** Because the ε-constraint dual is the frontier's local slope, compare it across solved points: where it barely changes, the curve is nearly straight — interpolate rather than add solves; where it jumps by more than the solve tolerance, the frontier bends between those points — refine there (smaller differences are solver noise, not curvature). This concentrates solves where the curve actually bends instead of spreading them over a uniform grid. On MILP, judge where to refine from the gaps between primal objective values instead. - **Verify, don't assume.** When you claim one method beats another, measure it — e.g. count the efficient points ε-constraint recovered that weighted-sum missed — rather than asserting it; and flag any solve returning feasible-but-not-`Optimal` so a non-certified point is never read as exact. ## Step 5 — complete the frontier: measure and fill what the sweep missed A weighted-sum sweep returns only **supported** points (Step 3's convex-hull limitation); on MILP frontiers, non-supported points — the ones no weighted-sum weighting returns — often make up much of the non-dominated set. A coarse ε-constraint grid leaves gaps the same way: any finite sweep can miss regions. Before presenting a swept frontier, measure the likely miss and decide whether to fill. ### Measure the miss Sort the swept points by one objective. For each adjacent pair, form the rectangle (in general, the box) between them in objective space; flag any box much larger than the median adjacent box (3× is a reasonable bar) or covering a large share of the frontier's spanned area — a sweep that returned only a handful of points is all gaps, so no box stands out from the median. Large boxes have two causes — non-supported regions (weighted sum cannot reach them, common under fixed-charge structure) and weight clustering (a finite grid re-discovering the same corners, even on a nearly convex frontier). The fill step treats both the same. If all boxes are small and even, the sweep is likely adequate — say so and stop. ### Fill the largest gaps first For each flagged box, solve one ε-constraint subproblem targeted inside it: optimize one objective with the other bounded at the box midpoint (bi-objective; with more objectives, sort by each objective in turn and place one target per flagged box instead of recursing). Only certified `Optimal` results settle or steer anything here — a time-limited incumbent is kept as a point (tagged, below) but proves nothing about the gap. A new certified point that survives Step 4's dominance filter means the gap was real (an ε solve can return a weakly optimal point) — bisect: two more targets inside the two sub-boxes it creates. A certified endpoint coming back clears just the probed side of the bound; certifying the whole box as a true discontinuity also needs a known objective step size — all-integer objective coefficients over integer variables give one — to place the bound just inside the far endpoint and match its certified optimum. Without that step size, report the box as a candidate gap, not a proven discontinuity. Stop on a solve budget, or when the remaining boxes fall below the flag bar. ### Warm-start each solve (cheap insurance) Consecutive fill solves differ by one bound, so seed each with its neighbor as a MIP start (Step 4's warm-start note) — one line, and it never changes what is optimal. Expect unchanged solve times; the value is insurance on hard subproblems. ### Degrade gracefully, never silently If a subproblem hits its time limit with a feasible incumbent (`FeasibleFound`), keep the point — it is feasible, and the solve's reported gap bounds its suboptimality — but record it as approximate. The time-capped solve is the primary fallback: it returns both an incumbent and a bound. Heuristics-only mode (`mip_heuristics_only`) drops the proof work and returns feasible points with no gap bound — use it when feasible points are all you need, and tag everything it returns approximate. ### Report with provenance Every presented point carries one of two tags: - **exact** — `Optimal` at your gap setting, i.e. optimal to that gap (Step 4); - **approximate** — time-limited incumbent (quote its reported gap) or heuristics-only result (no bound exists; say so). State the counts with the frontier ("14 points, 11 exact, 3 approximate near the low-cost end, worst gap 2.4%"). Never present a mixed frontier as uniformly optimal. ## Step 6 — interpret the frontier - **Report tradeoffs, not single numbers.** A frontier point means nothing in isolation. Quote the exchange rate — "≈ $4k of extra cost per 1% of added coverage in this region" — so the user can judge whether a move is worth it. On an LP/QP frontier this exchange rate is the swept constraint's dual at that point — the local slope of the frontier, accurate to the solve's optimality tolerance (tighten it before relying on a dual); on MILP, estimate it from the gap to the adjacent frontier point. - **Flag knee points; don't auto-pick them.** The "knee" is where the curve bends most sharply — beyond it you pay a lot for a little. It's often the best-balanced compromise and worth highlighting, but the final choice is the user's preference, not a rule. At the knee the slope is two-sided — the dual just below differs from just above — so quote the exchange rate there as a range, not one number. - **Treat dominated or gappy output as a diagnostic.** If dominated points survive filtering, or the frontier is implausibly sparse or perfectly linear, suspect the sweep or the model — most often weighted-sum hiding a concave region (return to Step 5 and fill the gaps) or a normalization mistake. - **State the weighting/ε you used.** Every reported point is conditional on its scalarization. Make that explicit so a single solve is never mistaken for "the" optimum. On LP/QP, the ε-constraint duals are the *implicit weights* at that point — the effective price the solution puts on each constrained objective, and the weights a weighted-sum solve would need to reproduce that tradeoff. Reporting them makes the accepted tradeoff ratio explicit. ## Interfaces This skill is solver- and interface-agnostic. The per-solve mechanics — building the objective, adding the ε constraints, passing a warm start, reading status — live in the API skills: - `cuopt-numerical-optimization-api` — LP, MILP, QP solves (Python, C, CLI). - `cuopt-routing-api-python` — the same frontier workflow applies to routing tradeoffs (distance vs. vehicles vs. time).