numerical-optimization-formulation

Compare original and translation side by side

🇺🇸

Original

English

🇨🇳

Translation

Chinese

Numerical Optimization Formulation

数值优化建模

Concepts and workflow for going from a problem description to a clear formulation across LP, MILP, and QP. No API code here.

本内容介绍从问题描述到LP、MILP、QP清晰建模的概念与流程。不包含API代码。

What is LP / MILP / QP

LP/MILP/QP是什么

LP: Linear objective, linear constraints, continuous variables.
MILP: Same as LP plus some integer or binary variables (e.g., scheduling, facility location, selection).
QP: Quadratic objective (e.g., x², x·y terms — portfolio variance, least squares), linear constraints. QP support in cuOpt is currently in beta.

LP：线性目标函数、线性约束、连续变量。
MILP：与LP规则相同，额外包含部分整数或二进制变量（例如调度、设施选址、选择类问题）。
QP：二次目标函数（例如x²、x·y项——投资组合方差、最小二乘法）、线性约束。cuOpt中的QP支持目前处于Beta阶段。

Identifying problem type

问题类型识别

Property	LP	MILP	QP
Objective	Linear	Linear	Quadratic (xᵀQx + cᵀx)
Constraints	Linear	Linear	Linear (no quadratic constraints)
Variables	Continuous	Mixed: continuous + integer/binary	Continuous
Sense	min or max	min or max	minimize only (negate to max)

If the objective is purely linear, prefer LP/MILP — do not artificially introduce quadratic terms. If any variable is integer or binary, the problem is MILP regardless of the rest.

属性	LP	MILP	QP
目标函数	线性	线性	二次型（xᵀQx + cᵀx）
约束条件	线性	线性	线性（不支持二次约束）
变量类型	连续型	混合型：连续型 + 整数/二进制	连续型
优化方向	最小化或最大化	最小化或最大化	仅支持最小化（取反后可转为最大化问题）

若目标函数为纯线性，优先选择LP/MILP——不要人为引入二次项。只要存在整数或二进制变量，无论其他条件如何，该问题均为MILP。

Required formulation questions

建模必备问题

Ask these if not already clear:

Decision variables — What are they? Bounds?
Objective — Minimize or maximize? Linear or quadratic? For QP: any squared or cross terms (x², x·y)? If maximize a quadratic, the user must negate and minimize.
Constraints — Linear inequalities/equalities? (Quadratic constraints are not supported.)
Variable types — All continuous (LP / QP) or some integer/binary (MILP)?
Convexity (QP only) — For minimization, the quadratic form (matrix Q) should be positive semi-definite for well-posed problems.

若以下信息不明确，需向用户确认：

决策变量——变量是什么？取值范围？
目标函数——最小化还是最大化？线性还是二次型？对于QP：是否包含平方项或交叉项（x²、x·y）？若为最大化二次型，用户需对目标函数取反后转为最小化问题。
约束条件——是否为线性不等式/等式？（不支持二次约束）
变量类型——全部为连续型（LP/QP）还是包含部分整数/二进制变量（MILP）？
凸性（仅QP适用）——对于最小化问题，二次型矩阵Q需为半正定矩阵，以保证问题有合理解。

Typical modeling elements

典型建模要素

Continuous variables — production amounts, flow, allocations, portfolio weights.
Binary variables — open/close, yes/no (e.g., facility open, item selected).
Linking constraints — e.g., production only if facility open (Big-M or indicator).
Resource constraints — linear cap on usage (materials, time, capacity).
Quadratic objective terms — variance (xᵀQx), squared error (‖Ax − b‖²), interaction terms.

连续变量——产量、流量、分配量、投资组合权重。
二进制变量——开启/关闭、是/否（例如设施是否启用、是否选中某物品）。
关联约束——例如仅当设施启用时才可生产（Big-M法或指示变量法）。
资源约束——对资源使用量的线性上限（物料、时间、产能）。
二次目标项——方差（xᵀQx）、平方误差（‖Ax − b‖²）、交互项。

Typical QP use cases

QP典型应用场景

