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 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.

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: it compares each criterion in buckets of a width the modeller chooses.

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 and value composition Single

conditions

All arguments have the same domain unit.

since version

20.21.0

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.

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.