Load Balancing Master Problem

Master problem and score utilities for CSD decomposition.

asunder.load_balancing.column_generation.master.solve_master_problem(A, a, m, Z_star, f_stars, LB=True, R=1, K=2, R_bounds=None, cannot_link=None, must_link=None, extract_dual=False, verbose=False, solver=None)

Solve the restricted master problem for the current column pool.

Parameters:

  • A (np.ndarray of int | float, shape (N, N)) – Adjacency / weight matrix.

  • a (np.ndarray of int | float, shape (N,)) – Degree-like vector; defaults to row sums of the symmetrized adjacency.

  • m (float) – Twice the total weight in the graph.

  • Z_star (list[ndarray of int]) – List of columns.

  • f_stars (list[float]) – Objective values computed using the existing columns.

  • LB (bool) – Whether load balancing constraints are activated or not.

  • R (int) – Width of the allowed cluster-size range. Also corresponds to the load balance tightness (smaller R implies tighter load balance). For a selected cluster count, the lower and upper bounds are computed from the corresponding balanced range rule.

  • K (int | None) – Number of communities.

  • R_bounds (tuple[int, int] | None) – Minimum and maximum number of nodes per community (community size constraint).

  • cannot_link (list[tuple[int, int]] or None) – List of node pairs that must not be together.

  • must_link (list[tuple[int, int]] or None) – List of node pairs that must be together.

  • extract_dual (bool) – Boolean that determines whether we extract duals from the master problem or not.

  • verbose (int or bool) – Controls the level of detail in the printed output. -1: No output False | 0: Minimal output True | 1: Detailed output

  • solver (Any) – Solver object.

Returns:

  • lambda_sol (list or ndarray of float) – A list/vector which sums to 1 that indicates what weight is assigned to each column (and by implication, what columns are active).

  • duals (dict[str, ndarray or float]) – Dual values computed from the master problem. This could be a 1D array, 2D array or a float.

  • master_obj_val (float) – The objective value of the master problem.