Obstacle-Aware Longest-Path Routing with Parallel MILP Solvers

Abstract—Longest-path routing problems, which can arise in the design of high-performance printed circuit boards (PCBs), have been proven to be NP-hard. In this article, we propose a mixed integer linear programming (MILP) formulation to gridded longest-path routing problems; each of which may contain obstacles. After a longest-path routing problem has been transformed into an MILP problem, parallel MILP solvers can be used to find optimal solutions. In addition, suboptimal solutions can be generated in exchange for reduced execution time. The proposed formulation method can also be used to solve shortest-path routing problems. Experimental results show that more than 3,700X speed-up can be achieved by using 16 threads in solving formulated longest-path routing problems. The execution time can be further reduced if more processer cores are available.