Any-direction wires and complex obstacle environments in emerging Printed Circuit Board (PCB) routing applications impose new challenges for length matching. To address these challenges, we develop a suite of area assignment approaches that leverage network flow theory and Linear Programming (LP) techniques. First, we partition the initial PCB region into a set of subregions and propose an LP formulation to model the area assignment of subregions to the wires in sparse PCB layouts. We then refine the LP formulation to handle dense PCB scenarios effectively. To enhance the algorithm’s performance further, we introduce utility constraints that consider complex obstacles and propose an Integer Linear Programming (ILP) model to optimize the subregion area assignment. Given the high computational complexity of solving the ILP model, we develop a combinatorial algorithm based on minimum-weight hierarchical flow to efficiently tackle the area assignment problem. By leveraging LP primal-dual techniques, we demonstrate that the proposed algorithm achieves near-optimal solutions even under upper bound constraints, and we further extend the approach to accommodate lower bound constraints. Notably, our algorithm allows the modification of the wire topology to generate better area assignment solutions. In addition, the proposed methodology is extensible to length-matching tasks in multilayer PCB designs. Lastly, we conduct extensive experiments to evaluate the effectiveness of our approach, demonstrating significant performance improvements over existing state-of-the-art methods, particularly in complex PCB routing scenarios.
Lin et al. (Mon,) studied this question.