In the optimum coordination of Directional Overcurrent Relays (DOCRs), the appropriate relay settings, namely, Plug Setting (PS) and Time Multiplier Setting (TMS), are selected to minimize the operating time of relays subject to various coordination and boundary constraints. In the large interconnected power systems, the key issue with DOCRs protection is to achieve correct relay coordination with satisfying all coordination constraints. In this paper, the parameters of Harmony Search Algorithm (HSA) are tuned to effectively solve the relay coordination problem on five different test cases. Also, the relay coordination problem is formulated as Linear Programming Problem (LPP), Non-linear Programming Problem (NLPP) and Mixed-Integer non-linear programming Problem (MINLPP). In addition, the superiority of proposed method is demonstrated by comparing the obtained results with those obtained by the Genetic Algorithm (GA), hybrid GA-Nonlinear Programming (GA-NLP), Firefly Algorithm (FFA), and Cuckoo Search Algorithm (CSA). (C) 2017 Elsevier Inc. All rights reserved.