When evaluating virtual atoms, an expanded search space is considered which recursively traverses the dependencies of virtual packages from all slots matching a given virtual atom. All combinations in this expanded search space are considered when choosing an optimal combination to satisfy constraints with minimal cost.