Model Program Integer untuk Problem Routing dalam Jaringan Telekomunikasi

Abstract

ABSTRACT GRIP is a global routing technique via integer programming. GRIP optimizes wirelength and via cost directly without going through a traditional layer assignment phase. Candidate routes spanning all the metal layers are generated using a linier programming pricing phase that formally accounts for the impact of existing candidate routes when generating new ones. To make an integer programming based approach applicable for today’s large scaled global routing instances, the original problem is decomposed into smaller sub-problems corresponding to rectangular sub-regions on the chip together with their assignments. Routes fragments of nets are connected in a flexible manner. In case of overflow, GRIP applies a second-phase optimization that explicitly minimize overflow. By using integer programming in an effective manner, GRIP obtains high-quality solutions. Keywords – Global Routing, Integer Programming.