Skip to content

An Optimization Routine for the Number of Paths

Models implemented with the class AbstractPathModelDAG assume a fixed number k of paths. This class provides an automatic method of iterating in an increasing manner over values of k to find the best one (i.e., when a stopping criterion has been met).

For example, our custom class for the Minimum Flow Decomposition problem could be emulated in this manner:

mfd_model = fp.NumPathsOptimization(
        model_type = fp.kFlowDecomp,
        stop_on_first_feasible=True,
        G=graph, 
        flow_attr="flow",
        )

If you want to pass additional parameters to the model, you can just add append them, for example:

mfd_model = fp.NumPathsOptimization(
        model_type = fp.kFlowDecomp,
        stop_on_first_feasible=True,
        G=graph, 
        flow_attr="flow",
        subpath_constraints=[[("a", "c"),("c", "t")]], 
        subpath_constraints_coverage=0.5, 
        optimization_options={"optimize_with_greedy": False}
        )

NumPathsOptimization 

NumPathsOptimization(model_type: AbstractPathModelDAG, stop_on_first_feasible: bool = None, stop_on_delta_abs: float = None, stop_on_delta_rel: float = None, min_num_paths: int = 1, max_num_paths: int = 2 ** 64, time_limit: float = float('inf'), **kwargs)

Bases: AbstractPathModelDAG

This is a generic class to find the “best” number of paths optimization problems implemented using AbstractPathModelDAG, and which are parameterized by the number of paths to be considered. The class iterates over a range of path numbers, creating and
solving a model for each path number until one of the stopping conditions is met.

Parameters

  • model_type : AbstractPathModelDAG

    The type of the model used for optimization.

  • stop_on_first_feasible : bool, optional

    If True, the optimization process stops as soon as a feasible solution is found. Default is None.

  • stop_on_delta_abs : float, optional

    The threshold for change (in absolute value) in objective value between iterations to determine stopping the optimization. Default is None.

  • stop_on_delta_rel : float, optional

    The relative threshold for change (in absolute value) in objective value between iterations to determine stopping the optimization. This is computed as the difference in objective value between iterations divided by the objective value of the previous iteration. Default is None.

    Pass at least one stopping criterion

    At least one of the stopping criterion must be set: stop_on_first_feasible, stop_on_delta_abs, stop_on_delta_rel.

  • min_num_paths : int, optional

    Minimum number of paths to be considered in the optimization. Default is 1. The class will also call get_lowerbound_k() on the model_type and the provided arguments to get a better lower bound for the number of paths.

  • max_num_paths : int, optional

    Maximum number of paths to be computed. Default is 2**64.

  • time_limit : float, optional

    Time limit (in seconds) for the optimization process. Default is float("inf").

  • **kwargs

    The keyword arguments to be passed to the model.

    Note

    Do not pass the parameter k here, as it will be handled by the internal optimization process.

Raises

  • ValueError

    If none of the stopping criteria (stop_on_first_feasible, stop_on_delta_abs, or stop_on_delta_rel) is provided (i.e., all are None).

