Neutrosophic set (NS) was originally proposed by Smarandache to handle indeterminate and inconsistent information. It is a generalization of fuzzy sets and intuitionistic fuzzy sets. Wang and Smarandache proposed interval neutrosophic sets (INS) which is a special case of NSs and would be extensively applied to resolve practical issues. In this paper, we put forward generalized interval neutrosophic rough sets based on interval neutrosophic relations by combining interval neutrosophic sets with rough sets. We explore the hybrid model through constructive approach as well as axiomatic approach. On one hand, we define generalized interval neutrosophic lower and upper approximation operators through constructive approach. Moreover, we investigate the relevance between generalized interval neutrosophic lower (upper) approximation operators and particular interval neutrosophic relations. On the other hand, we study axiomatic characterizations of generalized interval neutrosophic approximation operators, and also show that different axiom sets of theoretical interval neutrosophic operators make sure the existence of different classes of INRs that yield the same interval neutrosophic approximation operators. Finally, we introduce generalized interval neutrosophic rough sets on two universes and a universal algorithm of multi-attribute decision making based on generalized interval neutrosophic rough sets on two universes. Besides, an example is given to demonstrate the validity of the new rough set model.