Decomposition

Column generation decomposition orchestration.

asunder.base.column_generation.decomposition.CSD_decomposition(A, a, m, mp_function, sp_function, columns=None, f_stars=None, must_link=[], cannot_link=[], additional_constraints=None, contract_graph=False, stopping_window=5, check_flat_pricing=True, algo='louvain', package='sknetwork', seed=42, extract_dual=False, ifc_params={}, refine_in_subproblem=False, refine_params={}, use_refined_column=False, final_master_solve=True, max_iterations=1000, disable_tqdm=False, tolerance=1e-10, verbose=False)

Function that does column generation (CG) and refinement given a master and subproblem function.

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.

  • mp_function (callable) – Master problem function (Handles ILP and LP versions).

  • sp_function (callable) – Pricing subproblem which can be implemented as a ILP or a heuristic (custom / third-party) subproblem.

  • columns (list[ndarray of int] or None) – Existing columns. This parameter is typically active during Branch and Price.

  • f_stars (list[float] or None) – Objective values of the existing columns. This parameter is typically active during Branch and Price.

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

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

  • additional_constraints (dict[str, Any]) – Constraints beyond must- and cannot-links. For example, worthy edges (edges that can connect communities), community size, and balance constraints.

  • contract_graph (bool) – Boolean that determines whether must links are handled via graph contraction or not.

  • stopping_window (int) – Maximum number of allowed stangnant CG iterations. After this, CG is terminated.

  • check_flat_pricing (bool) – Boolean that determines whether to check for flat/stagnant pricing or not.

  • algo (str) –

    Name of heuristic subproblem used to replace the ILP subproblem. Third-party algorithms combine adjacency and dual information intro a unified input while custom algorithms treat adjacency and duals as separate inputs. Supported third-party algorithms are listed under the package parameter. Available custom algorithm options include:

    "spectral":

    Modified iterative bisection algorithm based on Mark Newman’s eigenvector-based method.

    "full_louvain":

    Modified but Louvain-like algorithm.

    "RCCS":

    This means Reduced Cost Community Search and is a greedy and local search heuristic for finding commiunities that maximize the reduced cost.

  • package (str or None) –

    Package from which non-custom heuristic subproblem is selected. Package and algorithm options include:

    "networkx":

    "louvain", "greedy", "girvan_newman"

    "sknetwork":

    "louvain", "leiden", "lpa"

    "igraph":

    "leiden", "greedy", "infomap", "lpa", "multilevel", "voronoi", "walktrap"

    leidenalg:

    "leiden"

    None:

    "signed_louvain", "spinglass"

  • seed (int or None) – Random seed value.

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

  • ifc_params (dict[str, callable or dict or int]) – Number of initial feasible columns (ifc), initial feasible column generator, and its corresponding arguments (excluding seed values).

  • refine_in_subproblem (bool) – Boolean value that determines whether a refinement operation is run in the subproblem.

  • refine_params (dict[str, callable or dict]) – Refinement function and its corresponding arguments (excluding seed values).

  • use_refined_column (bool) – Boolean that determines whether refined columns are used in the main column generation loop or not.

  • final_master_solve (bool) – Boolean that determines whether a final master solve is executed or not.

  • max_iterations (int) – Maximum number of column generation iterations.

  • disable_tqdm (bool) – Whether to disable the progress bar or not.

  • tolerance (float) – Tolerance value for terminating column generation.

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

Returns:

results – Column-generation iteration records. Each dictionary may include lambda_sol, dual terms, master_obj_val, z_sol, sub_obj_val, columns, f_stars, and heuristic_col.

Return type:

list[dict]