EFA: Electrical Flow Algorithm¶

Class Description¶

class paminco.algo.efa.EFA(network: paminco.net.network.Network, name=None, callback=None, use_simple_timer: bool = True, preprocess_network: bool = True, phase1_of: Optional[paminco.algo.efa.EFA] = None, copy_network: bool = True, **kwargs)[source]¶

Electrical flow algorithm.

Computes a piecewise linear optimal potential function that induces a piecewise linear minimum cost flow function. The underlying network must have piecewiese quadratic edge costs.

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 EFA. If True, timestamps for intializtion and every iteration will be saved to attribute timer.
phase1_ofEFA, default=None: The main EFA object of a 2-phase EFA run. If set to something other than None, it is assumed that this EFA object is used to compute the initial solution for the EFA run of the phase1_of object. If set, the is_phase1 property of this object will be set to True.
kwargskeyword arguments, optional: For further options of EFA, see EFAConfig.

See also

EFAConfig: Settings for EFA.

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

Example 2 from [Kli21]:

>>> import numpy as np
>>> import matplotlib.pyplot as plt
>>> import paminco
>>> ex2 = paminco.net.load_example(2)
>>> efa = paminco.EFA(ex2, lambda_max=10)
>>> efa.run()
>>> fig, (ax0, ax1, ax2) = plt.subplots(nrows=1, ncols=3, sharex=True, sharey=True, figsize=(12, 3))
>>> d = {0: ax0, 1: ax1, 2: ax2}
>>> ls = np.linspace(0, 10, 100)
>>> for edge, ax in d.items():
...   efa.plot_flow_on_edge(edge, x=ls, ax=ax) 
...   ax.set_title(f"Edge {edge}") 
...   ax.set_xlabel("$\lambda$") 
...   ax.set_ylabel("flow") 

Settings and Subclasses¶

`EFAConfig`(**kwargs)	Settings for running the electrical flow algorithm (EFA).
`NodePotentials`(net_nodes)	Class that stores values that relate to the potential in some region.
`EFAEdges`(source_target)	Object that stores edge values during EFA run.
`EFABreakFlag`(value)	Class that defines breakflags for the EFA algorithm.
`PivotStepMode`(value)	Enum defining the pivot step mode.

Attributes¶

`EFA.network`	Get network obj.
`EFA.name`	Get name of object.
`EFA.config`	Get configuration of solver.
`EFA.region`	ndarray of int: piecewise cost region of edges.
`EFA.edges`	Object that keeps track of edge values for current region.
`EFA.edge_coeffs`	Edge coefficients for current region.
`EFA.node_potentials`	Object that keeps track of node potentials of current region.
`EFA.L0`	spmatrix: Laplacian for initial region.
`EFA.region_zero`	ndarray of int: initial region in piecewise cost funcs.

Methods¶

`EFA.__init__`(network[, name, callback, ...])
`EFA.run`([callback])	Run the EFA algorithm for given network.