Load-Balancing Pricing Adapters

Load-balancing-specific pricing adapters.

asunder.load_balancing.column_generation.subproblem._balanced_fallback_partition(n_nodes, K)

Construct a deterministic near-equal partition.

Parameters:

  • n_nodes (int) – Number of nodes to assign.

  • K (int) – Number of requested parts.

Returns:

Binary co-association matrix produced by round-robin node assignment.

Return type:

numpy.ndarray

Raises:

ValueError – If K is not between one and n_nodes.

asunder.load_balancing.column_generation.subproblem._warn_about_ignored_internal_mass()

Warn that contracted diagonal mass is omitted from QMETIS search.

Return type:

None

asunder.load_balancing.column_generation.subproblem.qmetis_pricing_subproblem(A, a, m, duals, *, K, R, R_bounds=None, verbose=False, seed=None, **_)

Generate and exactly score a pricing candidate with QMETIS.

QMETIS receives a nonnegative approximation of the dual-adjusted pricing matrix. Its imbalance tolerance is derived only as a search envelope from the master’s permitted upper community-size bound. The candidate’s reduced cost is always recomputed with the original floating-point data.

Parameters:

  • A (numpy.ndarray) – Original or contracted adjacency matrix used by the exact pricing objective.

  • a (numpy.ndarray) – Degree/strength vector associated with A.

  • m (float) – Total directed graph weight used by Asunder’s modularity formula.

  • duals (dict[str, Any]) – Scalar, node-level, and pair-level master dual values.

  • K (int) – Requested number of load-balanced communities.

  • R (int) – Width of the permitted community-size range.

  • R_bounds (tuple[int or None, int or None] or None) – Optional explicit lower and upper community-size bounds.

  • verbose (int or bool, default=False) – Emit pricing diagnostics when enabled.

  • seed (int or None) – QMETIS random seed.

  • **_ (Any) – Ignored compatibility keywords from generic pricing dispatch.

Return type:

tuple[float, ndarray]

Returns:

  • reduced_cost (float) – Exact, unquantized reduced cost of the generated candidate.

  • partition (numpy.ndarray) – Binary co-association matrix generated by QMETIS or the deterministic edgeless fallback.

Warns:

QMETISApproximationWarning – If A has a nonzero diagonal. Contraction-generated internal mass is excluded from QMETIS candidate generation because its self-loop semantics are unsupported, but remains in exact rescoring.

Notes

Negative dual-adjusted edges are clipped to zero only for candidate generation. The clipping, integer quantization, and diagonal removal do not alter the exact reduced-cost calculation.