Costs in the interactive dependency resolver

Costs and cost components
Safety costs

Costs and cost components

The cost of a solution produced by the interactive dependency resolver is a value that aptitude uses to determine how bad that solution is. Solutions that are better are always displayed before solutions that are worse. The cost of solutions is defined in the configuration option Aptitude::ProblemResolver::SolutionCost.

Some typical costs are shown in Example 2.1, “Sample resolver costs”.

Example 2.1. Sample resolver costs

The default cost, sorting solutions by their safety cost, then by their apt pin priority:

safety, priority

Remove as few packages as possible, then cancel as few actions as possible:

removals, canceled-actions

Sort solutions by the number of packages they remove plus twice the number of actions they cancel.

removals + 2 * canceled-actions

As can be seen from the above examples, a cost is not necessarily a single number. In fact, a cost consists of one or more cost components, each of which is a number associated with the solution. When sorting solutions, the resolver examines cost components in order, proceeding to later components only if the earlier ones are equal. For instance, in the cost removals, canceled-actions, solutions with fewer removals always appear before solutions with more removals, regardless of how many canceled actions they have. However, solutions with the same number of removals are sorted so that solutions with fewer canceled actions appear first.

Cost components come in two flavors: basic cost components and compound cost components.

Basic components simply name some property of the solution, such as upgrades or removals. A list of built-in basic components provided by aptitude can be found in Table 2.1, “Basic cost components”. You can also create your own cost components using the add-to-cost-component and raise-cost-component hints; see the section called “Configuring resolver hints” for details.

Each basic component is either a counter or a level. Counters count how many of a solution's actions meet some condition (such as removing packages or installing new packages), while levels associate a number with each action and compute the highest number associated with any action in the solution.

Table 2.1. Basic cost components

broken-holdsCounter Counts the number of holds that the solution breaks, if the resolver is allowed to break holds (Aptitude::ProblemResolver::Allow-Break-Holds).
canceled-actionsCounter Counts the number of pending actions that the solution cancels (keeping packages at their current version).
installsCounter Counts the number of packages that the solution installs.
non-default-versionsCounter Counts the number of versions that the solution installs or upgrades from non-default sources.
priorityLevel A value that increases as the apt pin priority of a version decreases. Specifically, this is computed by negating the pin priority (so, e.g., if the pin priority is 500, this component will compute -500).
removalsCounter Counts the number of packages that the solution removes.
removals-of-manualCounter Counts the number of manually installed packages that the solution removes.
safetyLevel A broad heuristic that increases as actions become less safe; see the section called “Safety costs” for details.
upgradesCounter Counts the number of packages that the solution upgrades.

Compound components are built by combining the values of basic components. For instance, removals + canceled-actions adds the components removal and canceled-actions, resulting in a component that counts the number of removals and canceled actions. Compound components combine counters by adding them together and levels by taking their maximum value, as shown in Figure 2.11, “Syntax of compound cost components”.


It is an error to add two levels, or to take the maximum of two counters, or to combine levels and counters in any way. For instance, the costs removals + safety and max(upgrades, installs) will be treated as errors and ignored by the resolver.[13]

Figure 2.11. Syntax of compound cost components

Add two or more basic costs:

                [scale1]*cost1 + [scale2]*cost2 + ...

Take the maximum value of two or more basic costs:

                max([scale1]*cost1, [scale2]*cost2, ...)

Note that each individual basic component can be multiplied by a scaling factor before it is combined with other components. This can be used to control the trade-offs that the resolver makes between costs. For instance, a cost of 2*removals + 3*upgrades says that three removals are exactly as bad as two upgrades. Solutions that contain four removals and one upgrade will be considered equivalent to solutions containing one removal and three upgrades, since both have a cost of eleven.

Safety costs

Figure 2.12. Safety cost levels

Safety cost levels
[Safety cost levels diagram]

The safety cost component is a heuristic estimate of how safe or unsafe a solution is. Safety costs can be thought of as a way of dividing solutions into several numbered levels, where less safe levels are given higher numbers. Figure 2.12, “Safety cost levels” shows how this works with aptitude's default settings.


Safety cost levels are just one way to control the order in which dependency solutions are returned. See the section called “Costs in the interactive dependency resolver” for a full description of how to change the order in which aptitude sorts solutions.

By default, aptitude initializes the resolver with a reasonable set of safety cost levels. They are:

Table 2.2. Default safety cost levels

Cost levelDescriptionConfiguration option
10,000 Solutions that include only safe actions (installing the default target for a package or keeping a package at its current version) and package removals. Aptitude::ProblemResolver::Safe-Level, Aptitude::ProblemResolver::Remove-Level
10,000 The solution that cancels all the user's actions. It used to be higher than Aptitude::ProblemResolver::Remove-Level, but removing packages was ranked higher than keeping the same packages, even if the package was to be upgraded. Aptitude::ProblemResolver::Keep-All-Level
40,000 Solutions that break holds set by the user or install forbidden versions. Aptitude::ProblemResolver::Break-Hold-Level
50,000 Solutions that install packages from non-default versions (such as experimental, for instance). Aptitude::ProblemResolver::Non-Default-Level
60,000 Solutions that remove Essential packages. Aptitude::ProblemResolver::Remove-Essential-Level

If a solution qualifies for several safety cost levels, it will be placed in the highest one, that is, the one that appears last. For example, a solution that upgrades one package to its default version and breaks a hold on a second package will be placed at level 40,000. You can adjust the levels of individual versions using resolver hints; see the section called “Configuring resolver hints” for details. The default levels are illustrated in Figure 2.12, “Safety cost levels”.

[13] This limit was imposed because more complex cost structures could make it difficult to optimize the resolver. Future versions of the program might remove some of the restrictions if they turn out to be unnecessary.