可并行化整数线性规划的多米诺骨牌覆盖通用着色法及其在NP完全问题中的加速应用

《Journal of Computational Science》：A generalized colouring method for a parallelizable integer linear programming approach to polyomino tiling

本文提出了一种通用的棋盘着色法，用于解决大规模多米诺骨牌覆盖问题。该方法将传统的双色着色扩展至三色或更多色，通过整数线性规划（ILP）显著降低问题规模与计算时间。研究通过MATLAB、CPLEX和Gurobi进行数值实验，证明该方法可提升NP完全问题的求解效率，并为并行计算实现提供理论基础。

　　

背景与相关工作

提升NP完全问题算法的可扩展性在理论计算机科学和实际应用中均具有重要意义。Cook[1]与Garey和Johnson[2]的奠基性研究为理解NP完全性奠定了基础，而Karp的开创性框架[3]则强调了组合问题间的内在关联。

预备知识

为使文章自成体系，本节汇总理解本研究所需的关键概念与结论。

模型推导

本节严格推导了着色与未着色情况下多米诺骨牌覆盖问题的整数线性规划（ILP）公式。推导基于二元向量（而非相关文献[36]中使用的二元矩阵）简化了建模过程。由于符号系统较为复杂，我们使用m和n分别表示每个线性系统中的行数与列数（即ILP中约束条件与未知数的数量）。

科学计算

本节概述了实现棋盘着色方法所用的计算工具，包括软件环境、算法细节以及评估可扩展性与潜在并行加速的性能指标。

实验设置

我们进行了三项大规模覆盖实验，以评估着色对ILP可扩展性的影响：一项单形体覆盖和两项多形体覆盖。每个问题均采用未着色覆盖、C=2着色和C=3着色进行求解，并同时使用CPLEX和Gurobi求解器以避免优化器特异性偏差。对于每个ILP，我们记录了约束条件数m、未知数n、找到可行解的运行时间以及潜在加速比。

一般性评论

由于通用覆盖问题具有NP完全性，减少相关ILP公式的规模（以n衡量）通常会缩短大规模问题的求解时间。然而，这种缩减并不能保证运行时间一定更快。实践中，求解器性能还受约束矩阵的结构与稀疏性、以及ILP求解器内部启发式算法等因素影响。在某些情况下，规模较小的公式可能密度更高或结构上更不理想，从而导致求解器性能下降。