As traffic keeps increasing, En Route capacity, especially in Europe, becomes a serious problem. Aircraft conflict resolution, and resolution monitoring, are still done manually by controllers. Solutions to conflicts are empirical and, whereas aircraft are highly automated and optimized systems, tools provided for ATC control are very basic, even out of date. If we compare the current capacity and the standard separation to the size of controlled space, the conclusion is easy to draw: while ATC is overloaded, the sky is empty. It must be noticed that enhancing En Route capacity does not require optimal resolution of aircraft conflicts. The need for an automatic problem solver is also a serious concern when addressing the issues of free flight. It is still very much unclear how conflicts will be solved in free flight airspace. Human controllers highly rely on standard routes and traffic organization for solving conflicts; they are much quickly overloaded when controlling aircraft flying on direct routes. Free flight traffic, with a completely unorganized structure, might require automated, computer based, solvers. Moreover, one of the aim of free flight is to give aircraft optimal trajectories, whereas using ACAS techniques is certainly not optimal, and should only looked upon as a last issue system. In this paper, we present an optimal problem solver, based on a stochastic optimization technique (genetic algorithms). It builds optimal resolution for complex conflicts and also computes a large number of nearly optimal resolutions that do not violate separation constraints. Part 1 of the paper introduces the problem solver, its constraints and goals. Modelling is discussed in part 2. Part 3 introduces genetic algorithms techniques and the coding of the problem. Part 4 presents different examples of resolution of very complex test problems. In part 5 we present the complete ATC simulator, conflict detector and cluster builder used to benchmark the problem solver on real traffic; we also discuss weaknesses of the system and possible improvements.