Skip to content
Snippets Groups Projects

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.