Source code in flowpaths/numpathsoptimization.py 
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 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
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
def __init__(
    self,
    model_type: pathmodel.AbstractPathModelDAG,
    stop_on_first_feasible: bool = None,
    stop_on_delta_abs: float = None,
    stop_on_delta_rel: float = None,
    min_num_paths: int = 1,
    max_num_paths: int = 2**64,
    time_limit: float = float("inf"),
    **kwargs,
):
    """
    This is a generic class to find the "best" number of paths optimization problems implemented using `AbstractPathModelDAG`,
    and which are parameterized by the number of paths to be considered.
    The class iterates over a range of path numbers, creating and  
    solving a model for each path number until one of the stopping conditions is met.

    Parameters
    ----------

    - `model_type : AbstractPathModelDAG`

        The type of the model used for optimization.

    - `stop_on_first_feasible : bool`, optional

        If True, the optimization process stops as soon as a feasible solution is found.
        Default is None.

    - `stop_on_delta_abs` : float, optional

        The threshold for change (in absolute value) in objective value between iterations to determine stopping the optimization.
        Default is `None`.

    - `stop_on_delta_rel` : float, optional

        The relative threshold for change (in absolute value) in objective value between iterations to determine stopping the optimization. 
        This is computed as the difference in objective value between iterations divided by the objective value of the previous iteration.
        Default is `None`.

        !!! warning "Pass at least one stopping criterion"
            At least one of the stopping criterion must be set: `stop_on_first_feasible`, `stop_on_delta_abs`, `stop_on_delta_rel`.

    - `min_num_paths : int`, optional

        Minimum number of paths to be considered in the optimization.
        Default is 1. The class will also call `get_lowerbound_k()` on the `model_type` and the provided arguments to get a better lower bound for the number of paths.

    - `max_num_paths : int`, optional

        Maximum number of paths to be computed.
        Default is `2**64`.

    - `time_limit : float`, optional

        Time limit (in seconds) for the optimization process.
        Default is `float("inf")`.

    - `**kwargs`

        The keyword arguments to be passed to the model. 

        !!! warning "Note"

            Do not pass the parameter `k` here, as it will be handled by the internal optimization process.

    Raises
    ------

    - `ValueError`

        If none of the stopping criteria (`stop_on_first_feasible`, `stop_on_delta_abs`, or
        `stop_on_delta_rel`) is provided (i.e., all are `None`).
    """

    self.model_type = model_type
    self.stop_on_first_feasible = stop_on_first_feasible
    self.stop_on_delta_abs = stop_on_delta_abs
    self.stop_on_delta_rel = stop_on_delta_rel
    self.min_num_paths = min_num_paths
    self.max_num_paths = max_num_paths
    self.time_limit = time_limit
    self.kwargs = kwargs

    # We allow only one of the stopping criteria to be set
    if (stop_on_first_feasible is None) and (stop_on_delta_abs is None) and (stop_on_delta_rel is None):
        raise ValueError(
            "At least one of the stopping criteria must be set: stop_on_first_feasible, stop_on_delta_abs, stop_on_delta_rel"
        )

    self.lowerbound_k = None
    self.__solution = None
    self.solve_statistics = None

get_objective_value 

get_objective_value()

Returns the objective value of the model, if it is solved. Otherwise, raises an exception.

Source code in flowpaths/numpathsoptimization.py 
215
216
217
218
219
220
221
222
223
def get_objective_value(self):
    """
    Returns the objective value of the model, if it is solved. Otherwise, raises an exception.
    """

    self.check_is_solved()

    # Number of paths
    return len(self.__solution["paths"])

get_solution 

get_solution()

Retrieves the solution for the flow decomposition problem.

Returns

  • solution: dict

    The solution obtained from the model

Raises
  • exception If model is not solved.
Source code in flowpaths/numpathsoptimization.py 
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
def get_solution(self):
    """
    Retrieves the solution for the flow decomposition problem.

    Returns
    -------

    - `solution: dict`

        The solution obtained from the model

    Raises
    -------

    - `exception` If model is not solved.
    """
    self.check_is_solved()
    return self.__solution

is_valid_solution 

is_valid_solution() -> bool

Checks if the solution is valid, by calling the is_valid_solution() method of the model.

Source code in flowpaths/numpathsoptimization.py 
225
226
227
228
229
def is_valid_solution(self) -> bool:
    """
    Checks if the solution is valid, by calling the `is_valid_solution()` method of the model.
    """
    return self.model.is_valid_solution()

solve 

solve() -> bool

Attempts to solve the optimization problem by iterating over a range of path counts, creating and solving a model for each count until one of the stopping conditions is met. The method iterates from the maximum between the minimum allowed paths and a computed lower bound (via get_lowerbound_k()) to the maximum allowed paths. For each iteration:

  • Creates a model instance with the current number of paths (k).
  • Solves the model.
  • Checks if the model has been successfully solved.

  • Applies various stopping criteria including:

    • stop_on_first_feasible: stops at the first feasible solution.
    • stop_on_delta_abs: stops if the absolute change in the objective value between iterations is less than or equal to a provided threshold.
    • stop_on_delta_rel: stops if the relative change in the objective value between iterations is less than or equal to a provided threshold.

  • Stops if the elapsed time exceeds the designated time limit.

