
名称	cuopt-multi-objective-exploration
版本	“26.10.00”
描述	使用重复的单目标 cuOpt 求解（加权和与 ε-约束）来追踪、完善并解释竞争目标之间的帕累托前沿。
开源协议	Apache-2.0 origin: cuopt-skill-evolution metadata:
作者	NVIDIA cuOpt Team tags: - 多目标 - 帕累托 - ε约束 - 权衡 - 工作流

多目标探索

cuOpt 每次求解优化一个目标。许多实际问题包含多个相互制约的目标——成本与服务水平，回报与风险，制造周期与加班时间，行驶距离与车辆数量。单次求解回答的是“对于某个特定权重，什么最优”，却隐藏了用户真正需要看到的权衡。

本技能将一系列单目标 cuOpt 求解转化为帕累托前沿——即在不牺牲其他目标的情况下无法改进任一目标的解集——并提供了正确解读它的方法。它不增加求解器功能；而是编排已由公式与 API 技能所涵盖的 LP/MILP/QP 求解。

适用场景

当问题具有两个或更多目标且没有商定权重时，可以采用此工作流，典型语言包括：

“平衡 X 与 Y”、“权衡”、“尽可能便宜又不损害服务”
“最小化成本并且最大化覆盖”、“我想要选项，而不是一个答案”
任何用户愿意为了另一个目标而放松的目标

如果只有一个明确目标（其他一切都是硬约束），本技能不适用——直接建立并求解一次。

核心思想——一次求解只是曲线上的一个点

单个最优解编码了一种隐含的加权。改变权重，最优解就会移动。前沿就是由所有非支配最优点追踪出的曲线。

当解 A 支配 B 时，A 在每个目标上至少与 B 一样好，并且至少在一个目标上严格更好。被支配的解永远不值得选择。帕累托前沿正是非支配集合；用户的工作是在其上选择一个点，而你的工作是向他们展示整条曲线以及权衡最尖锐的位置。

不要把多目标问题压缩成一个加权数并将其最优解作为“答案”报告——那会静默地替用户做出权衡决定。要追踪前沿并让他们选择。

目标与约束是可以互换的。当前被视为固定的约束——覆盖下限、公平上限、预算——通常是潜在的目标：其水平是假设的，而非给定的。将这样的约束提升为参数化 ε-约束并进行扫描，会揭示原本隐藏的权衡，因此请将单目标模型中的硬约束视为候选目标，而不仅仅是限制——但仅当其水平是假设时。真正固定、不可协商的限制（硬性预算上限、监管最低要求）仍是约束；不要制造实际上不存在的权衡。将任何提升的变量以线性形式表达，以便其能作为 ε-约束（参见 cuopt-numerical-optimization-formulation）。

步骤 1 —— 定义目标

有意义的前沿需要真正冲突的目标：如果它们不相互对抗，就会坍缩成单个点，没有什么可权衡。而且每个目标必须正确建立，因为错误的形式、方向或比例会扭曲权衡并改变拐点位置。在扫描之前，使用 cuopt-numerical-optimization-formulation 来建立每个目标。

步骤 2 —— 构建支付表（锚定每个目标）

先单独求解每个目标。对于 k 个目标，需要 k 次求解。记录每个目标在其最优解处的所有目标值：

              f1        f2        f3
min f1   →   f1*       f2(at f1*) f3(at f1*)
min f2   →   ...       f2*        ...
min f3   →   ...       ...        f3*

对角线（f1*, f2*, …）是每个目标可实现的最佳值；非对角线给出每个目标在其他目标最优解上跨越的范围。此表有双重作用：

为 ε-约束方法设定扫描边界（每个被约束目标的可行范围）。
提供归一化所需的尺度——以美元、百分比和小时计量的目标在除以各自范围之前无法有意义的加权。

如果任何单目标求解已不可行，请在扫描前停止并修复模型——此时前沿还不存在。

步骤 3 —— 选择标量化方法

加权和

将多个目标合并为一个，并扫描权重：

minimize  w1·f1(x) + w2·f2(x) + ... ,   for a grid of weight vectors w

使用任何求解器都很廉价且简单。有两个必须尊重的局限：

它只能找到前沿凸包上的点。 无论你如何选择权重，前沿的凹（非凸）区域都无法到达；对于 MILP，可到达的点可能稀疏且有较大间隙。如果前沿看起来可疑地线性或只有少数聚集点，那就是这个症状。
在目标归一化之前，权重不是优先级。 先除以支付表中的范围；否则，量级最大的目标不论意图如何都会占主导。

