Minimum-Paths Minimum Discordant Nodes

This model optimizes the number of paths for the k-Minimum Discordant Nodes objective in DAGs. It wraps NumPathsOptimization with:

model_type = kMinDiscordantNodes
stop_on_delta_abs = 0

Thus, the routine iterates over increasing values of $k$ and stops when the objective value no longer improves in absolute value (plateau criterion).

1. Definition

Given a DAG with node flow values, this model returns a decomposition minimizing the number of discordant nodes while selecting $k$ automatically.

The search starts at $$ k_0 = \max\left(\text{min_num_paths},\ \text{lowerbound}(k)\right) $$ and increases $k$ until one of the stopping conditions in NumPathsOptimization is met.

2. Solving the problem

import flowpaths as fp
import networkx as nx

G = nx.DiGraph()
G.add_node("s", flow=5)
G.add_node("a", flow=10)
G.add_node("t", flow=5)
G.add_edge("s", "a")
G.add_edge("a", "t")

model = fp.MinPathsMinDiscordantNodes(
    G=G,
    flow_attr="flow",
    discordance_tolerance=0.1,
    min_num_paths=1,
    max_num_paths=10,
)
model.solve()

if model.is_solved():
    sol = model.get_solution(remove_empty_paths=True)
    print(model.model.k)  # selected k
    print(sol["paths"])
    print(sol["weights"])
    print(sol["discordant_nodes"])

Example search flow:

flowchart LR
    start([Start at k0]) --> solvek[Solve k-MinDiscordantNodes at k]
    solvek --> feasible{Solved?}
    feasible -- no --> nextk[Increase k]
    feasible -- yes --> plateau{Objective plateau?}
    plateau -- no --> nextk
    plateau -- yes --> stop([Return previous feasible model])
    nextk --> solvek

3. References

Jin Zhao, Haodi Feng, Daming Zhu, Yu Lin, MultiTrans: An Algorithm for Path Extraction Through Mixed Integer Linear Programming for Transcriptome Assembly, IEEE/ACM Transactions on Computational Biology and Bioinformatics 19(1), 48-56, 2022.
See also flowpaths References.

MinPathsMinDiscordantNodes

MinPathsMinDiscordantNodes(
    G: DiGraph,
    flow_attr: str,
    weight_type: type = float,
    discordance_tolerance: float = 0.1,
    subsequence_constraints: list = None,
    additional_starts: list = None,
    additional_ends: list = None,
    optimization_options: dict = None,
    solver_options: dict = None,
    round_flow_values_to_int: bool = True,
    flow_values_divisor: float = 1,
    min_num_paths: int = None,
    max_num_paths: int = 2
    ** 64,
    time_limit: float = float(
        "inf"
    ),
)

Bases: NumPathsOptimization

Minimize the number of paths for k-MinDiscordantNodes on DAG-like inputs.

The class wraps :class:NumPathsOptimization with: - model_type fixed to kMinDiscordantNodes - stop_on_delta_abs fixed to 0

This means the search over k stops at the first plateau, i.e. when the objective no longer improves in absolute value.

Multi-component behavior

If G has multiple weakly connected components, this class solves one component-local instance per component and merges the solutions. Constraints and optional start/end nodes are filtered per component. A single global time_limit is enforced across all component solves.

Build a MinPathsMinDiscordantNodes optimizer.

Parameters

G : nx.DiGraph Input graph. flow_attr : str Node/edge attribute name used by the wrapped discordance model. weight_type : type, default=float Type for path weights (typically int or float). discordance_tolerance : float, default=0.1 Relative tolerance used when deciding if a node is discordant. subsequence_constraints : list, optional List of node sequences that must be covered. In multi-component mode, each sequence must lie entirely inside one component. additional_starts : list, optional Optional allowed start nodes. Filtered per component in multi-component mode. additional_ends : list, optional Optional allowed end nodes. Filtered per component in multi-component mode. optimization_options : dict, optional Options forwarded to underlying models. solver_options : dict, optional Solver backend options (HiGHS/Gurobi wrapper options). flow_values_divisor : float, default=1 Divides node/edge flow values before solving. Division happens before optional rounding. min_num_paths : int, optional Lower bound for k. If None, a lower bound is computed via MinPathCover on a node-expanded graph (per component when componentized). max_num_paths : int, default=2**64 Upper bound for k. time_limit : float, default=inf Global time limit in seconds. For multi-component graphs, each component receives the remaining budget.