Dombi family of t-norms includes a parametric family of continuous strict t-norms, whose members are increasing functions of the parameter. This family of t-norms covers the whole spectrum of t-norms when the parameter is changed from zero to infinity. In this paper, we study a nonlinear optimization problem in which the constraints are defined as fuzzy relational equations (FRE) with the Dombi family of t-norms. We firstly investigate the resolution of the feasible solutions set when it is defined with max-Dombi composition and present some necessary and sufficient conditions for determining the feasibility. Also, some procedures are presented for simplifying the problem. Since the feasible solutions set of FREs is non-convex, conventional nonlinear programming methods may not be directly employed to solve the problem. Based on some theoretical properties of the problem, a genetic algorithm is presented, which preserves the feasibility of new generated solutions. Moreover, a method is presented to generate feasible max-Dombi FREs as test problems for evaluating the performance of our algorithm. The proposed method has been compared with some related works. The obtained results confirm the high performance of the proposed method in solving such nonlinear problems.