基于整数线性规划的后布图线长优化方法

针对可切分布图,提出了一种同时考虑模块交换、模块翻转和空白面积再分配减少线长的新方法.对给定布图相应的切分树,引入一组二进制变量来表示切分树中每个运算符下的两个子树是否发生交换,然后对切分树进行遍历,将所有模块位置表示为这些二进制变量的线性函数.在此基础上,将模块翻转和空白面积再分配考虑进来,将这一问题构建为一个整数线性规划模型.实验结果表明,所提出方法较已有文献可以获得更大的线长改进,这为布图之后进一步提高布图质量提供了一种有效的方法.