提出新评估方法，加速解决大规模列排列问题
A $Δ$-evaluation function for column permutation problems
- 基于Δ的新型评估机制，专为稀疏二值矩阵设计
- 在门阵列布局等实例上，处理速度优于现有方法
- 适合需要快速求解的大规模工业优化问题
本研究针对具有连续1性质的稀疏二值矩阵上的列排列问题，提出一种新的Δ-评估方法。该问题可建模图论与工业制造中的多种NP难问题。通过大量实验，对比了Δ评估法与两种经典局部搜索方法的计算耗时。研究涵盖门阵列布局、最小化开放栈等典型问题实例。结果表明，所提方法总体性能具有竞争力，尤其在大规模、高密度实例上表现优异，可无缝集成至局部搜索与元启发式算法中，在不显著增加计算时间的前提下提升解的质量。
原文摘要 · Abstract (English)
In this study, a new $Δ$-evaluation method is introduced for solving a column permutation problem defined on a sparse binary matrix with the consecutive ones property. This problem models various $\mathcal{NP}$-hard problems in graph theory and industrial manufacturing contexts. The computational experiments compare the processing time of the $Δ$-evaluation method with two other methods used in well-known local search procedures. The study considers a comprehensive set of instances of well-known problems, such as Gate Matrix Layout and Minimization of Open Stacks. The proposed evaluation method is generally competitive and particularly useful for large and dense instances. It can be easily integrated into local search and metaheuristic algorithms to improve solutions without significantly increasing processing time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。