Portfolio optimization — minimize variance subject to return and budget.
Least squares — minimize ‖Ax − b‖² subject to linear constraints.
Other quadratic objectives with linear constraints.

投资组合优化——在满足收益与预算约束的前提下最小化方差。
最小二乘法——在满足线性约束的前提下最小化‖Ax − b‖²。
其他带有线性约束的二次目标优化问题。

Problem statement parsing

问题陈述解析

When the user gives problem text, classify every sentence and then summarize before formulating. The parsing framework below applies regardless of LP / MILP / QP.

Classify every sentence as parameter/given, constraint, decision, or objective. Watch for implicit constraints (e.g., committed vs optional phrasing) and implicit objectives (e.g., "determine the plan" + costs → minimize total cost).

Ambiguity: If anything is still ambiguous, ask the user or solve all plausible interpretations and report all outcomes; do not assume a single interpretation.

当用户提供问题文本时，需先对每个句子进行分类，再总结后建模。以下解析框架适用于所有LP/MILP/QP问题。

将每个句子分类为参数/已知条件、约束、决策变量或目标函数。注意识别隐含约束（例如确定性表述与可选性表述的差异）和隐含目标（例如“确定方案”+成本信息→最小化总成本）。

歧义处理：若存在任何歧义，需询问用户，或求解所有合理的解读并汇报结果；不要默认单一解读。

🔒 MANDATORY: When in Doubt — Ask

🔒 强制规则：存疑必问

If there is any doubt about whether a constraint or value should be included, ask the user and state the possible interpretations.

若对某约束或数值是否应纳入模型存在任何疑问，需询问用户并说明可能的解读方向。

🔒 MANDATORY: Complete-Path Runs — Try All Variants

🔒 强制规则：全路径验证——尝试所有变体

When the user asks to run the complete path (e.g., end-to-end, full pipeline), run all plausible variants and report all outcomes so the user can choose; do not assume a single interpretation.

当用户要求全路径运行（例如端到端、完整流程）时，需运行所有合理的变体并汇报所有结果，供用户选择；不要默认单一解读。

Three labels

三类标签

Label	Meaning	Examples (sentence type)
Parameter / given	Fixed data, inputs, facts. Not chosen by the model.	"Demand is 100 units." "There are 3 factories." "Costs are $5 per unit."
Constraint	Something that must hold. May be explicit or implicit from phrasing.	"Capacity is 200." "All demand must be met." "At least 2 shifts must be staffed."
Decision	Something we choose or optimize.	"How much to produce." "Which facilities to open." "How many workers to hire."
Objective	What to minimize or maximize. May be explicit ("minimize cost") or implicit ("determine the plan" with costs given).	"Minimize total cost." "Determine the production plan" (with costs) → minimize total cost.

标签	含义	示例（句子类型）
参数/已知条件	固定数据、输入信息、既定事实。不由模型决定。	“需求量为100单位。”“共有3家工厂。”“单位成本为5美元。”
约束	必须满足的条件。可能是显式表述，也可能是隐含于措辞中。	“产能为200。”“必须满足所有需求。”“至少需配备2个班次的员工。”
决策变量	需要我们选择或优化的对象。	“生产多少数量。”“启用哪些设施。”“雇佣多少工人。”
目标函数	需要最小化或最大化的对象。可能是显式表述（“最小化成本”），也可能是隐含于上下文（例如“确定方案”+成本信息→最小化总成本）。	“最小化总成本。”“确定生产方案”（附带成本信息）→最小化总成本。

Implicit constraints: committed vs optional phrasing

隐含约束：确定性表述与可选性表述

Committed/fixed phrasing → treat as parameter or implicit constraint (everything mentioned is given or must happen). Not a decision.

Phrasing	Interpretation	Why
"Plans to produce X products"	Constraint: all X must be produced.	Commitment; production level is fixed.
"Operates 3 factories"	Parameter: all 3 are open. Not a location-selection problem.	Current state is fixed.
"Employs N workers"	Parameter: all N are employed. Not a hiring decision.	Workforce size is given.
"Has a capacity of C"	Parameter (C) + constraint: usage ≤ C.	Capacity is fixed.
"Must meet all demand"	Constraint: demand satisfaction.	Explicit requirement.