Upon termination, the method sets the overall solve status:

  • If no feasible solution was found, the status is marked as infeasible.
  • If the process did not exceed the time limit but no other stopping condition was met, the status is marked as unbounded.
  • If any of the stopping criteria (feasible or delta conditions) were satisfied, the status is set as solved.

If a valid solution is found, it stores the solution, updates solve statistics and the model, marks the problem as solved, and returns True. Otherwise, it returns False.

Returns

  • bool

    True if an optimal solution is found and the problem is marked as solved, False otherwise.

Source code in flowpaths/numpathsoptimization.py 
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
def solve(self) -> bool:
    """
    Attempts to solve the optimization problem by iterating over a range of path counts, creating and
    solving a model for each count until one of the stopping conditions is met.
    The method iterates from the maximum between the minimum allowed paths and a computed lower bound (via
    get_lowerbound_k()) to the maximum allowed paths. For each iteration:

    - Creates a model instance with the current number of paths (k).
    - Solves the model.
    - Checks if the model has been successfully solved.
    - Applies various stopping criteria including:

        - stop_on_first_feasible: stops at the first feasible solution.
        - stop_on_delta_abs: stops if the absolute change in the objective value between iterations is
            less than or equal to a provided threshold.
        - stop_on_delta_rel: stops if the relative change in the objective value between iterations is
            less than or equal to a provided threshold.

    - Stops if the elapsed time exceeds the designated time limit.

    Upon termination, the method sets the overall solve status:

    - If no feasible solution was found, the status is marked as infeasible.
    - If the process did not exceed the time limit but no other stopping condition was met, the status
        is marked as unbounded.
    - If any of the stopping criteria (feasible or delta conditions) were satisfied, the status is set as solved.

    If a valid solution is found, it stores the solution, updates solve statistics and the model,
    marks the problem as solved, and returns True. Otherwise, it returns False.

    Returns
    -------

    - `bool`

        `True` if an optimal solution is found and the problem is marked as solved, `False` otherwise.

    """

    start_time = time.time()
    previous_solution_objective_value = None
    solve_status = None
    found_feasible = False

    for k in range(max(self.min_num_paths,self.get_lowerbound_k()), self.max_num_paths+1):
        print("num_paths", k)
        # Create the model
        model = self.model_type(**self.kwargs, k=k)
        print("model", model)
        model.solve()
        if model.is_solved():
            found_feasible = True
            if self.stop_on_first_feasible:
                solve_status = NumPathsOptimization.solved_status_name
                break
            if self.stop_on_delta_abs:
                if previous_solution_objective_value is None:
                    previous_solution_objective_value = model.get_objective_value()
                else:
                    if abs(previous_solution_objective_value - model.get_objective_value()) <= self.stop_on_delta_abs:
                        solve_status = NumPathsOptimization.solved_status_name
                        break
            if self.stop_on_delta_rel:
                if previous_solution_objective_value is None:
                    previous_solution_objective_value = model.get_objective_value()
                else:
                    if abs(previous_solution_objective_value - model.get_objective_value()) / previous_solution_objective_value <= self.stop_on_delta_rel:
                        solve_status = NumPathsOptimization.solved_status_name
                        break
        if time.time() - start_time > self.time_limit:
            solve_status = NumPathsOptimization.timeout_status_name
            break

    if solve_status != NumPathsOptimization.timeout_status_name:
        if not found_feasible:
            solve_status = NumPathsOptimization.infeasible_status_name
        elif solve_status is None:
            solve_status = NumPathsOptimization.unbounded_status_name

    self.solve_statistics = {
            "solve_status": solve_status,
            "solve_time": time.time() - start_time,
        }

    if solve_status == NumPathsOptimization.solved_status_name:
        self.__solution = model.get_solution()
        self.set_solved()
        self.solve_statistics.update(model.solve_statistics)
        self.model = model
        return True

    return False