名称: cuopt-数值优化公式化 版本: “26.10.00” 描述: LP、MILP、QP——概念、问题文本解析和公式化模式（参数、约束、决策、目标）。仅概念；无API。 许可证: Apache-2.0 元数据: 作者: NVIDIA cuOpt团队 标签: - 线性规划 - 混合整数规划 - 二次规划 - 公式化 - 概念
数值优化公式化
概念和工作流程：从问题描述到清晰的LP、MILP和QP公式化。这里不涉及API代码。
什么是LP / MILP / QP
- LP：线性目标、线性约束、连续变量。
- MILP：与LP相同，加上一些整数或二进制变量（例如调度、选址、选择）。
- QP：二次目标（例如x²、x·y项——组合方差、最小二乘），线性约束。cuOpt中的QP支持目前处于beta阶段。
识别问题类型
| 属性 | LP | MILP | QP |
|---|---|---|---|
| 目标 | 线性 | 线性 | 二次（xᵀQx + cᵀx） |
| 约束 | 线性 | 线性 | 线性 + 凸二次（仅不等式），通过二阶锥 |
| 变量 | 连续 | 混合：连续 + 整数/二进制 | 连续 |
| 目标方向 | 最小化或最大化 | 最小化或最大化 | 仅最小化（最大化需取反） |
| 对偶/敏感性 | 对偶值 + 检验数 | 无（整数最优解） | 对偶值 + 检验数 |
如果目标纯线性，优先选择LP/MILP——不要人为引入二次项。如果任一变量是整数或二进制，则该问题属于MILP，无论其他部分如何。
求解后敏感性（仅LP/QP）。 连续LP和QP解会暴露对偶值（在约束被松绑时目标边际变化：在何处投入以改善结果）和检验数（对于优化器将变量保持在零的情况，该变量需要改进多少才能进入解：一种"接近命中"）。MILP解没有对偶——整数最优不是连续的，因此没有可返回的对偶。当模型包含二次约束时，对偶也不可用——二阶锥路径仅返回原始值。有关如何在求解后检索它们，请参见特定语言的API技能。
必备的公式化问题
如果尚未明确，请询问以下问题：
- 决策变量——它们是什么？有无边界？
- 目标——最小化还是最大化？线性还是二次？对于QP：有无平方项或交叉项（x²，x·y）？若最大化二次目标，用户必须取反并最小化。
- 约束——线性不等式/等式？也支持凸二次约束（仅不等式），按二阶锥处理；非凸或等式二次约束不支持。
- 变量类型——全部连续（LP / QP）还是部分整数/二进制（MILP）？
- 凸性（仅QP）——对于最小化，二次形式（矩阵Q）应为半正定，以保证问题适定。
典型建模元素
- 连续变量——产量、流量、分配、组合权重。
- 二进制变量——开/关、是/否（例如设施是否开放，是否选择项目）。
- 关联约束——例如只有在设施开放时才能生产（Big-M或指示变量）。
- 资源约束——对使用量（物料、时间、容量）的线性上限。
- 二次目标项——方差（xᵀQx）、平方误差（‖Ax − b‖²）、交互项。
典型QP用例
- 组合优化——在收益率和预算约束下最小化方差。
- 最小二乘——在线性约束下最小化‖Ax − b‖²。
- 其他带线性约束的二次目标。
问题陈述解析
当用户给出问题文本时，先对每个句子进行分类，再总结然后公式化。下面的解析框架适用于LP / MILP / QP，无论哪种类型。
将每个句子分类为参数/给定、约束、决策或目标。注意隐含约束（例如，承诺式与可选式表达）和隐含目标（例如，“确定计划”+成本→最小化总成本）。
**歧义性：**如果仍有歧义，请询问用户，或求解所有合理的解释并报告所有结果；不要假设单一解释。
🔒 强制规则：有疑问时——询问
- 如果对某个约束或值是否应包含有任何疑问，请询问用户并说明可能的解释。
🔒 强制规则：完整路径运行——尝试所有变体
- 当用户要求运行完整路径（例如端到端、全流程），运行所有合理变体并报告所有结果，以便用户选择；不要假设单一解释。
三类标签
| 标签 | 含义 | 示例（句子类型） |
|---|---|---|
| 参数 / 给定 | 固定数据、输入、事实。不由模型选择。 | “需求为100件。” “有3家工厂。” “成本为每单位5美元。” |
| 约束 | 必须满足的条件。可以是显式的，也可以从措辞中隐含。 | “产能是200。” “必须满足所有需求。” “至少需要配置2个班次。” |
| 决策 | 我们选择或优化的内容。 | “生产多少。” “开放哪些设施。” “雇佣多少工人。” |
| 目标 | 要最小化或最大化的内容。可以是显式的（“最小化成本”）或隐含的（"确定生产计划"并给出成本→最小化总成本）。 |
隐含约束：承诺式与可选式表达
承诺式/固定式表达 → 视为参数或隐含约束（提到的一切都是给定的或必须发生的）。不是决策。
| 表达方式 | 解释 | 原因 |
|---|---|---|
| “计划生产X种产品” | 约束：必须生产全部X种。 | 承诺；生产水平固定。 |
| “运营3家工厂” | 参数：3家工厂都处于开工状态。不是选址问题。 | 当前状态固定。 |
| “雇佣了N名工人” | 参数：N名工人全部受雇。不是招聘决策。 | 劳动力规模已给定。 |
| “产能为C” | 参数（C）+ 约束：使用量 ≤ C。 | 产能固定。 |
| “必须满足所有需求” | 约束：满足需求。 | 明确要求。 |
可选/决策式表达 → 视为决策。
| 表达方式 | 解释 | 原因 |
|---|---|---|
| “最多可生产……” | 决策：生产多少。 | 可选的量。 |
| “可以选择开放”（工厂、场所） | 决策：开放哪些。 | 选择由模型决定。 |
| “考虑雇佣……” | 决策：雇佣多少。 | 雇佣在考虑中。 |
| “决定订购多少……” | 决策：订购量。 | 明确决策。 |
| “希望最小化/最大化……” | 目标（驱动决策）。 | 目标；决策是手段。 |
隐含目标——不要遗漏
如果问题要求"确定计划"（或类似），但没有明确说"最小化"或"最大化"，目标往往是隐含的。 你必须在公式化前识别并说明；不要构建没有目标的模型。
| 表达方式 / 上下文 | 可能的隐含目标 | 原因 |
|---|---|---|
| “确定生产计划”+给出成本（每小时、每件等） | 最小化总成本（生产+检验/销售+加班等） | 计划需要选择；给出了成本→自然目标是总成本最小化。 |
| “确定计划”+给出成本和收入 | 最大化利润（收入−成本） | 同时出现收入和成本→优化利润。 |
| “尽量确定月度生产计划”+给出车间工时成本、检验/销售成本 | 最小化总成本 | 给出了所有成本组成；没有收入可最大化→最小化总成本。 |
**规则：**当问题给出成本（或成本与收入）数据并要"确定"、“找出"或"制定"计划时，始终明确说明目标（例如，“我视目标为最小化总成本，因为只给出了成本。”）。如果成本和收入都出现，说明你使用的是"最小化成本"还是"最大化利润”。不清楚就问用户。
解析工作流
- 拆分问题文本为句子或逻辑子句。
- 标注每一部分：参数/给定 | 约束 | 决策 | 目标（如果有）。
- 识别目标（显式或隐含）： 如果问题说"最小化/最大化X"，那就是目标。如果只说"确定计划"（或"找出"、“制定”）但给出了成本（以及可能收入），目标是隐含的——说明它（例如，最小化总成本，或最大化利润），如果模棱两可则向用户确认。
- 标记隐含约束： 对每个句子问——“这是固定事实或要求（→参数/约束），还是我们要选择的内容（→决策）？”
- 通过动词和情态消除歧义：
- “是”、“有”、“运营”、“雇佣”、“计划要”（固定/承诺）→ 参数或隐含约束。
- “可以”、“可以选择”、“考虑”、“决定”、“想要”（可选）→ 决策或目标。
- 🔒 强制规则——如果仍有歧义（例如某个值或约束有两种理解方式）：询问用户哪种解释正确，或求解所有合理解释并报告所有结果。不要默默选择单一解释。
- 为用户总结： 在写数学公式之前列出参数、约束（显式+标记的隐含）、决策和目标（显式或推断）。
解析检查清单
- [ ] 每个句子都有标签（参数 | 约束 | 决策 | 目标（如果有））。
- [ ] 目标已识别： 显式（“最小化/最大化X”）或隐含（“确定计划”+成本→最小化总成本；+收入→最大化利润）。没有说明目标就不要写出公式。
- [ ] 承诺式表达（“计划要”、“运营”、“雇佣”）→ 不是决策。
- [ ] 可选式表达（“可以”、“可以选择”、“考虑”）→ 决策。
- [ ] 承诺式表达产生的隐含约束被写出来（例如，“必须生产所有X种”）。
- [ ] 🔒 强制规则——歧义： 任何可以有两种理解方式的短语 → 我询问了用户，或我将求解所有解释并报告所有结果（不可静默采用单一解释）。
- [ ] 在公式化前给出了总结（参数、约束、决策、目标）。
示例
文本：“公司运营3家工厂，并计划生产500件产品。可以使用加班，但成本更高。最小化总成本。”
| 句子/短语 | 标签 | 备注 |
|---|---|---|
| “运营3家工厂” | 参数 | 3家都开工；不是选址问题。 |
| “计划生产500件” | 约束（隐含） | 必须生产全部500件。 |
| “可以使用加班，但有额外成本” | 决策 | 加班多少是决策。 |
| “最小化总成本” | 目标 | 驱动决策。 |
结果：参数 = 3家工厂，500件目标。约束 = 恰好生产500件（从"计划生产"隐含）。决策 = 各工厂生产分配、加班量。目标 = 最小化成本。
隐含目标示例： 一个问题要求"确定生产计划"（或类似）并给出成本构成（如车间、检验、销售）但未说明"最小化"或"最大化" → 目标是隐含的：最小化总成本。始终明确说明：“目标是最小化总成本。”
QP规则：仅最小化
QP目标必须是最小化。要最大化二次表达式，请对其取反并最小化；然后对最优值取反。
对于最小化问题是适定的，二次形式Q应为半正定。如果Q是不定矩阵，问题为非凸，可能没有有限最优解。
常见模式
以下各节涵盖特定的LP/MILP建模模式。每节独立——阅读匹配你问题的部分即可。
具有整数产量的分段线性目标
当建模凹分段线性利润/成本函数时（例如，大批量销售的边际利润递减），标准方法使用连续分段变量，其上限等于每个分段的宽度。对于最大化凹利润，求解器自然首先填充高利润段。
陷阱： 如果被生产的数量是离散的（件、单位、项目），则总产量变量必须是整数，即使分段变量可以保持连续。否则，LP松弛可能产生一个分数总产量，导致与真实整数最优不同的（更高或更低）目标值。
模式
x_total — 整数（产品的总产量）
s1, s2, … — 连续（每个价格段中的销售量，受分段宽度限制）
关联：x_total = s1 + s2 + …
资源约束使用x_total。
目标使用分段变量 × 分段利润费率。
下料 / 修边损失问题
在下料问题中，浪费面积包括修边损失（每个切割模式中未使用的宽度）和过度生产（超出需求的过剩条带）。仅最小化修边损失（每个模式的浪费宽度 × 长度）会忽略过度生产，导致错误的目标。
正确目标
由于所需有用面积是常数，最小化浪费等价于最小化总材料面积消耗：
最小化 sum_j (卷宽_j × x_j)
其中x_j为按模式j切割的长度。浪费面积则为：
浪费 = 总材料面积 − 所需有用面积
其中所需有用面积 = sum_i (订单宽_i × 订单长_i)。
陷阱
使用sum_j (浪费宽度_j × x_j)作为目标只捕获修边损失——即每个模式中未使用的条带。它不惩罚某个订单的过度生产。求解器会过度生产窄订单以高效填充模式，但那些多余材料仍然是浪费。始终使用总材料面积作为目标。
目标规划（优先 / 字典序）
目标规划按优先级顺序优化多个目标。实现为顺序求解——每个优先级一次。
公式化模式
- 硬约束——产能限制、非负性等。这些在每个阶段都成立。
- 目标约束——对每个目标引入偏差变量（d⁻ 表示未达到，d⁺ 表示超出），并写等式：
表达式 + d⁻ − d⁺ = 目标值。 - 按优先级顺序求解：
- 阶段1：最小化（或最大化）最高优先级目标的相关偏差。
- 阶段k：将所有更高优先级的偏差固定在各自最优值，然后优化优先级k的偏差。
目标规划中的变量类型
偏差变量（d⁻、d⁺）和松弛/空闲时间变量始终为连续。但是，当决策变量表示离散/可数数量（生产件数、车辆、工人等）时，它们仍必须是整数。不要因为存在连续偏差变量而将所有变量变成连续——决策变量的整数性直接影响可行性和目标值。
多周期库存 / 采购模型
在跨周期买、卖以及仓库容量约束的问题中，根据问题的时序假设决定包含哪些容量约束。
模式
对每个期间t，库存平衡为stock[t] = stock[t-1] + buy[t] - sell[t]：
- 期末容量（变量上限）：
stock[t] <= capacity——始终需要。 - 采购后容量（显式约束）：
stock[t-1] + buy[t] <= capacity——防止在期间内发生任何销售之前买入超过仓库可容纳的库存。
何时包含采购后约束
- 包含它当问题说明或暗示期间内采购先于销售发生（顺序操作），或仓库在任何时刻都不能物理超容量时。
- 省略它当采购和销售在一个期间内同时发生（常见于教科书式交易/库存问题）并且容量仅适用于期末库存时。许多经典问题只约束期末库存。
与卖出约束的关键相互作用： 如果模型已有sell[t] <= stock[t-1]（本期买入的粮食不能本期卖出），即使没有采购后约束，模型也是有界的。卖出约束防止无界的买卖循环。采购后约束是额外的物理限制，而非数学必要性。
默认： 如果问题没有指定期间内的时序，仅使用期末容量（stock[t] <= capacity）。仅当问题明确要求时，才加入采购后约束。
带共用混合/中间处理的混合问题
在一些混合问题中，一部分原料必须先混合在一起（例如在混合罐中），然后分配到不同产品。产生的中间体具有均匀组成——不能独立地将不同原料分配给不同产品。
为什么标准混合LP在这里是错误的
标准混合LP使用变量x[i][j]（原料i在产品j中的量）并自由地将每种原料分配给每个产品。当原料共用混合步骤时，这些原料的比例必须在每个接收中间体的产品中相同。这一比例约束是双线性的（x[A,1]*x[B,2] = x[B,1]*x[A,2]），无法直接在LP中表达。
线性化策略
-
单一产品分配： 如果分析表明中间体仅在一个产品中盈利，则将所有中间体分配给该产品（将其他产品的中间体分配设为零）。比例约束自然满足。这是最常见的情况——在进行一般拆分前先检查中间体在每个产品中的盈利性。
-
对中间体浓度参数化： 将中间体的硫含量/质量浓度固定为参数
σ。对每个固定σ，问题变为标准LP（中间体变为具有已知属性的虚拟原料）。在σ值的网格上求解，或利用结构解析求解最优值。 -
情景枚举： 当只有2–3个产品时，枚举哪些产品接收中间体（全部给A、全部给B、拆分）。对每个单一接收者情景，LP是标准的。对于拆分情景，使用策略2。
盈利性检查
在规划之前，检查每个产品中使用中间体是否盈利：
- 将中间体的每吨最低成本（使用最便宜的可行原料混合）与每个产品的销售价格进行比较。
- 如果
cost_intermediate > sell_price[j]对于某些产品j，则不应将中间体分配给该产品j。原料C（或其他直接输入）如果cost_C > sell_price[j]也可能无利可图。 - 此分析通常完全消除双线性拆分。