Improving the APT Solver: Elegantly Handling the Removal of Manually Installed Packages

This post details improvements to an APT package manager solver. Initially, manually installed packages were treated as fixed facts, while automatically installed packages were optional unit clauses. However, allowing the removal of manually installed packages broke the solver; it could unnecessarily remove them. The author solves this by initially assuming all optional clauses, then iteratively unwinding these assumptions during the solving process. This approach, while not globally optimal, proves effective in practice for dependency resolution, avoiding the exponential complexity of a global search.