总染色猜想（Δ=6）LP 求解器构建与互补松弛分析
2026年5月27日，路宇轩、英启锐、卢志钧围绕 (\Delta=6) 平面图总染色问题的 LP 求解器构建展开深入讨论，完成了从建模细节确定到代码实现与测试的全过程。
项目回顾与当前进度
项目目标：利用自动放电（Automatic Discharging）框架证明 (\Delta=6) 的平面图总染色猜想——即该情形下存在 ((\Delta+2)=8) 的全染色。
前一阶段已完成构型生成器 gen.py，将全部构型按度分类生成 8 个配置类：
| 配置类 | 数量 | 中心元素 | RHS（初始电荷） |
|---|---|---|---|
| face_3 | 665 | T (3-面) | 3 |
| face_4 | 11,161 | S (4-面) | 4 |
| face_5 | 118,770 | P (5-面) | 5 |
| face_6 | 1,446,776 | H (6-面) | 6 |
| vertex_3 | 24 | 3-顶点 | 3 |
| vertex_4 | 9,825 | 4-顶点 | 4 |
| vertex_5 | 100,466 | 5-顶点 | 5 |
| vertex_6 | 1,446,776 | 6-顶点 | 6 |
总计约 314 万条 canonical 构型。新方案的核心变化之一是将 6-面和 6-顶点完全纳入 LP 处理（旧方案对其仅施加硬编码边界 (|w|\le 1/6)）。
LP 求解器设计
整体框架：迭代 LP + 约束生成
求解器采用双层迭代结构。内层对给定 Red/ 集合在全部 314 万条约束下求最优 (\alpha)；外层从 LP 对偶中识别紧约束（critical constraints），将其对应构型写入 Red/ 后缩小约束池，重新求解。
外循环 (iter = 1, 2, ...):
内循环: 约束生成 → 得到对当前 Red/ 最优的 (α, w)
if α ≥ 4: SUCCESS, 输出放电规则
else:
求解对偶 LP → 识别互补松弛紧约束
将对应构型写入 Red/ 文件
下一轮中这些构型被过滤，约束池缩小
变量系统：三族，约 3,300 个
沿用旧框架的三族变量设计，变量均为无符号浮点数（可正可负），正值表示电荷从首字符对应元素流出：
| 变量族 | 格式 | 含义 | 数量 |
|---|---|---|---|
| VV | 4-char: deg faceL deg faceR | 顶点→顶点跨边传递 | 150 |
| FF | 4-char: face deg face deg | 面→面跨边传递 | 150 |
| FV | 6-char (face-leading): face deg face deg face deg | 面↔顶点传递 | 3,000 |
总计 3,300 个 canonical 变量（含一列 (\alpha) 共 3,301 列）。每个变量经规范化后唯一确定，其符号由首字符与约束中心元素的关系决定：首字符等于中心元素 → (+1)（电荷流出）；否则 (-1)（电荷流入）。
约束形式
对每个构型 (s)（中心元素类型 = (owner)），LP 约束为：
[ \alpha + \sum_{j} \mathrm{coef}j \cdot w{\mathrm{var}(s,j)} \le \mathrm{initial_charge} ]
总约束数约 314 万条，无法直接构建稠密矩阵，必须采用约束生成（Constraint Generation）策略。
关键设计决策
O-面（7⁺-面）的放电边界
本次讨论中的一个重要纠偏在于 O-面的放电上限。O-面没有独立的 face_O 构型类（数量过大且无穷），因此 LP 中不存在代表 O-面电荷平衡的约束。若不加限制，与 O-面相关的变量（FF 和 FV 中首字符为 O 者）可趋于无穷——O-面成为无限电荷源。
推导：最小 O-面为 7-面，初始电荷 7，需保留 (\alpha\ge 4)，最多给出 (7-4=3)。O-面有 (k=7) 条边，每条边上 2 个顶点 + 1 个邻面 = 3 个接收方，但整体来看 7-面共计 (2\times 7 = 14) 个入射元素（7 个顶点 + 7 个邻面）。因此每个入射元素平均获得电荷：
[ U_O = \frac{3}{14} ]
（讨论中最初提议 (3/7)，后经分析修正为 (3/14)，因电荷不仅分配给面，也分配给顶点。）
最终对约 640 个首字符为 O 的 canonical 变量施加对称边界：
[ |w| \le \frac{3}{14} \approx 0.2142857 ]
采用对称边界（而非单向 (0\le w\le 3/14)）是为 LP 保留一定自由度——某些配置中 O-面可能应收而非仅放。
其他决策汇总
| 问题 | 决定 |
|---|---|
| face_6 / vertex_6 的 RHS | 均为 6（面大小/顶点度数） |
| H-面额外 bound | 不需要（face_6 已有完整约束） |
| 6-顶点额外 bound | 不需要（vertex_6 已有完整约束） |
| 变量非负性 | 暂不强制，留 ENFORCE_NONNEGATIVE = False 标记备查 |
| Red/ 初始状态 | 空（已知不可约模式已在 gen.py 阶段过滤） |
| 约束生成提前终止 | 允许——只需 (\alpha\ge 4) 的可行解，不必收敛至最优 |
实现与测试
技术选型
求解器 solve_sys.py（约 1,000 行）基于 Python 3.12 实现，使用 scipy.optimize.linprog（HiGHS 求解器）替代原计划的 cvxopt+GLPK。主要考虑：
- cvxopt+GLPK 在 Windows 上安装复杂，HiGHS 随 scipy 直接可用
- HiGHS 在稀疏 LP 上性能与 GLPK 相当
约束生成算法
1. 初始工作集 W = 全部小类 (face_3/4, vertex_3/4) + 大类随机采样 5,000
2. 求解 LP(W) → (α, w)
3. 扫描全部 3.1M 约束，计算 slack = RHS − α − Σcoef·w
4. 若全部 slack ≥ −ε: 收敛，当前解对完整约束集可行
5. 否则: 将最 violated 约束加入 W，重新求解
每次 LP 求解仅需处理 (~42{,}000 \times 3{,}301) 的稀疏矩阵（HiGHS 数秒完成），扫描全部 3.1M 约束约 30 秒。初始工作集已充分覆盖约束空间，一轮扫描后通常无新增违规约束。
互补松弛分析：对偶 LP
scipy 不直接返回对偶变量，方案求解对偶 LP 来获取影子价格：
[ \begin{aligned} \min\quad & b^T y \ \text{s.t.}\quad & A^T y = [1, 0, \dots, 0]^T \ & y \ge 0 \end{aligned} ]
其中 (y_i) 为约束 (i) 的影子价格。由互补松弛条件，(y_i > 0) 的约束是决定当前最优解的"紧约束"（critical constraints）。它们是 tight 约束（(\mathrm{slack} \approx 0)）的一个子集，真正需要通过写进 Red/ 来移除的约束。
对偶 LP 规模约为 (42{,}000 \times 3{,}301) 等式约束，HiGHS 在 0.7 秒内求解完毕。
测试结果
编写 14 项单元测试覆盖所有核心模块，全部通过：
| 测试项 | 内容 |
|---|---|
| 字母表定义 | T/S/P/H/O 面类型 + 3/4/5/6 顶点度 |
| 变量规范化 | canon_4_with_sign（VV/FF）、canon_6_face_leading（FV） |
| 变量字典 | build_dico_all() 生成 (150+150+3000 = 3300) 变量 |
| O-变量识别 | 首字符=‘O’ 的 canonical 变量过滤 |
| 原始 key 生成 | 从 vertex/face 构型位置推导原始变量 key |
| 系数符号 | 首字符 == owner (\to) (+1)，否则 (-1) |
| 可约模式过滤 | del_dot / replace_dot / filter_red |
| 预计算类 | PrecomputedClass 的 cols/coefs 数组精度 |
| LP 求解 | HiGHS 正确求解最大化 (\alpha) 问题 |
| 构型元数据 | RowMeta 行索引到 (kind, config_string) 映射 |
| O-bound 约束 | (|w|\le 3/14) 正确生成 |
| 约束符号一致性 | 全 8 类构型的 coef 符号验证 |
| 完整 pipeline | 加载→过滤→求解→对偶分析→Red/ 写入 |
端到端运行
对全部 3.1M 构型执行外迭代，初步结果：
- Iteration 1（Red/ 为空）：(\alpha = 3.0)，661 个 tight 约束 → 识别出 355 个可归约构型（344 face_3 + 11 vertex_3），写入 Red/
- Iteration 2（过滤后）：(\alpha) 提升至 3.214，565 个 tight 约束中对偶 LP 仅识别出 4 个 critical，进一步缩紧
- O-面行为：所有非零变量值精确达到 O-bound 上限 3/14，验证了 O-面是系统中主要的电荷来源
- 每次迭代耗时：约 100 秒（主要消耗在预计算 3.1M 构型的约束数据）
后续工作
求解器目前已实现完整的内外层迭代循环。下一步将进行长时间运行（--max-iters 50），观察 (\alpha) 能否收敛至 4.0。若收敛停滞，可能需要：
- 放宽 O-bound (3/14) 或引入按接收方类型区分的 O-bound
- 调整约束生成的容差参数
- 手动构造复杂可约构型模式补充 Red/
运行命令：
$env:PYTHONIOENCODING = "utf-8"; python solve_sys.py --max-iters 50
英启锐
研究生
