pareto_optimal_eps

Relational functions pareto_optimal_eps

syntax

pareto_optimal_eps(partition_rel, crit1, crit2, eps2, …, critN, epsN)

where the first criterion and a bool criterion have no eps (since 20.23.1), as in pareto_optimal_eps(part, Price, TravelTime, 0.01, NeedsCar, NeedsBike).

definition

pareto_optimal_eps(partition_rel, crit1, crit2, eps2, …, 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 relative epsilon-dominance, false for the others. It is pareto_optimal with a relative tolerance per criterion.

The elements of a partition are taken in the order of the criteria, as pareto_optimal sorts them: by crit1, then by crit2, and so on, and exact duplicates by index number. The first element is kept. Each next element is kept only when, against every element kept before it, it is more than the fraction eps better on at least one criterion after the first: crit < kept - eps * |kept|, which for nonnegative values is crit < (1 - eps) * kept. An element that comes later and is not more than eps better on any of the other criteria counts as dominated. An eps of 0 leaves that criterion exact; with all eps 0 the result equals that of pareto_optimal.

With two criteria this is the rule of the route search of impedance_matrix: after (t1, x1) a later element (t2, x2) is kept only when x2 < (1 - eps2) * x1, where x1 is the smallest x kept so far. With an eps2 of 0.01 a slower route must be more than 1% cheaper to stay.

The first criterion only orders: the element with the smallest first criterion always survives, so it takes no eps. Choose it as the criterion that must stay exact, for instance the price when the question is who can afford a trip, or the travel time when it is who can make it in time. An eps of 1 makes a later criterion one that only orders (for nonnegative values): it never keeps an element by itself, which suits a tie-break.

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, 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.
eps2 … epsN: numeric parameters, each directly after its numeric criterion from the second on, a fraction from 0 to 1 (0.01 = 1%). Each must be defined and dimensionless: an eps with a Metric is refused.

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

Since GeoDMS 20.23.1 the eps is relative. The interim builds 20.21.0 to 20.22.0, and builds of 20.22.1 from before 5 October 2026, took it as a bucket width in the unit of its criterion and compared floor(crit / eps): whether two nearly equal elements both survived then depended on where a bucket edge fell. With buckets of 0.10, a cost of 9.95 survived next to a faster 10.00, because they fall in the buckets 99 and 100, while 10.01 next to a faster 10.09 did not, both lying in bucket 100. Those builds also wanted an eps1 after the first criterion, which had no effect under the relative rule. A configuration written for those builds now stops with a message instead of having its widths read as fractions: an eps above 1, or with a metric such as 10[Ct] or 60[s], is refused, and so is a parameter after the first criterion, with a message that the first criterion takes no epsilon. Write the call as pareto_optimal_eps(part, crit1, crit2, 0.01, ...).

Since GeoDMS 20.23.1 a criterion may be Bool (#1287), minimised as in pareto_optimal: false before true, and not(x) where true is the better value. A bool criterion has no eps; it is compared exactly. The arguments are therefore read by their type: a numeric criterion after the first is followed by its eps; the first criterion and a bool criterion are followed directly by the next criterion. pareto_optimal_eps(part, Price, TravelTime, 0.01, NeedsCar, NeedsBike) has four criteria: the price, which orders, the travel time with a tolerance, and two bool. Before, a bool criterion gave Cannot find operator for these arguments, and the way around it was uint8(x), 0, which gives the same result and may stay.

So the number of arguments no longer tells how many criteria there are, and a forgotten eps is caught by type: a numeric criterion after the first takes the next argument as its eps, and when that is a bool or an attribute rather than a numeric parameter, or there is no next argument, the call is refused with a message that names the argument and the criterion. A Uint2 or Uint4 criterion is numeric and takes an eps like the others.

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 an eps of 0.01 on the cost, a slower route stays only when it is more than 1% cheaper than every faster route that stays.

Two properties bound what is lost:

the result is a subset of the exact result of pareto_optimal on the same arguments;
every element that drops out has a surviving element in its partition that is no worse on the first criterion and at most the fraction eps better than it on each other criterion: kept - eps * |kept| <= crit.

The element with the smallest first criterion of each partition, for instance the fastest route of an origin-destination pair, always survives.

This is the table form of the imp2_epsilon argument of the pareto section of impedance_matrix (see Impedance options). The route search applies the relative test to its second criterion, at every node and per destination zone; pareto_optimal_eps applies it to every criterion after the first, and reduces afterwards the union of several searches, or of several modes, to a thinned front. Thinning with the same eps as the search changes nothing in the result of that search.

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
eps2 … epsN with a Numeric value type, no Metric and the domain unit Void, one after each numeric criterion from the second on

conditions

All criteria have the domain unit of partition_rel. Each eps lies from 0 to 1.

since version

20.23.1

performance

As pareto_optimal: one sort of the elements on (partition, criteria, index number) and one sweep, n log n for n elements; with three or more criteria each element is compared with the elements kept so far in its partition. Since GeoDMS 20.23.1 the elements are first grouped per partition, and the partitions are sorted and swept in parallel, with the same result (see pareto_optimal).

example

attribute<bool> is_optimal (Route) := pareto_optimal    (Route/OD_rel, Route/Duration, Route/Cost);
attribute<bool> eps_50     (Route) := pareto_optimal_eps(Route/OD_rel, Route/Duration, Route/Cost, 0.5);
attribute<bool> eps_30     (Route) := pareto_optimal_eps(Route/OD_rel, Route/Duration, Route/Cost, 0.3);

Route/OD_rel	Route/Duration	Route/Cost	is_optimal	eps_50	eps_30
0	10	5.0	true	true	true
0	20	3.0	true	false	true
0	30	4.0	false	false	false
0	20	3.0	false	false	false
0	40	1.0	true	true	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	true
0	null	0.0	false	false	false

domain Route, nr of rows = 10

eps_50, the cost relative 50%: in OD pair 0 the fastest route (10, 5.0) is kept; (20, 3.0) is 40% cheaper, not more than 50%, and falls; (40, 1.0) is 80% cheaper and stays. In OD pair 1 (10, 1.0) is exactly 50% cheaper than the faster (5, 2.0), not more, and falls.
eps_30, the cost relative 30%: every route of the exact front is more than 30% cheaper than the routes kept before it, so nothing more drops out.

With a bool criterion, which takes no eps (since 20.23.1):

attribute<bool> exact  (Option) := pareto_optimal_eps(Option/OD_rel, Option/NeedsCar, Option/Price, 0);
attribute<bool> eps_50 (Option) := pareto_optimal_eps(Option/OD_rel, Option/NeedsCar, Option/Price, 0.5);

Option/Price	Option/NeedsCar	exact	eps_50
1	true	true	false
2	false	true	true
3	false	false	false
4	true	false	false

domain Option, nr of rows = 4

The options without a car come first. With the price exact, the cheapest of them and the cheaper option that needs a car both stay. With the price relative 50%, the option that needs a car is exactly half the price of the cheapest without one, not cheaper by more than 50%, and falls.