Optional/decision phrasing → treat as decision.

Phrasing	Interpretation	Why
"May produce up to …"	Decision: how much to produce.	Optional level.
"Can choose to open" (factories, sites)	Decision: which to open.	Selection is decided.
"Considers hiring"	Decision: how many to hire.	Hiring is under consideration.
"Decides how much to order"	Decision: order quantities.	Explicit decision.
"Wants to minimize/maximize …"	Objective (drives decisions).	Goal; decisions are the levers.

确定性/固定表述→视为参数或隐含约束（提及的内容均为既定事实或必须执行的要求），不属于决策变量。

表述	解读	原因
“计划生产X种产品”	约束：必须生产全部X种产品。	属于承诺；产量固定。
“运营3家工厂”	参数：3家工厂均已启用。不属于选址问题。	当前状态固定。
“雇佣N名工人”	参数：已雇佣全部N名工人。不属于招聘决策问题。	员工规模既定。
“产能为C”	参数（C） + 约束：使用量 ≤ C。	产能固定。
“必须满足所有需求”	约束：需求必须被满足。	明确要求。

可选性/决策表述→视为决策变量。

表述	解读	原因
“最多可生产……”	决策变量：生产数量由我们决定。	产量可选。
“可选择启用”（工厂、站点）	决策变量：决定启用哪些设施。	选择由我们决定。
“考虑招聘”	决策变量：招聘人数由我们决定。	招聘处于考量阶段。
“决定订购数量”	决策变量：订购数量由我们决定。	明确的决策项。
“希望最小化/最大化……”	目标函数（驱动决策）	目标；决策是实现目标的手段。

Implicit objectives — do not miss

隐含目标——不可遗漏

If the problem asks to "determine the plan" (or similar) but does not state "minimize" or "maximize" explicitly, the objective is often implicit. You MUST identify it and state it before formulating; do not build a model with no objective.

Phrasing / context	Likely implicit objective	Why
"Determine the production plan" + costs given (per unit, per hour, etc.)	Minimize total cost (production + inspection/sales + overtime, etc.)	Plan is chosen; costs are specified → natural goal is to minimize total cost.
"Determine the plan" + costs and revenues given	Maximize profit (revenue − cost)	Both sides of the ledger → optimize profit.
"Try to determine the monthly production plan" + workshop hour costs, inspection/sales costs	Minimize total cost	All cost components are given; no revenue to maximize → minimize total cost.

Rule: When the problem gives cost (or cost and revenue) data and asks to "determine", "find", or "establish" the plan, always state the objective explicitly (e.g., "I'm treating the objective as minimize total cost, since only costs are given."). If both cost and revenue are present, state whether you use "minimize cost" or "maximize profit". Ask the user if unclear.

**若问题要求“确定方案”（或类似表述）但未明确说明“最小化”或“最大化”，目标函数通常是隐含的。**你必须先识别并明确目标，再进行建模；不要构建无目标的模型。

表述/上下文	可能的隐含目标	原因
“确定生产方案” + 成本信息（单位成本、小时成本等）	最小化总成本（生产成本+检测/销售成本+加班成本等）	方案需选择，且成本已明确→自然目标是最小化总成本。
“确定方案” + 成本与收入信息	最大化利润（收入−成本）	收支信息均已提供→优化利润。
“尝试确定月度生产方案” + 车间小时成本、检测/销售成本	最小化总成本	仅提供成本构成，无收入信息→最小化总成本。

规则：当问题提供成本（或成本与收入）数据，并要求“确定”“找到”或“制定”方案时，必须明确陈述目标函数（例如“由于仅提供成本信息，我将目标视为最小化总成本”）。若同时提供成本与收入信息，需说明是使用“最小化成本”还是“最大化利润”。若信息不明确，需询问用户。

Parsing workflow

解析流程

