Inter-domain traffic engineering is a key issue when QoS-aware resource optimization is concerned. Mapping inter-domain traffic flows into existing service level agreements is, in general, a complex problem, for which some algorithms have recently been proposed in the literature. In this paper a two-phase algorithm to optimize the utilization of domain resources both from a technical perspective and a monetary costs perspective is proposed. The first phase is carried out by a greedy random algorithm, which returns a feasible solution. This is followed by an improvement phase performed by a genetic algorithm, which returns the optimal solution. Results show that the first phase produces quasi-optimal resource assignments for regional ISPs and outer core autonomous systems (AS). For transit core and dense core ASs, where the number of aggregate flows is considerably higher, the second phase leads to significant improvement.