As for constraints, you can model all decision variables as binaries and express conjunctive normal form as linear constraints.

In both cases (SAT and ILP), I think you'd need to make dedicated heuristics to have smth reasonable for package manager, so it boils down to the most adaptable codebase.

What would be your optimization objective? Probably some heuristic of what it means to be "up to date" with open questions as "Is it better to have indirect dependency very outdated rather than a direct one slightly outdated", but you'd also need to defined "very" and "slightly".