Top-Level API

Package Entry Points

Asunder Package

Asunder: Constrained structure detection on undirected graphs.

The top-level package re-exports the most common entry points for convenience. Canonical API documentation is provided on the module pages below to avoid duplicate object targets for the same symbols.

Common package-level imports

  • asunder.run_csd_decomposition

  • asunder.solve_master_problem

  • asunder.solve_subproblem

  • asunder.run_evaluation

  • asunder.create_solver

  • asunder.CSDDecomposition

  • asunder.CSDDecompositionConfig

  • asunder.IterationRecord

  • asunder.DecompositionResult

Application package imports

  • asunder.load_balancing.LoadBalancer for the built-in load-balanced graph partitioning workflow

  • asunder.nlbnp.CorePeripheryPartition for component-level NLBNP partitioning after core removal

  • asunder.nlbnp.NonlinearBranchAndPrice for generic nonlinear branch-and-price runs on user-provided graphs

  • asunder.nlbnp.run_evaluation for the built-in nonlinear branch-and-price case-study evaluation workflow

Configuration

Configuration dataclasses.

class asunder.config.CSDDecompositionConfig(columns=None, f_stars=None, must_link=<factory>, cannot_link=<factory>, additional_constraints=<factory>, contract_graph=False, stopping_window=5, check_flat_pricing=True, algo='louvain', package='sknetwork', seed=42, extract_dual=False, ifc_params=<factory>, refine_in_subproblem=False, refine_params=<factory>, use_refined_column=False, final_master_solve=True, max_iterations=1000, disable_tqdm=False, tolerance=1e-10, verbose=1)

Bases: object

Configuration container for asunder.orchestrator.CSDDecomposition.

Parameters:

  • columns (list | None)

  • f_stars (list | None)

  • must_link (list)

  • cannot_link (list)

  • additional_constraints (Dict[str, Any])

  • contract_graph (bool)

  • stopping_window (int)

  • check_flat_pricing (bool)

  • algo (str)

  • package (str)

  • seed (int | None)

  • extract_dual (bool)

  • ifc_params (Dict[str, Any])

  • refine_in_subproblem (bool)

  • refine_params (Dict[str, Any])

  • use_refined_column (bool)

  • final_master_solve (bool)

  • max_iterations (int | None)

  • disable_tqdm (bool)

  • tolerance (float)

  • verbose (int | bool)

columns

Existing columns. This parameter is typically active during Branch and Price.

Type:

list[ndarray of int] or None

f_stars

Objective values of the existing columns. This parameter is typically active during Branch and Price.

Type:

list[float] or None

List of node pairs that must be together.

Type:

list[tuple[int, int]]

List of node pairs that must not be together.

Type:

list[tuple[int, int]]

additional_constraints

Constraints beyond must- and cannot-links. For example, worthy edges (edges that can connect communities), community size, and balance constraints.

Type:

dict[str, Any]

contract_graph

Boolean that determines whether must links are handled via graph contraction or not.

Type:

bool

stopping_window

Maximum number of allowed stangnant CG iterations. After this, CG is terminated.

Type:

int

check_flat_pricing

Boolean that determines whether to check for flat/stagnant pricing or not.

Type:

bool

algo

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.

Type:

str

package

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"

Type:

str or None

seed

Random seed value.

Type:

int or None

extract_dual

Boolean that determines whether we extract duals from the master problem or not.

Type:

bool

ifc_params

Number of initial feasible columns (ifc), initial feasible column generator, and its corresponding arguments.

Type:

dict[str, callable or dict or int]

refine_in_subproblem

Boolean value that determines whether a refinement operation is run in the subproblem.

Type:

bool

refine_params

Refinement function and its corresponding arguments.

Type:

dict[str, callable or dict]

use_refined_column

Boolean that determines whether refined columns are used in the main column generation loop or not.

Type:

bool

final_master_solve

Boolean that determines whether a final master solve is executed or not.

Type:

bool

max_iterations

Maximum number of column generation iterations.

Type:

int

disable_tqdm

Whether to disable the progress bar or not.

Type:

bool

tolerance

Tolerance value for terminating column generation.

Type:

float

verbose

Controls the level of detail in the printed output. -1: No output False | 0: Minimal output True | 1: Detailed output

Type:

int or bool

Orchestrator

High-level decomposition orchestrator.