Split the problem text into sentences or logical clauses.
Label each: parameter/given | constraint | decision | objective (if stated).
Identify the objective (explicit or implicit): If the problem says "minimize/maximize X", that's the objective. If it only says "determine the plan" (or "find", "establish") but gives costs (and possibly revenues), the objective is implicit — state it (e.g., minimize total cost, or maximize profit) and confirm with the user if ambiguous.
Flag implicit constraints: For each sentence, ask — "Does this state a fixed fact or a requirement (→ parameter/constraint), or something we choose (→ decision)?"
Resolve ambiguity by checking verbs and modals:
- "is", "has", "operates", "employs", "plans to" (fixed/committed) → parameter or implicit constraint.
- "may", "can choose", "considers", "decides", "wants to" (optional) → decision or objective.
🔒 MANDATORY — If anything is still ambiguous (e.g., a value or constraint could be read two ways): ask the user which interpretation is correct, or solve all plausible interpretations and report all outcomes. Do not assume a single interpretation.
Summarize for the user: list parameters, constraints (explicit + flagged implicit), decisions, and objective (explicit or inferred) before writing the math formulation.

拆分：将问题文本拆分为句子或逻辑分句。
标注：为每个分句标注：参数/已知条件 | 约束 | 决策变量 | 目标函数（若已明确）。
识别目标函数（显式或隐含）：若问题明确说明“最小化/最大化X”，则X为目标函数。若仅要求“确定方案”（或“找到”“制定”）但提供了成本（或成本与收入）信息，则目标函数是隐含的——需明确陈述（例如最小化总成本或最大化利润），若存在歧义需与用户确认。
标记隐含约束：对每个句子，需判断——“该句子表述的是固定事实或要求（→参数/约束），还是可选择的内容（→决策变量）？”
通过动词与情态动词解决歧义：
- “是”“拥有”“运营”“雇佣”“计划”（固定/确定性表述）→参数或隐含约束。
- “可以”“可选择”“考虑”“决定”“希望”（可选性表述）→决策变量或目标函数。
🔒 强制规则——若仍存在歧义（例如某数值或约束有两种解读方式）：询问用户哪种解读正确，或求解所有合理解读并汇报结果。不要默认单一解读。
总结：在撰写数学模型前，向用户列出参数、约束（显式+已标记的隐含约束）、决策变量，以及目标函数（显式或推导得出）。

Parsing checklist

解析检查清单

Example

示例

Text: "The company operates 3 factories and plans to produce 500 units. It may use overtime at extra cost. Minimize total cost."

Sentence / phrase	Label	Note
"Operates 3 factories"	Parameter	All 3 open; not facility selection.
"Plans to produce 500 units"	Constraint (implicit)	All 500 must be produced.
"May use overtime at extra cost"	Decision	How much overtime is a decision.
"Minimize total cost"	Objective	Drives decisions.

Result: Parameters = 3 factories, 500 units target. Constraints = produce exactly 500 (implicit from "plans to produce"). Decisions = production allocation across factories, overtime amounts. Objective = minimize cost.

Implicit-objective example: A problem that asks to "determine the production plan" (or similar) and gives cost components (e.g., workshop, inspection, sales) but does not state "minimize" or "maximize" → Objective is implicit: minimize total cost. Always state it explicitly: "The objective is to minimize total cost."

文本：“公司运营3家工厂，计划生产500单位产品。可使用加班模式，但需额外付费。目标为最小化总成本。”

句子/短语	标签	备注
“运营3家工厂”	参数	3家工厂均已启用；不属于设施选址问题。
“计划生产500单位产品”	约束（隐含）	必须生产全部500单位。
“可使用加班模式，但需额外付费”	决策变量	加班时长由我们决定。
“目标为最小化总成本”	目标函数	驱动决策的核心目标。

结果：参数=3家工厂、500单位生产目标；约束=必须生产恰好500单位（来自“计划生产”的隐含要求）；决策变量=各工厂生产分配量、加班时长；目标函数=最小化成本。

隐含目标示例：某问题要求“确定生产方案”（或类似表述），并提供成本构成（例如车间成本、检测成本、销售成本）但未明确说明“最小化”或“最大化”→隐含目标：最小化总成本。必须明确陈述：“目标函数为最小化总成本。”

QP rule: minimize only

QP规则：仅支持最小化

QP objectives must be minimization. To maximize a quadratic expression, negate it and minimize; then negate the optimal value.

For minimization to be well-posed, the quadratic form

