Master Problem

Master problem and score utilities for CSD decomposition.

asunder.base.column_generation.master._require_pyomo()

Internal helper for the require pyomo check.

Raises:

ImportError – If Pyomo is not importable in the current environment.

asunder.base.column_generation.master.compute_f_star(A, a, m, z, gamma=1.0)

Compute column/partiton score used by the restricted master objective.

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 (ndarray of int | float, shape (N, N)) – Graph partition.

  • gamma (float) – Resolution parameter.

Returns:

metric – Modularity score.

Return type:

float

asunder.base.column_generation.master.solve_master_problem(A, a, m, Z_star, f_stars, cannot_link=None, must_link=None, worthy_edges=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.

  • 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.

  • worthy_edges (list[tuple[int, int]] or None) – List of edges that are allowed to connect different communities

  • 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.