pareto_optimal

syntax

pareto_optimal(partition_rel, crit1, …, critN)

definition

pareto_optimal(partition_rel, crit1, …, critN) results in a boolean Attribute with the Domain unit of its arguments: true for the elements that are Pareto-optimal within their partition on the criteria crit1 to critN, all of which are minimised, false for the others.

An element is dominated when another element of the same partition is less than or equal on every criterion and strictly less on at least one of them. Elements that are equal on all criteria are exact duplicates: the first of them (the lowest index number) is optimal and the others are not, so the true elements of a partition are its distinct Pareto front, one representative per combination of criterion values. An element with a Null partition or a null criterion is never optimal and dominates nothing.

partition_rel: a relation to a domain unit, the partition within which elements are compared
crit1 … critN: one to eight numeric or bool attributes, the criteria. They may have different value types; they are compared as float64. A criterion that should be maximised is negated by the modeller.

Since GeoDMS 20.23.1 a criterion may be Bool (#1287), such as whether a route needs a car. It is minimised like the others, false before true, as the values 0 and 1: a route that needs no car is better on that criterion. Where true is the better value, write not(x). Before, a bool criterion stopped with criterion 2 must be numeric, and uint8(x) was the way around it; that form gives the same result and may stay. A Uint2 or Uint4 criterion was accepted by the same check but then failed with an internal error; it now works like any other numeric criterion.

description

The function replaces the self-join idiom for a Pareto selection: a Join_equal_values of a partition relation with itself, per pair a conjunction of <= over the criteria with a tie-break on the index number, and Any over the pairs. That idiom materialises every pair of elements within a partition, k² pairs for a partition of k elements, and compares all with all. pareto_optimal sorts the elements once on (partition, crit1, …, critN, index number) and sweeps that order per partition, which costs n log n for the sort and, with two criteria, one comparison per element: every earlier element of the partition already has crit1 less than or equal, so an element is optimal exactly when its crit2 is below the smallest crit2 accepted so far. This is the rule with which the pareto option of impedance_matrix keeps its fronts during the route search (see Impedance options), applied afterwards to a table. With three or more criteria each element is compared against the elements of its partition accepted so far only; their number is the size of the front, not of the partition.

With one criterion the result marks the minimum per partition, the first occurrence on ties.

When an exact front is larger than needed, because every small step in one criterion paid for with a small step in another is a front member of its own, pareto_optimal_eps thins it: a later element stays only when it is more than a fraction the modeller chooses better on some criterion than every element kept before it.

The subset itself follows with select_with_attr_by_cond or collect_by_cond on the result, or the result is kept as a condition on the original domain.

applies to

partition_rel with a Value type of the group CanBeDomainUnit
crit1 … critN with a Numeric value type or the value type bool, and value composition Single

conditions

All arguments have the same domain unit.

since version

20.23.1

performance

One sort of the elements on (partition, crit1, …, critN, index number), n log n for n elements, and one sweep: with one or two criteria one comparison per element, with three or more one comparison per element of the partition’s front accepted so far. The self-join it replaces compares k² pairs for a partition of k elements. On a table of 4.4 million routes in 78,717 origin-destination pairs, 56 per pair on average, the self-join formed 396 million pairs in 5 seconds, while pareto_optimal took a fraction of a second with the same result.

Since GeoDMS 20.23.1 the work is split by partition, and every step runs on all available threads. The elements are first brought together per partition value, by a radix sort on that value alone, which needs no pass at all when partition_rel is already ascending and fewer passes the closer together its values lie; then every partition is sorted and swept on its own. The result is the same as before; only the time changes. Before, only the one big sort ran in parallel and reading the arguments, the sweep and writing the result used one thread. In the chain joiner of NetworkModel_PBL, 29 calls with up to 105 million elements in partitions of about 100, all together took 7.2 seconds instead of 25.1; on 40 million elements in 400,000 partitions, 1.5 seconds instead of 6.7 (#1286).

Working memory at its peak, during the radix sort: about 32 bytes per element plus 8 per criterion.

example

attribute<bool> is_optimal (Route) := pareto_optimal(Route/OD_rel, Route/Duration, Route/Cost);
unit<uint32> front := select_with_attr_by_cond(Route, Route/is_optimal);

Route/OD_rel	Route/Duration	Route/Cost	is_optimal
0	10	5.0	true
0	20	3.0	true
0	30	4.0	false
0	20	3.0	false
0	40	1.0	true
0	40	1.0	false
1	10	1.0	true
1	10	1.0	false
1	5	2.0	true
0	null	0.0	false

domain Route, nr of rows = 10

In OD pair 0 the third route (30, 4.0) is dominated by (20, 3.0), the fourth is a duplicate of the second and the sixth a duplicate of the fifth; in OD pair 1 the two routes (10, 1.0) and (5, 2.0) do not dominate each other and the duplicate falls away. The last route has a null duration and is never optimal.

With a bool criterion (since 20.23.1), a public transport option that is more expensive than a car trip stays on the front because it needs no car:

attribute<bool> is_optimal (Option) := pareto_optimal(Option/OD_rel, Option/Price, Option/NeedsCar);

Option/Price	Option/NeedsCar	is_optimal
1	true	true
2	false	true
3	false	false
4	true	false

domain Option, nr of rows = 4

The first option is the cheapest and needs a car, the second is the cheapest without one; the third and the fourth are dominated by the second.