should be positive semi-definite. If

is indefinite, the problem is non-convex and may not have a finite optimum.

QP目标函数必须为最小化。若需最大化二次表达式，需对其取反后转为最小化问题；之后再对最优值取反即可得到原问题的最优结果。

为保证最小化问题有合理解，二次型矩阵

需为半正定矩阵。若

为不定矩阵，问题为非凸问题，可能不存在有限最优解。

Common patterns

常见建模模式

The remaining sections cover specific LP/MILP modeling patterns. Each is independent — read the one that matches your problem.

以下章节涵盖特定的LP/MILP建模模式。各章节独立，可阅读与你的问题匹配的部分。

Piecewise-linear objectives with integer production

带整数产量的分段线性目标函数

When modeling concave piecewise-linear profit/cost functions (e.g., decreasing marginal profit for bulk sales), the standard approach uses continuous segment variables with upper bounds equal to each segment's width. For a maximization with concave profit, the solver fills higher-profit segments first naturally.

Gotcha: If the quantity being produced is discrete (pieces, units, items), the total production variable must be INTEGER, even though segment variables can remain CONTINUOUS. Without this, the LP relaxation may yield a fractional total that produces a different (higher or lower) objective than the true integer optimum.

当建模凹分段线性利润/成本函数（例如批量销售的边际利润递减）时，标准方法是使用连续分段变量，其上限等于各分段的宽度。对于凹利润的最大化问题，求解器会自然优先填充高利润分段。

注意事项：若生产数量为离散型（件、单位、物品），总产量变量必须为整数型，即使分段变量可保持连续型。否则，LP松弛解可能得到分数型总产量，导致目标函数值与真实整数最优解不同（偏高或偏低）。

Pattern

模式

x_total  — INTEGER (total production of a product)
s1, s2, … — CONTINUOUS (amount sold in each price segment, bounded by segment width)

Link: x_total = s1 + s2 + …
Resource constraints use x_total.
Objective uses segment variables × segment profit rates.

x_total  — 整数型（某产品的总产量）
s1, s2, … — 连续型（各价格分段的销量，上限为分段宽度）

关联关系: x_total = s1 + s2 + …
资源约束使用x_total。
目标函数使用分段变量 × 分段利润率。

Cutting stock / trim loss problems

下料/切损问题

In cutting stock problems, waste area includes both trim loss (unused width within each cutting pattern) and over-production (excess strips produced beyond demand). Minimizing only trim loss (waste width × length per pattern) ignores over-production and yields an incorrect objective.

在下料问题中，废料面积包括切损（每个下料模式中未使用的宽度）和过量生产（超出需求的条带产量）。仅最小化切损（废料宽度×每个模式的长度）会忽略过量生产，导致目标函数错误。

Correct objective

正确的目标函数

Since the total useful area demanded is a constant, minimizing waste is equivalent to minimizing total material area consumed:

minimize  sum_j (roll_width_j × x_j)

where

x_j

is the length cut using pattern

. The waste area is then:

waste = total_material_area − required_useful_area

where

required_useful_area = sum_i (order_width_i × order_length_i)

由于需求的总有用面积为常数，最小化废料等价于最小化消耗的总物料面积：

minimize  sum_j (roll_width_j × x_j)

其中

x_j

为使用模式

切割的长度。废料面积计算公式为：

waste = total_material_area − required_useful_area

其中

required_useful_area = sum_i (order_width_i × order_length_i)

。

Gotcha

注意事项

Using

sum_j (waste_width_j × x_j)

as the objective only captures trim loss — the unused strip within each pattern. It does not penalize over-production of an order. The solver will over-produce narrow orders to fill patterns efficiently, but that excess material is still waste. Always use total material area as the objective.

将

sum_j (waste_width_j × x_j)

作为目标函数仅能捕捉切损——每个模式中未使用的条带。它不会惩罚订单的过量生产。求解器会过量生产窄幅订单以高效填充模式，但这些多余物料仍属于废料。必须始终使用总物料面积作为目标函数。

Goal programming (preemptive / lexicographic)

目标规划（优先/字典序）

