MCAInterpolationRule

class paminco.algo.mca.MCAInterpolationRule(alpha: float, beta: float, m: int, x_max: float, accuracy: float = 1e-05)[source]

Breakpoint rule for MCA guaranteeing the \((\alpha, \beta)\)-approximation property.

This class manages the the breakpoint computation for the interpolation of the cost functions in the Marginal Cost Approximation (MCA).

The following assumptions on the cost functions \(F_e(x)\) and the marginal costs \(f_e(x) := F'_e(x)\) must be satisfied.

  • \(F_e\) is strictly convex and smooth.

  • For \(x \geq 0\), \(f_e''(x)\) is non-negative and non-decreasing

  • For \(x < 0\), \(f_e''(x)\) is non-positive and non-increasing

These properties are satisfied for functions of the form

\[F_e(x) = a_e |x_e| x_e^{k-1} + b_e\]

for \(k > 3\) and therefore apply for example to BPR functions for traffic networks or the activation functions typically used in the Weymouth equations in gas networks.

The step sizes \(\delta_i\) depending on \(x_i\) that this rule computes, satisfy the inequality

\[\delta_i B \leq 2 \sqrt{2} \sqrt{(\alpha-1) |f_e (x_i)| + \frac{\beta}{m x^{\max}}}\]

where \(B = \sqrt{ \max \{ |f''(x_i)|, |f''(x_{i+1})| \} }\). The breakpoint rule always includes \(x=0\) as breakpoint. The breakpoints are computed by solving the above inequality numerically up to a fixed precision given by the parameter accuracy, while rounding to the safe side.

Parameters
alphafloat

The parameter \(\alpha\) for the relative approximation error of the MCA output

betafloat

The parameter \(\beta\) for the absolute approximation error of the MCA output

mint

The number of edges of the network the rule is applied to. Needed, since the absolute error of all edges is additive, in order to ensure an overall absolute error.

x_maxfloat

The (absolute value of the) maximum flow value on one edge, or a bound on that value. An estimate on this value could be \(x^{\max} := \lambda^{\max} \frac{1}{2} \sum_{v \in V} |b_v|\).

accuracyfloat, default=1e-05

The accuracy for the numerical solution of the breakpoint inequality.

See also

paminco.network.cost.NetworkCostInterpolation
__init__(alpha: float, beta: float, m: int, x_max: float, accuracy: float = 1e-05)[source]

Methods

__init__(alpha, beta, m, x_max[, accuracy])

step(edge_cost, edge, x)

Compute the next breakpoint \(\delta\) by solving the inequality