Next-generation APT solver
Project Kal El implements the most sophisticated solver in the history of package managers, using Clasp1 and pseudo-boolean optimisation to ensure optimal results in all use cases.
Representation of problems
Representation of dependencies
Dependencies are represented as sums of versions, for example, the
positive dependency of x1
on x2
and x3
is represented as the
constraint:
-x1 + x2 + x3 >= 0
If x1 = true
, then one of x2
and x3
must be true to satisfy the
constraint on the right hand side.
Negative dependencies (conflicts) are represented similarly:
-2 x1 - x2 - x3 >= -2
that is, when x1
is installed, the lhs is -2
. If one of the other
packages were installed, it would become -1
or 0
, not satisfying
the constraint.
Representation of criteria
Criterias are a sum of literals representing packages, or versions, that
will be minimized, e.g. min: x1 + x2 + x3
.
The members of the sum might have weights.
Multiple criteria can be run after each other. In this case, the first
criterion's result will be added as a hard constraint to the next solving
step. This ensures that a later criterion does not worsen the result of
a previous criterion
.
Merge Optimisation: If two criteria a, b
have the same sign, then
b
can be merged into a
if maxsum(a)*(maxsum(b)+1)
does not
overflow, by multiplying each member of a with maxsum(b)+1
, and then
adding b
to it; for example, given the criteria
x1 + x2 + x3
x4 + x5 + x6
we can merge them into 4x1 + 4x2 + 4x3 + x4 + x5 + x6
.
Representatio
Criteria
Kal El currently implements the changed and new criteria used by all EDSP solvers. It is expected to also learn the other common criteria, and some more listed below.
Order preservation
Debian packages commonly specify dependencies of the form
preferred|alternative
. Kal El will deal with that with an
ordering criteria, scoring each package. A package gets 10^5
for being a preferred choice, 10^4
for 2nd choice, and so on,
with choices other than the 6 most preferred ones getting a score of 0.
Recommends
Kal El will gain a criteria that it installs as many Recommends from newly installed packages as possible, and as many new Recommends for upgrades as possible.
Non-candidate installations
We will order all versions of all packages, and then optimise the number of satisfied candidates, followed by the number of second choices, third, and so on.
Pattern criteria
Once we get aptitude-style patterns in apt, it should be possible to
specify criteria using patterns, e.g. ?name(apt)
to maximise installed
packages called apt, and -?name(apt)
to minimize them, or some other
syntax.