A generalized colouring method for a parallelizable integer linear programming approach to polyomino tiling

doi:10.1016/j.jocs.2025.102734

A generalized colouring method for a parallelizable integer linear programming approach to polyomino tiling

2025-10-24

0

PRE

AI

DOI：10.1016/j.jocs.2025.102734

原文链接

原文求助

摘要

En 中文

本文提出了一种广义棋盘着色方法，用于通过整数线性规划（ILP）求解大型多联骨牌铺砌问题。该方法在扩展以往的双色方法基础上，可扩展至三种或更多颜色，并在双色方法无优势的情况下改善运行时间。我们严格推导了着色与不着色两种情况下的ILP公式，并提出了一种概念验证的并行实现方案，以提升这些NP完全铺砌问题的可扩展性。使用MATLAB、CPLEX和Gurobi进行的数值实验表明，该方法显著减小了问题规模和计算时间。这一方法有望解决比以往通过ILP方法可处理的更大规模的铺砌问题。尽管我们的着色方法会生成许多子问题，但它允许高效探索可管理的子集以寻找可行解。我们公开可用的MATLAB软件包CHROMINOES（v1.0.0）能够构建ILP公式、绘制解，并可在Zenodo.org上下载。最后，我们讨论了这些结果的意义，并概述了开发完全实用的并行实现所面临的关键挑战，包括负载均衡以及管理处理大量子问题所带来的开销。

A generalized colouring method for a parallelizable integer linear programming approach to polyomino tiling

摘要

期刊

机构

引用论文