The computation of the McMillan degree and structure at infinity of a transfer function model is considered for the family of early design models, referred to as Structured Transfer Function (STF) matrices. Such transfer functions have certain elements fixed to zero, some elements being constant and other elements expressing some identified dominant dynamics of the system. For the family of large dimension STF matrices the computation of the generic McMillan degree and structure at infinity are considered using genericity arguments which lead to optimization problems of integer matrices. A novel approach is introduced here that uses the notion of "irreducibility" of integer matrices, which is developed as the equivalent of irreducibility (properness) of polynomial matrices. This new notion provides the means for exploiting the structure of integer matrices and enables the termination of searching processes in a reduced number of steps, thus leading to an efficient new algorithm for the computation of the generic value of the McMillan degree and the structure at infinity of STFs. Links are made to standard optimization problems and to graph theory. The formulation of the optimization algorithm in terms of bipartite graphs offers better results and reduces the computational effort.