pareto_optimal_eps

Relational functions pareto_optimal_eps

syntax

pareto_optimal_eps(partition_rel, crit1, eps1, …, critN, epsN)

definition

pareto_optimal_eps(partition_rel, crit1, eps1, …, critN, epsN) results in a boolean Attribute with the Domain unit of its arguments: true for the elements that are Pareto-optimal within their partition under epsilon-dominance, false for the others. It is pareto_optimal with a bucket width per criterion.

Each criterion is compared in buckets of width eps: instead of the value crit itself, floor(crit / eps) is compared. An element is dominated when another element of the same partition lies in a lower or equal bucket on every criterion, so a partition keeps at most one element per box of buckets. An eps of 0 leaves that criterion exact; with all eps 0 the result equals that of pareto_optimal.

Which element of a box survives is decided by the order of the elements: the smallest raw values in criterion order, and among exact duplicates the lowest index number. So eps1 decides which elements count as equal on the first criterion, among those the lowest bucket of the second criterion wins, and within that bucket the smallest raw first criterion.

partition_rel: a relation to a domain unit, the partition within which elements are compared
crit1 … critN: one to eight numeric attributes, the criteria, all of which are minimised. They may have different value types; they are compared as float64. A criterion that should be maximised is negated by the modeller.
eps1 … epsN: numeric parameters, each directly after its criterion, the bucket width of that criterion in the unit of that criterion. Each must be defined and nonnegative. Their values units are not checked against the criteria, so a plain number such as 0.10 is accepted.

An element with a Null partition or a null criterion is never optimal and dominates nothing.

description

Exact Pareto fronts can be large when the criteria take many distinct values: every small step in cost that is paid for with a small step in time is a front member of its own. pareto_optimal_eps thins such a front to a resolution the modeller chooses: with a cost eps of 10 cent, two routes whose costs differ by less than 10 cent are no longer both kept for being cheaper than the other.

Two properties bound what is lost:

the result is a subset of the exact result of pareto_optimal on the same arguments;
every exactly optimal element that drops out has a surviving element in its partition that is less than eps worse or better on every criterion, since its buckets are lower or equal on all of them.

With an eps1 of 0 on the first criterion, the element with the smallest first criterion of each partition, for instance the fastest route of an origin-destination pair, always survives. With an eps1 above 0 it need not: an element in the same bucket of the first criterion that is cheaper on the second takes its place, see the example.

A value that lies within a millionth of a bucket width below a bucket edge counts in the higher bucket, so that 0.30 with an eps of 0.10 lies in bucket 3 despite floating-point rounding.

This is the table form of the imp2_epsilon argument of the pareto section of impedance_matrix (see Impedance options). The route search buckets its second criterion only and always keeps the fastest route per bucket; pareto_optimal_eps can bucket every criterion, and reduces afterwards the union of several searches, or of several modes, to a thinned front.

applies to

partition_rel with a Value type of the group CanBeDomainUnit
crit1 … critN with a Numeric value type and value composition Single
eps1 … epsN with a Numeric value type and the domain unit Void

conditions

All criteria have the domain unit of partition_rel.

since version

20.21.0

performance

As pareto_optimal: one sort of the elements on (partition, buckets, criteria, index number) and one sweep, n log n for n elements.

example

attribute<bool> is_optimal (Route) := pareto_optimal    (Route/OD_rel, Route/Duration, Route/Cost);
attribute<bool> eps_cost   (Route) := pareto_optimal_eps(Route/OD_rel, Route/Duration, 0, Route/Cost, 5.0);
attribute<bool> eps_time   (Route) := pareto_optimal_eps(Route/OD_rel, Route/Duration, 30, Route/Cost, 0);

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

domain Route, nr of rows = 10

eps_cost, cost in buckets of 5.0: in OD pair 0 the costs 5.0, 3.0 and 1.0 lie in the buckets 1, 0 and 0, so (40, 1.0) falls away because the faster (20, 3.0) already occupies bucket 0; in OD pair 1 the costs 1.0 and 2.0 share bucket 0 and the faster (5, 2.0) stays. The fastest route of each pair survives, since the duration is exact.
eps_time, duration in buckets of 30: in OD pair 0 the durations 10 and 20 count as equally fast, so the cheaper (20, 3.0) takes the place of (10, 5.0); in OD pair 1 all durations lie in bucket 0 and the cheapest (10, 1.0) takes the place of the fastest (5, 2.0).

An eps of 0.10 on the cost changes nothing on this table: the costs 5.0, 3.0 and 1.0 lie in the buckets 50, 30 and 10.