class asunder.orchestrator.CSDDecomposition(config=None, master_fn=<function solve_master_problem>, subproblem_fn=<function heuristic_subproblem>)

Bases: object

High-level driver that wires configuration to master/subproblem hooks.

Parameters:
run(A, a=None, m=None, **overrides)

Execute decomposition and return typed iteration records.

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.

  • **overrides (Any) – Additional keyword arguments.

Returns:

Computed decomposition result object.

Return type:

DecompositionResult

asunder.orchestrator.run_csd_decomposition(A, a=None, m=None, config=None, master_fn=<function solve_master_problem>, subproblem_fn=<function heuristic_subproblem>, **kwargs)

Convenience wrapper for one-shot decomposition runs.

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.

  • config (CSDDecompositionConfig | None) – Column generation configuration.

  • master_fn (MasterProblemFn) – Master problem function.

  • subproblem_fn (SubproblemFn) – Subproblem function.

  • **kwargs (Any) – Additional keyword arguments.

Returns:

Computed decomposition result object.

Return type:

DecompositionResult

Solvers

Solver factory helpers.

asunder.solvers.create_solver(solver_name='gurobi_direct', **solver_kwargs)

Create a pyomo solver instance.

Parameters:

  • solver_name (str) – Name of solver.

  • **solver_kwargs (Any) – Additional keyword arguments.

Returns:

Solver object.

Return type:

Any

asunder.solvers.set_default_solver(solver)

Set the process-wide default solver instance used by Asunder.

Parameters:

solver (Any) – Solver object.

Return type:

None

asunder.solvers.get_default_solver()

Return the configured default solver, creating one lazily if needed.

Returns:

Solver object.

Return type:

Any

Types

Core types and protocols for Asunder.

class asunder.types.MasterProblemFn(*args, **kwargs)

Bases: Protocol

Protocol for master-problem solvers used in decomposition loops.

Notes

Implementations are expected to accept the current column pool and return either an integer-master solution tuple or an LP-with-duals tuple, depending on whether dual extraction is enabled.

class asunder.types.SubproblemFn(*args, **kwargs)

Bases: Protocol

Protocol for pricing/subproblem solvers used in decomposition loops.

Notes

Implementations are expected to solve or approximate the pricing problem and return (sub_obj_val, z_sol).

class asunder.types.IterationRecord(lambda_sol, duals=<factory>, master_obj_val=None, z_sol=None, heuristic_col=None, sub_obj_val=None, columns=<factory>, f_stars=<factory>)

Bases: object

Structured record for one decomposition iteration.

Parameters:

  • lambda_sol (List[float] | None)

  • duals (Dict[str, Any])

  • master_obj_val (float | None)

  • z_sol (ndarray | None)

  • heuristic_col (ndarray | None)

  • sub_obj_val (float | None)

  • columns (List[ndarray])

  • f_stars (List[float])

lambda_sol

A list/vector which sums to 1 that indicates what weight is assigned to each column (and by implication, what columns are active).

Type:

list[float] or ndarray[float]

duals

The dual terms corresponding to a constraint in the relaxed master problem. This could be a 2D array, 1D array or a float.

Type:

Dict[str, ndarray[float] or float]

master_obj_val

The objective value of the master problem.

Type:

float

z_sol

The most recently generated column from the subproblem.

Type:

ndarray[int], shape (N, N)

heuristic_col

Refined column generated using local search that is initialized with z_sol or the convex combinations of all columns.

Type:

ndarray[int], shape (N, N)

sub_obj_val

The reduced cost of the current column.

Type:

float

columns

All columns under consideration for the next iteration. The most recently generated column is at index -1.

Type:

list[ndarray]

f_stars

List of objective values computed using each column in columns.

Type:

list[float]

class asunder.types.DecompositionResult(records, final_partition, final_master_obj, metadata=<factory>)

Bases: object

Container for full decomposition output and summary metadata.

Parameters:

  • records (List[IterationRecord])

  • final_partition (ndarray | None)

  • final_master_obj (float | None)

  • metadata (Dict[str, Any])

records

Column generation iteration records.

Type:

List[IterationRecord]

final_partition

Partition matrix.

Type:

Optional[np.ndarray]

final_master_obj

Final master problem objective.

Type:

Optional[float]

metadata

Decomposition metadata.

Type:

Dict[str, Any]