For any Linux Distro's packaging system, find the maximum number of simultaneously installable packages

The brute force option is the only option in this case. Here is a paper that will describe why in depth but the issue is that package installation and dependency/conflict resolution is a NP-Complete problem.

A problem is in NP if every TRUE answer has an easily-checked polynomial-size explanation. In this case this can be done by listing the installed packages and available packages.

Debian package installation is in NP-hard if an efficient solution for the problem can be adapted to efficient solutions to every other problem in NP. I will defer to the above listed paper as it is a bit complex to prove here but it can be encoded as 3-SAT.

As Debian package installation is in NP and NP-hard, thus it is NP-complete.

Here are some ways the default solver in APT tries to avoid the NP-completeness:

• Use of heuristics
• A preference for the first element in an or-group
• A strict package version convention
• Giving up when it encounters a major conflict.

Basically the constraints have to be specifically designed to get the problem to fall into known tractable classes for a NP-Complete problem like HORN-SAT

Unfortunately find the maximum possible number of installable packages for a given system pretty much excludes all of the known tractable classes that I am aware of.

So brute force is the only option and an expensive one until a suitable tractable class is discovered or if someone proves that P=NP.