《电子技术应用》2023年第49卷第1期ComputerTechnologyandItsApplications计算机技术与应用一种基于线性规划的全局逃逸布线算法陈虹1，陈传东1，2，魏榕山1（1.福州大学物理与信息工程学院，福建福州350108；2.福建省光电信息科学与技术实验室，福建福州350108）摘要：有序逃逸布线问题作为PCB设计中的关键一环，属于一类特殊的NP-困难问题，近年来得到广泛研究。传统方法中，基于整数线性规划或者是拆线重布类的启发式算法只适用于引脚数目较少的PCB引脚阵列，否则容易出现时间违规而导致布线失败。针对传统方法中大规模全局自动布线难的问题，基于线性规划的全局自动布线算法提出采用线性规划解决逃逸布线问题，并提出降低线网容量化解拥塞的新方法。与最新的逃逸布线算法相比，在处理大规模问题时，该算法不仅可以实现全部引脚的有序逃逸，并且布线时间提升50%，节省31%线长。关键词：PCB自动布线；有序逃逸；线性规划；拥塞驱动中图分类号：TN47；TP391文献标志码：ADOI:10.16157/j.issn.0258-7998.222554中文引用格式：陈虹，陈传东，魏榕山.一种基于线性规划的全局逃逸布线算法[J].电子技术应用，2023，49(1)：97-101.英文引用格式：ChenHong，ChenChuandong，WeiRongshan.Algorithmofglobalescaperoutingproblembasedonlinearpro‐gramming[J].ApplicationofElectronicTechnique，2023，49(1)：97-101.AlgorithmofglobalescaperoutingproblembasedonlinearprogrammingChenHong1，ChenChuandong1，2，WeiRongshan1(1.SchoolofCollegeandInformationEngineering，FuzhouUniversity，Fuzhou350108，China；2.FujianScience&TechnologyInnovationLaboratoryforOptoelectronicInformationofChina，Fuzhou350108，China)Abstract：AsakeypartofPCBdesign,theorderedescaperoutingproblemisaspecialNP-hardproblem,whichhasbeenstud‐iedextensivelyinrecentyears.Inthetraditionalmethod,bothILPmethodandtheheuristicalgorithmsbasedonripping-upandreroutingareonlyapplicabletosmall-scaledpinarrayswithfewerpins,whicheasilyleadtotimeviolation.Aimingatthediffi‐cultyoflarge-scaleglobalroutingintraditionalmethods,theiteration-drivenmethodisproposedtosolvetheglobalescapingroutingproblembylinearprogramming(LP),andtooptimizeareacongestionbyreducingcapacity.Comparedwiththelatestwork,thisalgorithmcannotonlyescapeallpins...