ε-约束（更适用于完整前沿）

保留一个目标；将其余目标移到约束中并扫描它们的右边项：

minimize  f1(x)
subject to  f2(x) ≤ ε2
            f3(x) ≤ ε3
            (original constraints)

扫描每个 ε_k 跨过支付表中的范围。每个 (ε2, ε3, …) 组合就是一次标准的 cuOpt 求解。这将恢复完整前沿，包括加权和无法到达的凹区域，这就是在完整性重要时优先使用它的原因。代价是更多次求解（对约束目标做网格）以及对 ε 值的记录。

直接对线性目标施加 ε-约束。二次目标（例如风险 xᵀΣx）最简单的是保留为目标 f1，同时你对线性目标做 ε-约束。一个凸二次目标可以被直接 ε-约束：将其作为二次约束 xᵀQx ≤ ε 添加，cuOpt 支持。非凸或等式二次约束不支持，MILP 路径仅保持线性约束。

在现有代码中识别：手写的对目标或预算值（回报目标、成本上限）的循环已经是 ε-约束方法——将其命名为这样，滤除支配点，并读取所扫描约束的对偶（仅 LP/QP）。

将对偶视为局部汇率。 在前沿平滑的地方，对扫描 ε-约束的对偶是它的斜率——保持的目标 f1 每单位边界变化的量——除了已运行的求解外没有额外成本；在折点处仅给出单侧速率。零对偶通常意味着边界松弛——扫描已经超过了前沿边缘（单方向的：松弛的边界总是显示零对偶，但在退化情况下，起作用的边界也可能显示零）。这种解读需要 LP/QP 和线性 ε-约束（MILP 优化和具有二次约束的问题不返回对偶）——在不能获得对偶的地方，改为求相邻前沿点之差。

选择方法： 当需要快速凸草图或已知前沿是凸的（例如纯 LP/QP 权衡）时，用加权和；当问题是 MILP、前沿可能非凸、或者用户需要忠实且完整的曲线时，用 ε-约束。

步骤 4 —— 扫描、收集、滤除

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

实用说明：

为 LP 扫描提供热启动。 对于 LP 前沿，将上一次求解的 PDLP warmstart 数据带入下一次，以减少求解时间。根据 cuOpt，这仅限 LP：MILP 求解不接受 PDLP warmstart（可选地，你可以植入 MIP 启动）。参见 cuopt-numerical-optimization-api。
为每次 MILP 求解设定上限。 在 MILP 扫描时设置每次求解的时间限制（参见 cuopt-numerical-optimization-api）——扫描是多次求解，分支定界可能会花费过多时间在小间隙上证明最优性，而 cuOpt 默认不设置限制且不会警告。将点报告为在对你所设的间隙内的最优，而不是被证明的最优。
滤除支配点。 即使正确的扫描也可能发出支配点（尤其接近凸包的加权和，或 MILP）。丢弃它们；它们不是前沿的一部分。
分辨率是一项预算。 曲线保真度与求解次数相互制约。先进行粗略扫描以了解形状，然后仅在曲线弯曲处以更细网格细化。
把预算花在斜率变化的地方（LP/QP）。 因为 ε-约束对偶是前沿的局部斜率，因此对比已求解点间的对偶：如果变化很小，曲线近直线——可插值而不是增加求解；如果变化超过求解容差，则前沿在这些点之间弯曲——在那里细分（更小的差异是求解器噪声，不是曲率）。对 MILP，则根据原始目标值之间的间隙来判断在何处细化。
验证，而不是假设。 当声称一种方法优于另一种时，要量化它——例如，统计 ε-约束恢复而加权和遗漏的有效点数量——而不是断言；并标记任何返回 Feasible 而非 Optimal 的求解，使未被认证的点永远不会被当作精确值。

步骤 5 —— 完善前沿：测量并填补扫描遗漏的部分

加权和扫描只返回受支持的点（步骤 3 的凸包限制）；在 MILP 前沿上，非受支持点——任何加权和权重都无法返回的点——常常构成非支配集合的大部分。粗 ε-约束网格同样会留下缺口：任何有限扫描都可能错过区域。在呈现扫描前沿之前，先测量可能的遗漏并决定是否填补。

测量遗漏