Goal programming optimizes multiple objectives in priority order. Implement it as sequential solves — one per priority level.

目标规划按优先级顺序优化多个目标。需实现为序贯求解——每个优先级对应一次求解。

Formulation pattern

建模模式

Hard constraints — capacity limits, non-negativity, etc. These hold in every phase.
Goal constraints — for each goal, introduce deviation variables (d⁻ for underachievement, d⁺ for overachievement) and write an equality:
```
expression + d⁻ − d⁺ = target
```
.
Solve sequentially by priority:
- Phase 1: minimize (or maximize) the relevant deviation for the highest-priority goal.
- Phase k: fix all higher-priority deviations at their optimal values, then optimize priority k's deviation.

硬约束——产能限制、非负性等。这些约束在每个阶段均需满足。
目标约束——为每个目标引入偏差变量（d⁻表示未达标量，d⁺表示超额量），并写出等式：
```
表达式 + d⁻ − d⁺ = 目标值
```
。
按优先级序贯求解：
- 阶段1：最小化（或最大化）最高优先级目标的相关偏差变量。
- 阶段k：将所有更高优先级的偏差变量固定在其最优值，再优化第k优先级目标的偏差变量。

Variable types in goal programming

目标规划中的变量类型

Deviation variables (d⁻, d⁺) and slack/idle-time variables are always continuous. However, decision variables must still be INTEGER when they represent discrete/countable quantities (units produced, vehicles, workers, etc.). Do not let the presence of continuous deviation variables cause you to make all variables continuous — the integrality of decision variables directly affects feasibility and objective values.

偏差变量（d⁻、d⁺）和松弛/闲置时间变量始终为连续型。但决策变量在代表离散/可数数量时仍需为整数型（产量、车辆、工人等）。不要因存在连续偏差变量而将所有变量设为连续型——决策变量的整数性直接影响可行性与目标函数值。

Multi-period inventory / purchasing models

多周期库存/采购模型

In problems with buying, selling, and warehouse capacity over multiple periods, decide which capacity constraints to include based on the problem's timing assumptions.

在涉及多周期采购、销售与仓库容量的问题中，需根据问题的时间假设确定应纳入哪些容量约束。

Pattern

模式

For each period t with inventory balance

stock[t] = stock[t-1] + buy[t] - sell[t]

End-of-period capacity (variable bound):
```
stock[t] <= capacity
```
— always needed.
After-purchase capacity (explicit constraint):
```
stock[t-1] + buy[t] <= capacity
```
— prevents buying more than the warehouse can hold before any sales occur within the period.

对于每个周期t，库存余额为

stock[t] = stock[t-1] + buy[t] - sell[t]

：

期末容量（变量边界）：
```
stock[t] <= capacity
```
——始终需要。
采购后容量（显式约束）：
```
stock[t-1] + buy[t] <= capacity
```
——防止在周期内销售发生前，采购量超出仓库容量。

When to include the after-purchase constraint

何时纳入采购后约束

Include it when the problem states or implies that purchases are received before sales happen within a period (sequential operations), or when the warehouse physically cannot exceed capacity at any instant.
Omit it when buying and selling are concurrent within a period (common in textbook trading/inventory problems) and the capacity applies only to end-of-period stock. Many classic problems only constrain end-of-period inventory.

Key interaction with the sell constraint: If the model already has

sell[t] <= stock[t-1]

(grain bought this period cannot be sold this period), the model is bounded even without the after-purchase constraint. The sell constraint prevents unbounded buy-sell cycling. The after-purchase constraint is then an additional physical restriction, not a mathematical necessity.

Default: If the problem does not specify timing within a period, use only end-of-period capacity (

stock[t] <= capacity

). Add the after-purchase constraint only if the problem explicitly requires it.

需纳入：当问题明确或隐含表示采购在周期内销售前完成（顺序操作），或仓库在任何时刻都不能超出容量。
可省略：当采购与销售在周期内同时进行（常见于教材中的交易/库存问题），且容量仅针对期末库存时。许多经典问题仅约束期末库存。

与销售约束的关键交互：若模型已包含

sell[t] <= stock[t-1]

