Set-Pair Routing Solver with Layer-by-Layer Formulation on ILP

This paper presents an Integer Linear Programming (ILP) formulation addressing the set-pair routing problem. The optimization framework involves calculating routing lower bounds, implementing the min-cost max-flow algorithm, and seeking to minimize the maximum length while maximizing the minimum length. Incremental and binary search methods are employed for optimization. Experimental validation of the proposed methods against existing approaches reveals substantial speed improvements. In run-time comparisons, both the incremental (INC) and binary search (BS) methods surpasses the performance of established approaches. Notably, the proposed methods demonstrates success in solving instances that posed challenges for existing methods, as evidenced by the obtained length results.