基于精确(Exact)与启发式(Heuristic)方法求解最大范数(L∞-norm)下二维带宽问题(Two-dimensional Bandwidth Minimization Problem, 2D-BMP)
《European Journal of Operational Research》：Optimizing the two-dimensional bandwidth problem under the maximum norm using exact and heuristic approaches
编辑推荐：
研究人员提出了三种约束满足问题(Constraint Satisfaction Problem, CSP)模型（算术模型、有限域扩展约束可满足模型及二分优化模型）以精确求解小规模图实例下的二维带宽最小化问题(Two-dimensional Bandwidth
研究人员提出了三种约束满足问题(Constraint Satisfaction Problem, CSP)模型（算术模型、有限域扩展约束可满足模型及二分优化模型）以精确求解小规模图实例下的二维带宽最小化问题(Two-dimensional Bandwidth Minimization Problem under L∞-norm, 2D-BMP)；同时提出一种基于收敛判定的多重启动算法(Convergence-Based Multi-start Algorithm, CBMA)，该算法结合贪心构造启发式(Greedy Construction Heuristic)与局部搜索(Local Search)以高效优化大规模复杂图的二维带宽上界。研究结果表明：CSP模型可为70个标准图基准实例求得最优解，其中包含21个此前未知的理论下界；CBMA算法在取自Harwell-Boeing稀疏矩阵集的113个大尺度复杂图上刷新了现有上界记录，且计算时间更短。该项工作通过精确与启发式方法的双重贡献，推进了L∞度量下二维图嵌入问题在VLSI设计、网络仿真及调度问题等领域的研究现状。
论文解读：基于CSP与启发式方法求解L∞范数下的二维带宽最小化问题(2D-BMP)
一、研究背景与开展的研究
图嵌入问题(Graph Embedding Problem)，又称标号问题(Labeling Problem)，在VLSI设计、并行计算机网络拓扑模拟、广播网络调度及传感器网络中有重要应用价值。二维带宽最小化问题(Two-dimensional Bandwidth Minimization Problem, 2D-BMP)要求将含n个顶点的Guest Graph G=(V,E)单射(Injection)嵌入至?√n?×?√n?的Host Grid（网格图）中，以边两端点在网格上的切比雪夫距离(L∞-norm / Chebyshev Distance，dL∞(u,v)=max{|f(u)1-f(v)1|,|f(u)2-f(v)2|}的最大值——即二维带宽β2D(G,f)——为最小目标。既往文献仅给出路径、圈、星型、轮型等正则图的理论下界，缺乏针对复杂或不规则拓扑图的有效精确或近似算法。鉴于2D-BMP属NP-hard问题，研究人员分别构建了基于约束满足问题(Constraint Satisfaction Problem, CSP)的精确模型，以及融合贪心构造与局部搜索的启发式多重启动算法，并通过与Memetic Algorithm(MA)及改进的对偶表示模拟退火(Dual Representation Simulated Annealing, DRSA)基线算法对比，验证所提方法之有效性。本文发表于《European Journal of Operational Research》。
二、主要关键技术方法
研究人员采用两类技术路线：(1) 精确法——建立三种CSP模型并用Python+PyCSP3库实现，调CHOCO求解器进行二分判定式优化(Dichotomic Optimization)，以AllDifferent约束保证网格点互异，对称破缺(Symmetry Breaking)约束限定最高度顶点位于左下四分对角区；(2) 启发式法——设计Convergence-Based Multi-start Algorithm(CBMA)，构造阶段用带权重(w1=2/3,w2=1/3)的McAllister准则结合广度优先搜索(Breadth-First Search, BFS)逐层选点，宿主网格点选取使已嵌入邻接点的L∞距最大值最小；局部搜索采用交换算子(Swap Operator)及Promising Set of Vertices(PSV)邻域约简策略，辅以替代目标函数(考虑各距离层级边数分布)克服平坦搜索地形，终止条件综合最大迭代次数、最小样本量下方差阈值及相对改善率判定。实验基准含70个标准拓扑图(路径、圈、笛卡尔积、完全图、双星图等)及113个Harwell-Boeing稀疏矩阵图(小/大两组)，对照基线为定制Memetic Algorithm(MA, PMX交叉+交换变异+首改进局部搜索)与适配L∞距的DRSA。参数(w1,w2,终止阈值M=250,N=90,v=1×10-5,r=0.01)经irace自动调参确定。
三、研究结果
2. Constraint satisfaction problem models（约束满足问题模型）
研究人员构建了算术模型MA（直接以最大化边距≤k为优化目标）、有限域扩展约束可满足模型MFDE（将边两端点标号对限制于预计算允许元组表le中，且可将二维表拆分为两个一维Table约束以降低内存）及基于MFDE的二分优化模型MDO（利用带宽单调性在[lb,ub]区间二分调用SAT型CSP判定是否存在β2D≤k的嵌入）。对比实验显示MA仅能求解n≤13的微小实例（>13节点超时），而MDO借助早期剪枝与分步判定显著提速，故被选作最终精确求解器。理论下界由最高度顶点邻域几何增长(8k个L∞距为k的点)推得。
3. Multi-start algorithm（多重启动算法——CBMA）
3.1 General procedure：CBMA循环执行"构造→局部搜索→更新最优"，收集历次目标值，当达最小迭代N=90后若方差<10-5或最佳解与均值相对改善<1%或达最大M=250次则终止。
3.2 Constructive procedure：以随机根做BFS分层，每步按gi(u,f)=w1·|A(u)|-w2·|R(u)|（A(u)已分配邻接点集，R(u)未分配邻接点集）选Guest顶点，宿主顶点从已占用格点的L∞距=1的邻接候选集CH(f)中取使maxv∈A(u)dL∞((i,j),f(v))最小的格点，初始宿主点取网格角点。
3.3 Local search procedure：采用Swap算子（含与空格点交换等效为插入Insert），定义Promising Set of Vertices PSV(u,f)=∩v∈A(u)Svf，其中Svf={(i,j)∈VH: d(f(v),(i,j))≤β2D(G,f)}，仅当两顶点互换后对方进入自身PSV才纳入Reduced Neighborhood NR(f)；目标函数增量仅重算受影响边；引入替代评价函数t(G,f)=Σl=1lmaxnl·fl（fl为距恰等于l的边数）在同带宽解间做平局打破(Tiebreaking)。First Improvement策略优于Best Improvement且耗时更低(0.25s vs 3.67s)。
4. Computational experiments（计算实验）
4.1 CSP experiments：MDO在30分钟限制内求解n≤117的部分Harwell-Boeing实例，对70个标准图均求最优解（平均1.17s），MA仅n≤13可解，确认MDO优越性。
4.2 Heuristic algorithm experiments：加权BFS构造(WeightedBFS, w1=2/3,w2=1/3)较BasicMcA与WeightedMcA在1000次迭代取得最低偏差(0.00%)与最短用时(0.398s)；局部搜索中Alt.O.F.+高效增量计算+PSV邻域约简(FI策略)在质量接近全枚举前提下大幅降时(0.25s)；FI较BI获更多最优解(12/13 vs 11/13)且快一个数量级；irace调参得M=250,N=90,v=1e-5,r=0.01。
4.3 Competitive experiments：在标准70图，MDO全优(Best O.F.=1.64, Dev=0%)，CBMA近优(Best O.F.=1.69, Dev=4.29%, #Best=67, T=0.24s)，MA与DRSA偏差>27%；在52个可解Harwell-Boeing图，CBMA最优(Best O.F.=3.37, Dev=0.96%, #Best=51)显著快于MDO(22516s)及MA/DRSA(Dev>280%)；在剩余61个大Harwell-Boeing图(未解 by MDO)，CBMA给出新上界(Best O.F.=7.03, #Best=61)，MA与DRSA严重退化(Dev>300%)。
四、讨论与结论翻译
研究表明：所提CSP二分模型可有效求小规模及中等规模2D-BMP最优解，并为21个先前无界实例提供下界；CBMA启发式算法在大尺度Harwell-Boeing稀疏矩阵图上系统性突破已有上界且具良好扩展性。该双重贡献推进了L∞度量下二维图嵌入问题在变尺度与变拓扑图族上的求解水平，对VLSI布局、网络模拟及调度等应用领域具实用参考价值。未来可进一步优化算法效率、探索其他启发式框架或拓展至其余图嵌入度量问题。
结论(Conclusion)原文意译：
本文研究了使用L∞-norm距离的二维带宽最小化问题(2D-BMP)，即将Guest Graph嵌入Grid Host Graph使最大边Chebyshev距最小。研究人员提出了三种精确约束满足问题(CSP)模型——算术模型、有限域扩展模型及二分优化模型——并设计了结合贪心构造与局部搜索的收敛判定多重启动算法(Convergence-Based Multi-start Algorithm, CBMA)。CSP方法求出70个小基准图的最优解并更新数例未知下界；CBMA在113个Harwell-Boeing大复杂图上刷新上界且耗时更少。本工作通过精确与启发式途径共同推进了不同规模与拓扑下2D-BMP的求解现状，对VLSI设计、网络仿真及调度有重要意义。后续可优化算法性能、尝试替代启发式或推广至其他图嵌入问题。
