Skip to content

See also

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

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

  2. See also flowpaths References.

MinPathsMinDiscordantNodes 

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

Bases: NumPathsOptimization

Find a minimum number of paths for k-MinDiscordantNodes by iterating over k.

This class is a thin wrapper around NumPathsOptimization with: - model_type fixed to kMinDiscordantNodes - stop_on_delta_abs fixed to 0

Therefore, the search stops at the first k where the objective value does not improve in absolute value compared to the reference used by NumPathsOptimization.

Source code in flowpaths/minpathsmindiscordantnodes.py 
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def __init__(
    self,
    G: nx.DiGraph,
    flow_attr: str,
    weight_type: type = float,
    discordance_tolerance: float = 0.1,
    subpath_constraints: list = None,
    additional_starts: list = None,
    additional_ends: list = None,
    optimization_options: dict = None,
    solver_options: dict = None,
    min_num_paths: int = 1,
    max_num_paths: int = 2**64,
    time_limit: float = float("inf"),
):
    super().__init__(
        model_type=kmindiscordantnodes.kMinDiscordantNodes,
        stop_on_delta_abs=0,
        min_num_paths=min_num_paths,
        max_num_paths=max_num_paths,
        time_limit=time_limit,
        G=G,
        flow_attr=flow_attr,
        weight_type=weight_type,
        discordance_tolerance=discordance_tolerance,
        subpath_constraints=subpath_constraints or [],
        additional_starts=additional_starts or [],
        additional_ends=additional_ends or [],
        optimization_options=optimization_options,
        solver_options=solver_options or {},
    )