MCA: Marginal Cost Approximation¶

Class Description¶

class paminco.algo.mca.MCA(network: paminco.net.network.Network, name=None, callback=None, use_simple_timer: bool = True, copy_network: bool = True, **kwargs)[source]¶

Marginal Cost Approximation.

This method interpolates the marginal edge cost and then runs EFA to compute an exact optimal potential (and thus minimum cost flow) function. Thus, MCA is an approximate solver, where the approximation error arises from the spline-interpolation, and is named as marginal cost approximation (MCA).

Parameters

netNetwork: Network to find parametric min cost flows for.
namestr, optional: Name of solver.
callbackcallable, or list of callable, optional: Callbacks called during initialization and run method. Can be used for debugging and timing.
use_simple_timerbool, default=True: Whether to time MCA. If True, timestamps for intializtion and every iteration will be saved to attribute timer.
kwargskeyword arguments, optional: Further options for MCA, see MCFIConfig.

See also

MCAConfig: Settings for MCA.
MCAInterpolationRule: Piecewise linear interpolation of the edge cost.
paminco.algo.efa.EFA: Electrical flow algorithm to be run on modified network with piecewise quadratic cost.

References

Kli21: Klimm, Max, and P. Warode. “Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs.” Mathematics of Operations Research (2021). Available 10/25/2021 at https://www3.math.tu-berlin.de/disco/research/publications/pdf/KlimmWarode2021.pdf

Examples

SiouxFalls: a parametric Price of Anarchy:

>>> import copy
>>> import numpy as np
>>> import matplotlib.pyplot as plt
>>> import paminco
>>> sioux = paminco.load_sioux()
>>> sioux.set_demand(("20", "3", 100000))
>>> # --- Run MCA for user equilibrium
>>> sioux_ue = copy.deepcopy(sioux)
>>> sioux_ue.cost.integrate(inplace=True)
>>> mca_ue = paminco.MCA(sioux_ue)
>>> mca_ue.run()
>>> # --- Run MCA for system optimum
>>> sioux_so = copy.deepcopy(sioux) 
>>> sioux_so.cost.times_x(inplace=True)
>>> mca_so = paminco.MCA(sioux_so)
>>> mca_so.run()
>>> # compute POA
>>> def TTST(x):
...   return sioux_so.cost.F(x).sum()
>>> lambdas = np.linspace(1e-5, 1, 100)
>>> cost_ue = np.array([TTST(mca_ue.flow_at(l)) for l in lambdas])
>>> cost_so = np.array([TTST(mca_so.flow_at(l)) for l in lambdas])
>>> poa = cost_ue / cost_so

Determine edge flow in user equilibrium as a function of demand factor:

>>> import matplotlib.pyplot as plt
>>> import paminco
>>> net = paminco.net.load_sioux()
>>> net.integrate_cost()
>>> net.set_demand(("2", "21", 100000))
>>> mca = paminco.MCA(net)
>>> mca.run()
>>> mca.plot_flow_on_edge(55): 

Parametric natural gas flows:

>>> import matplotlib.pyplot as plt
>>> import paminco
>>> net = paminco.net.load_gas("gas24")
>>> net.size
(18, 19, 1)
>>> net.cost.integrate(inplace=True)
>>> demand_dir = ("entry03", "exit05", abs(net.demand()).sum())
>>> net.set_demand((net.demand.b, demand_dir), mode="affine")
>>> mca = paminco.MCA(net)
>>> mca.run()
>>> fig, (ax0, ax1) = plt.subplots(nrows=1, ncols=2, sharex=True, figsize=(12, 4))
>>> d = {5: ax0, 8:ax1}
>>> for edge, ax in d.items():
...     mca.plot_flow_on_edge(edge, ax=ax) 
...     ax.set_xlabel("$\lambda$")
...     ax.set_ylabel("flow")
...     ax.set_title(f"Parametric gasflow for edge {edge}")

Attributes

region: ndarray of int: piecewise cost region of edges.
edges: Object that keeps track of edge values for current region.
edge_coeffs: Edge coefficients for current region.
node_potentials: Object that keeps track of node potentials of current region.

Main Idea¶

Instead of computing a solution to the actual problem - i.e., a parametric mincost flow w.r.t. to the demand factor - the MCA algorithm uses marginal cost \(s_f(x)\) that are a piecewise linear interpolation of the original marginal costs \(f_e(x)\). This problem can then be solved exactly with the EFA algorithm. This main idea is shown in the following image, where we follow the orange arrows to calculate a \((\alpha, \beta)\)-approximate minimum cost flow.

Settings and Interpolation¶

`MCAConfig`(**kwargs)	Settings for MCA algorithms.
`MCAInterpolationRule`(alpha, beta, m, x_max)	Breakpoint rule for MCA guaranteeing the \((\alpha, \beta)\)-approximation property.

Attributes¶

`MCA.network`	Get network obj.
`MCA.name`	Get name of object.
`MCA.config`	Get configuration of solver.
`MCA.i`	Get current iteration count.
`MCA.lambda_min`	Get current lambda_min.
`MCA.lambda_max`	Get current lambda_max.
`MCA.breakflag`	Get current breakflag value.
`MCA.region`	ndarray of int: piecewise cost region of edges.
`MCA.edges`	Object that keeps track of edge values for current region.
`MCA.edge_coeffs`	Edge coefficients for current region.
`MCA.node_potentials`	Object that keeps track of node potentials of current region.
`MCA.param_solution`	Get ParametricSolution object.
`MCA.L0`	spmatrix: Laplacian for initial region.
`MCA.region_zero`	ndarray of int: initial region in piecewise cost funcs.

Methods¶

MCA.run([callback])