This paper gives Interval Linear Programming (ILP) approach based solution to optimal relay coordination problem for microgrid scenario. Relay coordination in microgrids is complex because of varied fault current magnitude and direction due to existence of Distributed Generation (DG). Over-current relays are feasible and economic choice of protection for distribution systems connected with DG. The coordinated relay settings must account to all possible fault scenarios in both grid connected and isolated microgrid modes of operation. Inadequate fault current levels from grid connected to isolated mode is the major cause of miscoordination in the microgrid network. This paper systematically formulates the relay coordination problem for microgrid scenario as linear interval optimization problem. The feasibility of ILP method in including all the fault scenarios and operating modes of microgrid by representing the variables as intervals are combined to find the optimal overcurrent relay settings. The results show the effectiveness of this method. The programming is done using optimization tool box available in Matlab. © 2017 IEEE.