optiwindnet.heuristics

Package Contents

optiwindnet.heuristics.ClassicEW(L: networkx.Graph, capacity: int, delaunay_based: bool = False, maxiter: int = 10000, weightfun: Callable | None = None, weight_attr: str = 'length') → networkx.Graph[source]

Classic Esau-Williams heuristic for C-MST.

Parameters:

  • L – location graph

  • capacity – max number of terminals in a subtree

  • maxiter – fail-safe to avoid locking in an infinite loop

Returns:

Routeset graph G

optiwindnet.heuristics.constructor(Aʹ: networkx.Graph, capacity: int, method: str = 'rootlust', *, rootlust_: tuple[float, float] = (), maxiter: int = 10000, bias_margin: float = _DEFAULT_BIAS_MARGIN, weigh_detours: bool = True, straight_feeder_route: bool = False, keep_log: bool = False, blockage_link_cos_lim: float = 0.85, blockage_link_feeder_lim: float = 2.0, blockage_subtree_feeder_lim: float = 2.5) → networkx.Graph[source]

Create a network using a constructive greedy heuristic.

The overall structure of the constructive algorithm is based on:

Esau, L. R., and K. C. Williams. “On Teleprocessing System Design,

Part II: A Method for Approximating the Optimal Network.” IBM Systems Journal 5, no. 3 (1966): 142–47. https://doi.org/10.1147/sj.53.0142.

However, this implementation uses the extended Delaunay triangulation (given in A) as the base connectivity, and implements terminal-terminal crossing prevention. This means that even the method named ‘esau_williams’ does not match exactly the paper’s description, but the similarities are still substantial.

Note that constructor cannot be constrained in the number of feeders and that only method ‘radial_EW’ is constrained to producing radial topologies (i.e. subtrees are always simple paths) as opposed to the branched topologies produced by the others.

Methods: - ‘esau_williams’: Esau-Williams C-MST heuristic modified to avoid crossings (EW). - ‘biased_EW’: EW with a bias towards moving radially (root-ward) on quasi-ties. - ‘rootlust’: EW with a tunable root-ward bias that increases as capacity decreases. - ‘radial_EW’: EW variant that produces radial subtrees (simple paths from root).

Parameters:

  • Aʹ – available links graph

  • capacity – max number of terminals in a subtree

  • method – choice of method (see Methods)

  • bias_margin – (biased_EW | radial_EW) fractional margin within with edges are equivalent

  • weigh_detours – (!= esau_williams) only add edges whose tradeoff is not outweighted by detours

  • straight_feeder_route – prevent crossings of feeders (incompatible with weigh_detours=True)

  • maxiter – fail-safe to avoid locking in an infinite loop

Returns:

Solution topology S.

optiwindnet.heuristics.CPEW(L: networkx.Graph, capacity: int, delaunay_based: bool = True, maxiter: int = 10000, weightfun: Callable | None = None, weight_attr: str = 'length') → networkx.Graph[source]

Crossing Preventing Esau-Williams heuristic for C-MST

Parameters:

  • L – location graph

  • capacity – max number of terminals in a subtree

  • maxiter – fail-safe to avoid locking in an infinite loop

Returns:

Routeset graph G

optiwindnet.heuristics.EW_presolver(Aʹ: networkx.Graph, capacity: int, maxiter: int = 10000, keep_log: bool = False) → networkx.Graph[source]

Modified Esau-Williams heuristic for C-MST with limited crossings

Parameters:

  • Aʹ – available links graph

  • capacity – max number of terminals in a subtree

  • maxiter – fail-safe to avoid locking in an infinite loop

Returns:

Solution topology S.

optiwindnet.heuristics.NBEW(L: networkx.Graph, capacity: int, delaunay_based: bool = True, rootlust: float = 0.0, maxiter: int = 10000, weightfun: Callable | None = None, weight_attr: str = 'length') → networkx.Graph[source]

Non-branching Esau-Williams heuristic for C-MST.

Parameters:

  • L – networkx.Graph

  • capacity – max number of terminals in a subtree

  • rootlust – weight of the reduction of subroot length in calculating savings (use some value between 0 and 1, e.g. 0.6)

Returns:

Routeset graph G

optiwindnet.heuristics.OBEW(L: networkx.Graph, capacity: int, rootlust: str | None = None, maxiter: int = 10000, maxDepth: int = 4, MARGIN: float = 0.0001, warnwhere: Callable | None = None, weightfun: Callable | None = None, keep_log: bool = False) → networkx.Graph[source]

Obstacle Bypassing Esau-Williams heuristic for C-MST.

Recommended rootlust: ‘0.6*cur_capacity/capacity’

Parameters:

  • L – location graph

  • capacity – max number of terminals in a subtree

  • rootlust – expression to use for biasing weights

  • warnwhere – print debug info based on utils.Alerter

Returns:

Routeset graph G