cuopt-multi-objective-exploration

多目标探索

cuOpt 每次求解只优化一个目标。许多实际问题包含多个相互牵制的目标——成本与服务水平、收益与风险、完工时间与加班时长、距离与车辆数量。单次求解只能回答“在某种特定权重下什么是最优的”，却掩盖了用户真正需要了解的权衡关系。

这项技能将一系列单目标 cuOpt 求解转化为帕累托前沿——其中的解无法在不牺牲另一项目标的情况下改善某一目标——并提供解读前沿的方法。它不增加求解器功能，只负责协调公式和 API 技能中介绍的 LP / MILP / QP 求解。

适用场景

当问题包含两个或更多尚未商定权重的目标时，使用此工作流。相关表述包括：

• “兼顾 X 和 Y”“权衡”“在不影响服务水平的前提下尽可能降低成本”
• “既要最小化成本，又要最大化覆盖率”“我想要多个选项，而不是一个答案”
• 用户愿意为另一目标而放宽的任何目标

如果只有一个明确目标（其他所有事项都是硬约束），则不适用此技能——只需建模并求解一次。

核心理念——一次求解就是曲线上的一个点

单个最优解隐含了对各目标的一种权重设定。改变权重，最优解也会随之变化。由所有非支配最优解描绘出的曲线就是前沿。

如果解 A 在每个目标上都至少和 B 一样好，并且在某个目标上严格优于 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，可到达的点还可能很稀疏，间隔很大。前沿看起来异常线性，或只有少数几个聚集点，就是这种情况的表现。
• 目标归一化之前，权重并不代表优先级。 先将每个 f_k 除以其收益表中的取值范围；否则，无论意图如何，幅值最大的目标都会占据主导地位。

ε-约束（首选，用于求完整前沿）

保留一个目标；将其余目标改为约束，并遍历约束右端项：

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 热启动数据传递给下一次求解，以缩短求解时间。根据 cuOpt，此功能仅适用于 LP：MILP 求解不接受 PDLP 热启动（你也可以选择提供 MIP 初始解）。有关调用方式，请参阅 cuopt-numerical-optimization-api。
• 限制每次 MILP 求解的时间。 为 MILP 扫描设置每次求解的时间限制（参见 cuopt-numerical-optimization-api）——一次扫描包含许多次求解，而分支定界可能会为了证明最优性而耗费过多时间，即使最优性间隙已经很小。cuOpt 默认不设限制，也不会发出警告。应报告这些点在你设定的间隙下为最优，而不是报告为已证明最优。
• 筛除被支配的点。 正确的扫描仍可能生成被支配的点（尤其是凸包附近的加权和扫描，或 MILP）。请将其删除；它们不属于前沿。
• 分辨率就是预算。 曲线保真度需要权衡求解次数。先用较粗的网格了解整体形状，然后仅在曲线弯曲处细化网格。
• 将预算花在斜率变化处（LP/QP）。 ε-约束的对偶值就是前沿的局部斜率，因此要比较各个已求解点的对偶值：如果变化很小，曲线就接近直线——插值即可，不必增加求解次数；如果变化超过求解容差，说明前沿在这些点之间弯曲——应在此处细化（较小的差异是求解器噪声，不是曲率）。这样可以将求解次数集中在曲线实际弯曲处，而不是均匀分布在整个网格上。对于 MILP，应根据原始目标值之间的间隙来判断在哪里细化。
• 验证，不要想当然。 当你声称一种方法优于另一种方法时，应进行测量——例如，统计 ε-约束法找回而加权和法漏掉的有效点数量——而不是直接断言；并标记任何返回可行但非 Optimal 的求解结果，避免将未经认证的点视为精确结果。

第 5 步——补全前沿：衡量并填补扫描遗漏

加权和扫描只会返回受支持的点（受第 3 步中凸包限制）；在 MILP 前沿中，非受支持点——也就是加权和法无论如何加权都无法返回的点——往往占非支配点集合的很大一部分。较粗的 ε-约束网格也会留下间隙：任何有限次扫描都可能遗漏某些区域。在展示扫描得到的前沿之前，应衡量可能的遗漏，并决定是否填补。

衡量遗漏

