3. 变量边界冲突导致不可行：从预求解报告反推矛盾约束

预求解不可行性报告能告诉我们什么

当模型被判定为不可行时，现代求解器（如 Gurobi、CPLEX、HiGHS、SCIP）在预求解阶段通常会输出一份不可行性报告。这份报告的核心价值在于：它把"整个模型不可行"这一模糊结论，压缩成一组具体的变量边界与约束行，并给出每条约束在边界传播后的活动范围。我们要做的，就是从这份报告反推出"哪条约束被变量边界卡死"。

典型报告包含三类信息：

  • 变量边界：每个变量的 lb / ub，以及预求解收紧后的边界。
  • 约束活动区间：对约束 a·x ≤ b，报告给出在变量边界下 a·x 的最小可能值 min_activity 与最大可能值 max_activity。
  • 冲突判定：若 min_activity > b（对 ≤ 约束），则该约束在边界下必然被违反，报告会标记为冲突成员。

因此，定位矛盾的核心判据是：约束的可行活动区间与右端项 b 不相交。下面这张图展示了一个具体例子中，三条约束在变量边界下的活动区间与各自右端项的关系——只有 C2 的区间整体落在 b 的右侧，它就是直接矛盾源。

预求解活动区间 vs 右端项：定位直接矛盾约束 变量边界：x1∈[0,4]，x2∈[0,3]，x3∈[0,2]（预求解未再收紧） 0 10 20 30 40 活动值 C1 2x1+3x2≤20 [0, 17] b=20 ✓ 可行 C2 4x1+5x2≤12 [0, 31] b=12 ✗ 冲突 C3 x1+x3≤8 [0, 6] b=8 ✓ 可行 C2 的 min_activity = 0，max_activity = 4·4 + 5·3 = 31 > b = 12，区间与可行域不相交 → 直接矛盾约束 修复方向：放宽 x1 上界至 ≥3（4·3=12），或放宽 x2 上界至 ≥2.4，或增大 C2 右端项至 ≥31

从报告反推矛盾的三步判读法

拿到报告后，不要逐行读，按下面三步快速收敛：

  1. 筛冲突成员：只保留被标记为冲突的约束行。若报告未显式标记，则对每条 ≤ 约束计算 min_activity，若 min_activity > b 即为冲突；对 ≥ 约束则看 max_activity < b。
  2. 找边界贡献者：对冲突约束，看哪些变量的边界把活动值推到了 b 的另一侧。例如 C2 中 4x1 在 x1=4 时贡献 16，已单独超过 b=12，说明 x1 的上界是主因。
  3. 算最小修复量：解一个单变量不等式。对 C2，若只调 x1 上界，需 4·ub1 + 5·0 ≤ 12 不成立时，实际要满足 4·ub1 ≤ 12 即 ub1 ≤ 3；若同时保留 x2 上界 3，则需 4·ub1 + 15 ≤ 12，无解，必须同时调 x2 或改 b。
注意：预求解报告中的活动区间是在当前变量边界下算出的，不是原始模型边界。若预求解已收紧过边界，报告里的 lb/ub 可能已不同于你写的模型。修复时应以报告中的边界为准，否则改完仍不可行。

实操：用 HiGHS 复现并修复

下面给出一个最小可运行示例。模型含三个变量、三条约束，其中 C2 与变量上界直接冲突。代码用 Python 调用 HiGHS，先触发不可行，再读取预求解信息，最后按判读结果修复。

import highspy

def build_model(h):
    # 变量：x1∈[0,4], x2∈[0,3], x3∈[0,2]
    h.addVars(3)
    h.changeColsBounds(3, [0,1,2], [0.0,0.0,0.0], [4.0,3.0,2.0])
    # 目标：最小化 0（仅可行性）
    h.changeColsCost(3, [0,1,2], [0.0,0.0,0.0])
    # 约束 C1: 2x1+3x2 <= 20
    h.addRow(0.0, 20.0, 2, [0,1], [2.0,3.0])
    # 约束 C2: 4x1+5x2 <= 12   ← 冲突源
    h.addRow(-highspy.kHighsInf, 12.0, 2, [0,1], [4.0,5.0])
    # 约束 C3: x1+x3 <= 8
    h.addRow(-highspy.kHighsInf, 8.0, 2, [0,2], [1.0,1.0])

h = highspy.Highs()
h.setOptionValue("presolve", "on")
h.setOptionValue("output_flag", True)
build_model(h)
h.run()

status = h.getModelStatus()
print("status =", status)          # 预期 kInfeasible
if status == highspy.HighsModelStatus.kInfeasible:
    # 读取不可行性报告（HiGHS 通过 IIS 接口给出冲突行/列）
    iis = h.getIis()
    print("conflict rows:", iis.row_index)
    print("conflict cols:", iis.col_index)

运行后预期看到 status = kInfeasible，且 conflict rows 中包含 C2 对应的行索引（本例为 1），conflict cols 中包含 x1（索引 0）。这与前面 SVG 中的判读一致：C2 与 x1 上界共同构成矛盾。

修复与验证

按"最小修复量"结论，把 x1 上界从 4 放宽到 3，或把 C2 右端项从 12 放宽到 31。下面演示放宽 x1 上界到 3 并重新求解：

h2 = highspy.Highs()
h2.setOptionValue("presolve", "on")
build_model(h2)
# 修复：x1 上界 4 → 3
h2.changeColsBounds(1, [0], [0.0], [3.0])
h2.run()
print("status =", h2.getModelStatus())   # 预期 kOptimal
print("x =", h2.getSolution().col_value)

验证通过条件：status = kOptimal，且解满足 4x1+5x2 ≤ 12。若仍不可行，说明还有第二条冲突约束未被报告列出（IIS 可能只给一个最小冲突集），需再次运行 IIS 或手动检查其余约束的活动区间。

当模型规模较大时，IIS 计算可能很慢。可先用 presolve 报告中的活动区间做一次快速筛查，只对 min_activity > b 的约束调用 IIS，能显著缩短排障时间。

常见误判与规避

现象原因规避方法
报告说 C2 冲突，但改 C2 右端项后仍不可行存在多个独立冲突集，IIS 只返回其中一个修复后重跑，循环直到可行；或一次性收集所有 min_activity > b 的约束
活动区间与手算不一致预求解已收紧边界，报告用的是收紧后边界以报告中的 lb/ub 为准，不要用原始模型边界手算
≥ 约束被误判为可行判据用反了：≥ 约束应看 max_activity < b按约束方向分别套用判据，不要统一用 min_activity
等式约束 a·x = b 冲突需同时满足 min_activity ≤ b ≤ max_activity检查 b 是否落在 [min_activity, max_activity] 之外

掌握这套判读法后，变量边界冲突类不可行问题基本可以在几分钟内定位到具体约束与具体变量，而不必靠反复试改模型。下一例将转向目标函数系数尺度差异引发的数值警告，那是另一类与"数值健康度"相关的排障任务。

← 上一章 📖 返回目录 下一章 →