链上镖师 / Chain Biaoshi
COR|用 2-index 超模公式逼近 4-index 紧界
一篇关于多分配枢纽选址强公式的论文解读
这篇论文为多分配枢纽选址问题提出新的超模强化公式，在只使用 1-index 和 2-index 变量的前提下，达到已知最紧 4-index 路径公式的线性规划界。
- 01：研究对象是带枢纽启用成本的 MA-HLP，需求可以通过多个枢纽分配和路由。
- 02：核心贡献是从 CF-P 与 CF-S 的弱界问题出发，构造 FZ-P 和 FZ-S 两个强化公式。
- 03：计算实验显示，FZ-S 在 CAB 数据集上的 LP bound 提升约 20%，在 AP 数据集上的提升约 30%。
- 04：论文报告了最多 200 个节点实例在两小时限制内求得最优解的结果。
研究背景
枢纽选址问题把战略设施选址、骨干网络设计和运输路径决策放在同一个优化模型中。航空、通信、货运和末端配送系统都会通过枢纽完成流量汇集、分拣与再分发，借助枢纽间运输的规模经济降低总成本。
论文关注多分配枢纽选址问题 MA-HLP。非枢纽节点可以连接多个枢纽，同一节点发出或接收的不同需求能够经由不同枢纽路径流动。模型目标是最小化枢纽启用成本与所有需求的路由成本之和。
图源：Figure 1，MA-HLP 相关公式与本文贡献关系图。
这类问题的难点在于公式规模与 LP bound 质量之间的取舍。4-index 路径变量公式界很紧，变量规模达到 O(n4)；低维变量公式更省内存，早期超模公式的线性松弛界偏弱。
核心问题
已有 MA-HLP 公式大致分为两条路线。Hamacher 等和 Marín 等的路径公式使用 4-index 变量，能够产生很紧的 LP bound；Contreras 和 Fernández 的超模公式只使用 1-index 与 2-index 变量，变量数量更少。
图源：Table 5，MA-HLP 各类公式的变量类型与数量对照。
论文指出，CF-P 在特定情形下会要求额外启用枢纽边，导致与 MA-HLP 的最优解不一致；在 LP 松弛层面，CF-P 和对应的 CF-S 还可能把同一单枢纽路由价值分摊到多条相邻边上，形成过低的松弛成本。
图源：Figure 2，Remark 1 中用于说明旧公式局限的网络实例。
论文要解决的问题可以概括为：在保持低维变量优势的同时，把超模公式的 LP bound 提升到 4-index 紧路径公式的水平。
方法框架
论文先从路径公式侧构造 FZ-P。它保留 CF-P 中的枢纽启用变量 z、枢纽边启用变量 y 和商品-边路由变量 x，并用新的关联约束强化旧公式：对任一商品 r 和节点 i，所有与 i 相邻边上的路由份额之和不能超过 z_i。
1从 SK、HLPMA、CF-P 梳理 MA-HLP 路径变量公式的界强度。
2用约束 sum_{e in delta(i)} x_re <= z_i 阻止同一商品在同一枢纽周围重复分摊。
3证明 FZ-P 的 LP bound 与 HLPMA 相同。
4把同一强化逻辑迁移到超模不等式，得到只含 z、y、eta 的 FZ-S。
在超模公式侧，论文把每个商品在已启用边集合上的最小路由成本视为非增超模函数。CF-S 的不等式只按枢纽边的路由成本排序，FZ-S 进一步把单枢纽路径的启用状态纳入排序与右端项计算。
图源：Table 4，MA-HLP 公式使用的参数与索引说明。
关键证明分两步完成。第一步证明 FZ-P 和 HLPMA 的 LP bound 相同；第二步给出从 FZ-S 的 z、y 解恢复 FZ-P 路由变量 x 的规则，并证明 FZ-S 与 FZ-P 的 LP bound 一致。
案例或实验设置
模型设定中，网络为完全图，每个节点都可作为潜在枢纽，枢纽启用有成本，枢纽间边无额外启用成本。由于成本满足三角不等式，任一需求的最优路由可写成 origin-i-j-destination，最多包含接入、枢纽间、分发三段。
实验使用两个经典数据集。CAB 数据集来自美国 100 个机场，测试规模为 20 到 100 个节点；AP 数据集包含 200 个澳大利亚邮政点，测试规模为 100、125、150、175 和 200 个节点。
论文设置 interhub discount factor alpha 为 0.2、0.5、0.8，接入和分发权重 gamma、theta 均为 1。公式由 Python 3.11 实现，用 Gurobi 10.0.1 求解，并固定 Threads 为 1、关闭 Presolve。
图源：Figure 3，CAB 数据集上 CF-S 与 FZ-S 的 LP bound 对比。
硬件环境为 Ryzen 7 5700G CPU 和 32GB RAM。节点数不超过 100 的实例时间限制为 3600 秒，超过 100 个节点的大实例时间限制为 7200 秒，超模约束通过类似 Contreras 和 Fernández 的 branch-and-cut 分离过程处理。
结果分析
LP bound 对比显示，FZ-S 明显强于 CF-S。论文报告在 CAB 实例上的提升约为 20%，在 AP 实例上的提升约为 30%。这说明新增的超模强化项有效修复了旧公式在松弛层面的分摊问题。
图源：Table 1，CAB 实例中 HLPMA、CF-S 与 FZ-S 的性能结果。
CAB 结果用于同时比较 HLPMA、CF-S 和 FZ-S 的求解时间、搜索节点与可扩展性。结合 Figure 3，可看到 FZ-S 的界质量接近紧路径公式，同时保留低维变量结构带来的规模优势。
图源：Figure 4，AP 数据集上不同 alpha 条件下的 LP bound 对比。
图源：Table 2，AP 大规模实例中 FZ-S 的求解结果。
管理启示
对航空、通信和物流网络规划而言，公式规模直接影响可求解的网络尺寸。论文给出的 FZ-S 使用 1-index 和 2-index 变量，适合在更大节点规模下保留强线性松弛界，减少内存压力和分支搜索负担。
变量规模
O(n2)
FZ-S 保留低维超模变量结构
实验规模
200 nodes
论文报告 AP 实例可在两小时限制内求得最优解
图源：Table 3，不同 hub setup cost factor 下的 AP 大规模实例结果。
Table 3 展示 hub setup cost factor 变化下的大规模 AP 结果和枢纽选择。它对应一个直接的管理含义：枢纽启用成本参数会改变最优枢纽数量与位置，进而影响网络集中化程度和运输路径结构。
这篇论文的实用价值在于给出一种更适合大规模 MA-HLP 的强公式：它保持超模低维表达，同时把 LP bound 拉到最紧路径公式水平，为大规模枢纽网络设计提供了更稳的建模入口。
论文：A strong formulation for Multiple Allocation Hub Location based on supermodular inequalities
作者：Elena Fernández，Nicolás Zerega
期刊：Computers and Operations Research
链上镖师、先卜交通、先卜运筹通用论文ID
保存此推文 ID，可在粉丝群内获取相关材料，未来更多功能敬请期待
先卜科技团队：常文婕、张巧巧、王一航、夏子帆、张晓乐、祁园园、张仁义