按一个目标对扫描到的点进行排序。对每个相邻对，在目标空间中形成它们之间的矩形（一般情况是盒子）；标记任何比中位相邻盒子大得多（3× 是合理标准）或覆盖前沿跨度区域很大份额的盒子——一次只返回少量点的扫描全是缺口，所以没有盒子能突出于中位。大盒子有两个原因——非受支持区域（加权和无法到达，常见于固定费用结构）和权重聚集（有限网格在近乎凸的前沿上重复发现相同的角）。填补步骤对两者同样处理。

如果所有盒子都小而均匀，扫描很可能足够——说明该情况并停止。

先填补最大的缺口

对每个标记的盒子，在目标内部求解一个 ε-约束子问题：优化一个目标，并在盒子中点（双目标）约束另一个目标；目标更多时，按每个目标依次排序，并为每个标记的盒子放置一个目标，而不是递归。只有被认证的 Optimal 结果才能在此确定或调整任何结论——时间限制的当前解保留为一个点（下面带标记），但不能证明缺口。新认证的点在步骤 4 的支配过滤中存活的意味着缺口是真实的（ε 求解可能返回弱最优的点）——二分：在新点创建的两个子盒子内部再加两个目标。认证的端点返回时仅清除边界被探测的一侧；将整个盒子认证为真正不连续还需要已知目标步长——整数变量上的全整数目标系数提供一个——从而在远端内放置边界并与其被认证的最优值匹配。如果没有步长，则将盒子报告为候选缺口，而非已证实的不连续。无论何时达到求解预算或剩余盒子低于标记标准，就停止。

每次求解均热启动（廉价保险）

连续填补求解只相差一个边界，因此用其邻居作为 MIP 启动来植入每个求解（步骤 4 的热启动说明）——只需一行，并不改变最优解。期望求解时间不变；其价值是解决困难子问题时的保险。

优雅降级，绝不静默

如果子问题在时间限制内找到可行当前解（FeasibleFound），保留该点——它是可行的，并且求解报告的间隙约束了其次优性——但将其记录为近似值。时间封顶的求解是主要的回退：它同时返回当前解和界限。仅启发式模式（mip_heuristics_only）放弃证明工作并返回可行点且没有间隙界限——当你只需要可行点时使用它，并将所有返回的点标记为近似。

报告来源

每个呈现的点都带有两个标签之一：

exact（精确） — 在您设定的间隙下的 Optimal，即优化达到了该间隙（步骤 4）；
approximate（近似） — 时间限制的当前解（引用其报告的间隙）或仅启发式结果（无界限存在；要说明）。

用计数说明前沿（“14 个点，11 个精确，3 个近似位于低成本端附近，最差间隙 2.4%”）。切勿将混合前沿呈现为统一最优。

步骤 6 —— 解读前沿

报告权衡，而不是单一数字。 孤立的点毫无意义。引用汇率—“此区域每增加 1% 覆盖约需 $4k 额外成本”——以便用户判断移动是否值得。在 LP/QP 前沿上，此汇率是扫描约束在该点的对偶——前沿的局部斜率，精确到求解的最优容差（在依赖它之前收紧容差）；在 MILP 上，则根据到相邻前沿点的间隙估计。
标出拐点；不要自动选择。 “拐点”是曲线弯曲最剧烈的点——超过它，你付出很多却只能得到很少。它通常是最均衡的折中方案，值得高亮，但最终选择是用户的偏好，不是规则。在拐点处，斜率是双侧的——下方略低、上方略高的对偶不同——因此将汇率作为一个区间而非一个数字引用。
把支配点或有间隙的输出视为诊断。 如果滤波后仍有支配点，或者前沿异常稀疏或完全线性，则怀疑扫描或模型——最常见的是加权和隐藏了凹区域（回到步骤 5 填补缺口）或归一化错误。
说明所用的权重/ε。 每个报告的点都以其标量化为条件。要明确说明，以便单次求解不会被误认为是“那个”最优解。在 LP/QP 上，ε-约束对偶是该点的隐式权重——解赋予每个被约束目标的有效价格，以及加权和求解重现该权衡所需的权重。报告它们使所接受的权衡比率明确。

接口

本技能与求解器和接口无关。每个求解的机制——构建目标、增加 ε 约束、传递热启动、读取状态——都在 API 技能中：

cuopt-numerical-optimization-api — LP、MILP、QP 求解（Python、C、CLI）。
cuopt-routing-api-python — 同样的前沿工作流适用于路由权衡（距离 vs. 车辆 vs. 时间）。