按某个目标对扫描得到的点排序。对于每对相邻点，在目标空间中构造它们之间的矩形（一般情况下为长方体）；标记任何远大于相邻区域中位数的区域（3 倍是合理的阈值），或覆盖前沿所跨区域较大部分的区域——如果扫描只返回少数几个点，那么到处都是间隙，因此没有哪个区域会显著大于中位数。大区域有两种成因——非受支持区域（加权和法无法到达这些区域，在固定成本结构中很常见）和权重聚集（有限网格反复找回相同的拐角，即使前沿几乎是凸的也会如此）。填补步骤对这两种情况采用相同的处理方式。

如果所有区域都很小且大小均匀，那么扫描很可能已经足够——说明这一点，然后停止。

优先填补最大的空白

对于每个标记的区间，在其中针对一个 ε-约束子问题求解：优化一个目标，同时将另一个目标限制在区间中点（双目标情形；若目标更多，则依次按各目标排序，并为每个标记区间设定一个目标，而不是递归细分）。只有经认证的 Optimal 结果才能在这里确定或引导任何判断——受时间限制的当前解会作为一个点保留（见下文的标记），但不能证明区间存在空白。经认证的新点若通过 Step 4 的支配性筛选，就说明该空白确实存在（ε 求解可能返回弱最优点）——将区间二分：在新形成的两个子区间内各设一个目标，再求解两次。若返回的是经认证的端点结果，则只能清除探测到的那一侧边界；要将整个区间认证为真正的不连续，还需要已知目标的步长——例如，整数变量上的目标系数全为整数时就能得到该步长——以便将边界放在远端点内侧，并与其经认证的最优值相匹配。若不知道该步长，应将该区间报告为候选空白，而非已证实的不连续。达到求解预算，或剩余区间低于标记阈值时，停止。

为每次求解提供热启动（低成本保障）

连续的填补求解只相差一个边界，因此使用相邻求解的结果作为 MIP 初始解（见 Step 4 的热启动说明）——只需一行，而且不会改变最优解。求解时间通常不会变化；其价值在于为困难子问题提供保障。

逐步降级处理，绝不隐瞒

如果子问题达到时间限制时有可行当前解（FeasibleFound），就保留该点——它是可行的，且求解报告的间隙限定了其次优程度——但要标记为近似解。达到时间限制的求解是首选回退方案：它会同时返回当前解和界。

报告时注明来源

每个展示的点都要带有以下两种标记之一：

• 精确 — 在你的间隙设置下达到 Optimal，即在该间隙内最优（Step 4）；
• 近似 — 受时间限制的当前解（注明其报告的间隙）。

在前沿结果旁注明数量（“14 个点，其中 11 个精确，3 个近似且靠近低成本端，最差间隙为 2.4%”）。绝不要把混合前沿说成全部都是最优解。

Step 6 — 解读前沿

• 报告权衡，而非单一数字。 前沿上的一个点单独来看毫无意义。应给出交换率——“在此区域，覆盖率每增加 1%，成本约增加 4,000 美元”——让用户判断这种变化是否值得。在 LP/QP 前沿上，该交换率就是该点处被扫描约束的对偶值——前沿的局部斜率，其精度受求解最优性容差影响（依赖对偶值前应收紧容差）；在 MILP 上，则根据相邻前沿点之间的间距估算。
• 标出拐点；不要自动选定。 “拐点”是曲线弯折最明显之处——越过它之后，代价很高，收益却很小。它往往是平衡性最佳的折中点，值得重点说明，但最终选择应取决于用户的偏好，而非一条规则。在拐点处，斜率有两侧之分——其正下方的对偶值与正上方的不同——因此应将该处的交换率报告为一个范围，而非单一数字。
• 将受支配或有空白的输出视为诊断信号。 如果筛选后仍有受支配点，或者前沿稀疏得不合常理或完全呈线性，就应怀疑扫描过程或模型；最常见的原因是加权和法隐藏了凹形区域（返回 Step 5 填补空白），或归一化有误。
• 说明使用的权重/ε。 每个报告的点都取决于其标量化方式。应明确说明这一点，以免把单次求解误认为“唯一”最优解。在 LP/QP 上，ε-约束的对偶值就是该点的隐式权重——解为每个受约束目标赋予的有效价格，也是加权和求解要复现该权衡时所需的权重。报告这些对偶值，就能明确说明所接受的权衡比率。

接口

此技能不依赖特定求解器或接口。每次求解的具体操作——构建目标函数、添加 ε 约束、传入热启动、读取状态——请参阅 API 技能：

• cuopt-numerical-optimization-api — LP、MILP、QP 求解（Python、C、CLI）。
• cuopt-routing-api-python — 同样的前沿工作流也适用于路径规划权衡（距离与车辆数量、时间之间的权衡）。