A method may including obtaining, for an application, an application dependency including called components, and obtaining, using the called components, a component compatibility graph including a set of nodes and a set of edges each connecting a pair of nodes in the set of nodes. The pair of nodes may include a calling node and a called node. Each node may correspond to a component. The method may further include generating, from the component compatibility graph, a set of constraints including a set of edge variables corresponding to the set of edges, selecting, using the set of constraints, an edge subset of the set of edges, and recommending, for the application, an upgrade solution including installing a called component corresponding to a called node connected by an edge in the edge subset.