Legalized routing is an essential part of PCB automatic routing. It solves the problem of wiring conflicts and obtains routing results that comply with the constraints of design rules. Traditional legalized routing problems mostly use trial backtracking methods, but with increasing design complexity and design rules, avoiding wiring conflicts between networks has become increasingly challenging. This paper proposes a legalized routing algorithm based on linear programming to obtain the optimal wiring trajectory under specified topological constraints. First, the corresponding routing model was established based on numerous routing rules, and a routing grid diagram was found using obstacles as grid points. Secondly, a global routing algorithm was used to obtain the estimated wiring path, and integer linear programming was used to realize the mathematical modeling of the legalized routing problem. Finally, a multi-line simultaneous routing strategy was used to design and implement a detailed routing algorithm, optimizing the routing results. We use C++ to complete the coding work and thoroughly test the PCB use cases of different sizes. The experimental results show that our algorithm still maintains a 100% routing success rate, good time performance, and excellent routing quality with large-scale use cases compared with the trial backtracking method.

Redistribution layer ordered routing is a critical problem in fan-out wafer-level chip-scale packaging (WLCSP) design. The traditional integer linear programming (ILP) method is inefficient in dealing with the ordered routing problem of multiple-capacity. Hence, we propose a high-performance ordered routing algorithm to solve the multiple-capacity ordered routing problem on the redistribution layer (RDL). First, we transform the ordered routing problem into the min-cost multi-commodity flow (MMCF) problem and use the linear programming (LP) method to solve it. Then, we use depth-first search (DFS) to process the LP method flow results and obtain the pre-assignment I/O candidate paths. Finally, the candidate path set obtains legal routing results by setting the crossing weight and a heuristic algorithm to receive the minimum crossing weight. When the pre-assignment I/O routing is uncompleted, we will set the capacity of tile nodes and edges to 0 and perform iterative routing for better results. Compared with the state-of-the-art work, experimental results show that our algorithm can solve twice the scale of the RDL ordered routing problems and reduce the routing time by 17% when dealing with multi-capacity RDL ordered routing problems.