（本期采购的货物无法在本期销售），即使没有采购后约束，模型也有界。销售约束可防止无限制的采购-销售循环。采购后约束是额外的物理限制，而非数学必需条件。

默认规则：若问题未指定周期内的时间顺序，仅使用期末容量约束（

stock[t] <= capacity

）。仅当问题明确要求时，才添加采购后约束。

Blending with shared mixing / intermediate processing

带共享混合/中间加工的配料问题

In some blending problems, a subset of raw materials must be mixed together first (e.g., in a mixing tank) before being allocated to different products. The resulting intermediate has a uniform composition — you cannot independently assign different raw materials to different products.

在某些配料问题中，部分原材料需先混合（例如在混合罐中），再分配给不同产品。所得中间产物的成分均匀——无法独立将不同原材料分配给不同产品。

Why the standard blending LP is wrong here

标准LP配料模型为何在此场景下失效

The standard blending LP uses variables

x[i][j]

(amount of raw material

in product

) and freely allocates each raw material to each product. When raw materials share a mixing step, the proportions of those raw materials must be identical in every product that receives the intermediate. This proportionality constraint is bilinear (

x[A,1]*x[B,2] = x[B,1]*x[A,2]

) and cannot be directly expressed in an LP.

标准LP配料模型使用变量

x[i][j]

（原材料

在产品

中的用量），并可自由将每种原材料分配给每种产品。当原材料共享混合步骤时，这些原材料的比例在所有使用中间产物的产品中必须完全相同。该比例约束为双线性（

x[A,1]*x[B,2] = x[B,1]*x[A,2]

），无法直接在LP中表达。

Linearization strategies

线性化策略

Single-product allocation: If analysis shows the intermediate is profitable in only one product, allocate all intermediate to that product (set intermediate allocation to other products to zero). The proportionality constraint becomes trivially satisfied. This is the most common case — check profitability of intermediate in each product before attempting a general split.
Parametric over intermediate concentration: Fix the sulfur/quality concentration of the intermediate as a parameter
```
σ
```
. For each fixed
```
σ
```
, the problem is a standard LP (intermediate becomes a virtual raw material with known properties). Solve for a grid of
```
σ
```
values or use the structure to find the optimum analytically.
Scenario enumeration: When only 2–3 products exist, enumerate which products receive the intermediate (all-to-A, all-to-B, split). For each scenario with a single recipient, the LP is standard. For split scenarios, use strategy 2.

单一产品分配：若分析表明中间产物仅在一种产品中盈利，可将所有中间产物分配给该产品（设置中间产物向其他产品的分配量为0）。此时比例约束自动满足。这是最常见的情况——在尝试通用拆分前，先检查中间产物在各产品中的盈利性。
基于中间产物浓度的参数化：将中间产物的硫含量/质量浓度固定为参数
```
σ
```
。对于每个固定的
```
σ
```
，问题变为标准LP（中间产物成为具有已知属性的虚拟原材料）。可针对一系列
```
σ
```
值求解，或利用结构解析找到最优解。
场景枚举：当仅存在2-3种产品时，枚举哪些产品使用中间产物（全部分配给A、全部分配给B、拆分分配）。对于单一接收方的场景，LP模型为标准型。对于拆分场景，使用策略2。

Profitability check

盈利性检查

Before formulating, check whether using the intermediate in each product is profitable:

Compare the minimum cost per ton of the intermediate (using cheapest feasible raw material mix) against each product's selling price.
If
```
cost_intermediate > sell_price[j]
```
for some product
```
j
```
, the intermediate should not be allocated to product
```
j
```
. Raw material C (or other direct inputs) alone may also be unprofitable if
```
cost_C > sell_price[j]
```
.
This analysis often eliminates the need for a bilinear split entirely.

建模前，需检查中间产物在各产品中的盈利性：

比较中间产物的最低单位成本（使用最便宜的可行原材料组合）与各产品的售价。
若
```
cost_intermediate > sell_price[j]
```
对于某产品
```
j
```
成立，则中间产物不应分配给该产品。单独使用原材料C（或其他直接输入）若
```
cost_C > sell_price[j]
```
，同样不盈利。
该分析通常可完全消除双线性拆分的需求。