In this paper the problem of directional overcurrent relays coordination in interconnected power networks is presented and solved using the optimization theory. Linear programming with Simplex two-phase method is applied to minimize the operating time of the relays. The insignificance of weighting factors and far-end fault consideration in the problem formulation is proved, through a mathematical example, by simulation, mathematically, graphically and by sensitivity analysis. The current transformer (CT) selection is achieved based on the maximum load and fault currents in order to prevent the miscoordination problem resulting from CT's saturation. A complete algorithm for calculating the optimal operating times is introduced and applied to sample examples.