Evaluating the new APT solver in 25.04

tl;dr:

  • The 3.0 solver runs if the classic one fails or apport is installed; in compatibility mode (it is allowed to remove manually installed packages).
  • If the 3.0 solver produces a worse result, a bug is filed with apport
  • If the 3.0 solver produces a result and the internal one failed; the 3.0 result will be used
  • You may notice up to 10s slower dependency resolution time in case the solver is unable to find a solution, the usual slow down should be sub-second.

Hi team,

apt 2.9.30ubuntu1 just migrated and enables the 3.0 solver as a fallback to the internal one, if that failed; and for automatic evaluation with apport.

This means that if the 3.0 solver upgrades fewer packages or deletes more packages to upgrade the same number of packages; an apport report will be created.

The 3.0 solver is a not-state-of-the-art[1] SAT solver and while it is super constrained and I did not experience it so far, there can be situations where it could run “forever” trying to find solutions to an unsolvable dependency problem (the SAT problem is NP-complete, if you have 300 upgrades, you need to try up to 2**300 choices!). For this release, a timeout of 10s has been added to ensure we eventually terminate.

Results from the 3.0 solver are only used if the internal one failed to find a solution. The 3.0 solver still has some bugs that will not be causing significant impact in this scenario:

  1. when a versioned Recommends is bumped in an upgrade it will try to reinstall it.

  2. It may sometimes remove a package due to a Breaks when upgrading another package where the classic solver would have chosen to keep back the upgrade.

A future version might use the 3.0 results if they are better than the classic solver as well. This would also not be impacted by more removals given that that would be a worse solution.

A known issue right now is that the 3.0 solver does not support violating the rules of apt-get upgrade and apt upgrade. The classic solver allows you to run apt-get upgrade foo- bar to install bar and remove foo (and dependencies); the 3.0 solver strictly requires the “no removals” and “no new installs” (apt-get) rules to be followed; so it may inadvertently create bug reports if you specify arguments to the upgrade command.

I hope that this change proves useful, and am looking forward to finalizing the solver for 25.10 and turning it on by default when the 25.10 series opens.

If you are more enthusiastic, you can use --solver 3.0 (or APT::Solver "3.0"; in apt.conf) to use the 3.0 solver as the default. Please note that the 3.0 solver by default does not allow removing manually installed packages, so it’s important to maintain a good “manual marking hygiene”.

[1] Conflict-driven clause learning is still WIP. This change may be crucial for very complex upgrade cases to be solvable; albeit I have plenty of upgrade tests from mantic to noble and noble/devel time_t upgrades and I have not been able to trigger the pathological case.

3 Likes