3. 约束求解概述：CSP 定义、约束类型与求解器角色
在智能寻源算法中，约束求解是连接业务规则与数学优化的核心环节。它将“在满足所有限制条件的前提下，找到最优供应商组合”这一业务问题，形式化为计算机可处理的数学模型。本节从约束满足问题（CSP）的定义出发，梳理智能寻源中的约束分类，并明确求解器在其中的关键作用。
3.1 约束满足问题（CSP）定义
约束满足问题（Constraint Satisfaction Problem, CSP）由三个基本要素构成：
- 变量（Variables）：需要决策的对象，例如“中标供应商ID”、“分配份额”、“单价”等。
- 值域（Domains）：每个变量允许取值的集合，例如供应商ID的取值范围为{供应商A, 供应商B, 供应商C}，份额的取值范围为[0, 100]。
- 约束（Constraints）：规定变量之间必须满足的关系，例如“总份额之和 = 100%”、“单价不得超过预算上限”。
一个CSP的解，就是为每个变量在其值域内赋予一个值，使得所有约束同时成立。在智能寻源场景中，我们通常寻找的是最优解——在满足所有硬约束的前提下，使目标函数（如总成本最低、交付准时率最高）达到最优。
形式化定义： 一个CSP可表示为三元组 (X, D, C)，其中 X = {x₁, x₂, ..., xₙ} 为变量集，D = {D₁, D₂, ..., Dₙ} 为对应值域集，C = {c₁, c₂, ..., cₘ} 为约束集。解是映射 σ: X → ∪Dᵢ，满足 σ(xᵢ) ∈ Dᵢ 且对所有 cⱼ 成立。
3.2 智能寻源中的约束类型
根据约束在求解过程中的强制程度，智能寻源中的约束分为硬约束和软约束两大类。理解两者的区别，是调试求解参数的前提。
| 约束类型 | 定义 | 违反后果 | 典型示例 |
|---|---|---|---|
| 硬约束 | 必须严格满足的约束，不可违反 | 解直接无效，被求解器丢弃 | “总份额=100%”、“供应商必须通过资质审核” |
| 软约束 | 希望尽量满足，但允许一定程度的违反 | 违反时产生惩罚成本，降低解的评分 | “尽量选择历史合作供应商”、“单价尽量低于市场均价” |
实战提示： 在参数调试阶段，常见的错误是将本应设为硬约束的条件误设为软约束（导致解不合法），或将软约束误设为硬约束（导致无解）。建议在建模初期，将所有业务规则先标记为硬约束，再根据求解结果逐步放宽。
3.2.1 硬约束详解
硬约束是寻源问题的底线规则，通常来源于法律法规、合同条款或不可妥协的业务要求。常见的硬约束包括：
- 数量/份额约束：所有中标供应商的分配份额之和必须等于100%。
- 资质约束：供应商必须具备特定行业资质（如ISO认证、安全生产许可证）。
- 唯一性约束：同一物料只能由一家供应商中标（单源采购场景）。
- 预算约束：总采购金额不得超过预算上限。
- 交付约束：供应商的交付能力必须满足最低需求量。
3.2.2 软约束详解
软约束用于表达偏好或优化方向，不强制满足，但违反时会降低解的“质量”。求解器通过引入惩罚项或权重来平衡软约束的满足程度。常见软约束包括：
- 成本偏好：尽量选择单价更低的供应商（可量化为与最低价的偏差惩罚）。
- 合作历史偏好：优先选择历史合作评分高的供应商。
- 区域平衡偏好：尽量使中标供应商分布在多个区域，降低供应链风险。
- 绿色采购偏好：优先选择环保评级高的供应商。
参数调试注意： 软约束的权重设置直接影响求解结果。权重过高可能导致求解器过度追求软约束而牺牲成本最优性；权重过低则软约束形同虚设。建议通过敏感性分析，观察不同权重下目标函数的变化曲线，找到平衡点。
3.3 求解器角色
在智能寻源算法中，求解器（Solver） 是执行约束求解的引擎。它接收CSP模型（变量、值域、约束、目标函数）作为输入，通过搜索、推理、优化等算法，输出满足约束的最优或近似最优解。
求解器在寻源流程中扮演以下核心角色：
- 模型解析器：将业务人员定义的约束规则（如“份额和=100%”）转化为求解器内部的数据结构（如约束图、约束矩阵）。
- 搜索执行器：采用回溯搜索、分支定界、局部搜索等算法，在庞大的解空间中寻找可行解。
- 约束传播器：通过弧一致性、前向检查等技术，提前剪除不可能满足约束的变量赋值，缩小搜索空间。
- 优化引擎：在可行解的基础上，根据目标函数（如总成本最小化）进行迭代优化，输出最优解。
- 冲突分析器：当无解时，分析导致冲突的约束组合，辅助业务人员调整模型或放宽约束。
关键认知： 求解器不是“黑盒”。它的行为受大量参数控制，包括搜索策略（深度优先 vs. 广度优先）、变量选择启发式（最小剩余值 vs. 最大度）、约束传播强度、软约束权重等。这些参数正是本课程后续章节调试的核心对象。
下表总结了常见求解器类型及其在寻源场景中的适用性：
| 求解器类型 | 典型算法 | 适用场景 | 优势 | 局限 |
|---|---|---|---|---|
| 精确求解器 | 分支定界、整数规划 | 中小规模、硬约束严格、需要最优解 | 保证全局最优 | 大规模问题求解时间指数增长 |
| 启发式求解器 | 遗传算法、模拟退火 | 大规模、软约束多、允许近似最优 | 求解速度快，可处理复杂约束 | 不保证最优，结果不稳定 |
| 约束传播求解器 | 弧一致性、前向检查 | 约束密集、变量值域小的场景 | 剪枝效率高，快速排除无效解 | 对数值约束处理能力弱 |
选型建议： 对于中标场景，建议采用混合求解策略：先用约束传播快速剪枝，再用启发式搜索寻找候选解，最后用精确求解对Top-N候选进行局部优化。这种分层策略在工业级寻源系统中被广泛验证。