In this article, we tackle the conflict resolution problem using a new variant of the minimum weight maximum clique model. The problem consists in identifying maneuvers that maintain the required separation distance between all pairs of a set of aircraft while minimizing fuel costs. To this end, we design a graph whose vertices correspond to a finite set of maneuvers and whose edges connect conflict-free maneuvers. A maximum clique of minimal weight yields a conflict-free situation involving all aircraft and minimizing the costs induced. The innovation of the model relies on the cost structure: the cost of the vertices cannot be determined a priori, since they depend on the vertices in the clique. To tackle this feature, we formulate the problem as a mixed integer linear program. Since the modeling of aircraft dynamics and the computation of trajectories is separated from the solution process, the model is flexible. As a consequence, the mathematical framework presented in this article remains valid, whatever the hypotheses considered. In particular, in this paper aircraft can perform dynamic velocity, heading and flight level changes. To solve instances involving a large number of aircraft spread on several flight levels, we introduce two decomposition algorithms: the first one is a sequential mixed integer linear optimization procedure that iteratively refines the discretization of the maneuvers to yield a trade-off between solution time and cost. The second is a large neighborhood search heuristic that uses the first one as a subroutine. The best solutions for the available set of maneuvers are obtained in less than 10 seconds for instances with up to 250 aircraft randomly allocated to 20 flight levels.