digraphx/min_parametric_q.hpp file

Minimum parametric network problem solver with constraints.

This module provides algorithms for solving constrained parametric network optimization problems. It extends the basic parametric solver to support constraint handling and both predecessor/successor-based algorithms.

Problem formulation:

min  r
s.t. dist[v] - dist[u] <= distance(e, r)
     forall e(u, v) in G(V, E)
     subject to update constraints

Key features:

  • Support for distance update constraints
  • Both predecessor and successor algorithm variants
  • Flexible callback-based constraint handling
  • Early termination options for optimization
  • Abstract API interface for extensibility

Constraint types:

  • Upper/lower bounds on distance updates
  • Step size limitations
  • Domain-specific validation rules
  • Custom feasibility conditions

Example constrained parametric problem:

   a ----d(5,r)----> b
   |                |
   |d(2,r)    d(3,r)|
   |                |
   v      c(1)      v
   d ----d(4,r)----> e

Where d(i,r) represents distance depending on parameter r
and c(1) represents a constraint on updates

Algorithm variants:

  • Predecessor-based: Traditional forward relaxation
  • Successor-based: Reverse relaxation for different constraint types
  • Alternating: Switches between both for robustness

Performance characteristics:

  • Time complexity depends on constraint restrictiveness
  • Space complexity: O(V + E) for mappings
  • Constraints can significantly improve convergence

Classes

template<typename DiGraph, typename Ratio, typename Domain>
class MinParametricSolver
Minimum Parametric Solver with constraint support.

Functions

template<typename DiGraph, typename Ratio, typename Fn1, typename Fn2, typename Mapping, typename Domain>
auto min_parametric(const DiGraph& digraph, Ratio ratio, Fn1&& distance, Fn2&& zero_cancel, Mapping& dist, Domain domain, bool pick_one_only = false) -> std::pair< Ratio, std::vector< typename MinParametricSolver< DiGraph, Ratio, Domain >::Edge > > -> auto
Free function for constrained minimum parametric problems.

Function documentation

template<typename DiGraph, typename Ratio, typename Fn1, typename Fn2, typename Mapping, typename Domain>
auto min_parametric(const DiGraph& digraph, Ratio ratio, Fn1&& distance, Fn2&& zero_cancel, Mapping& dist, Domain domain, bool pick_one_only = false) -> std::pair< Ratio, std::vector< typename MinParametricSolver< DiGraph, Ratio, Domain >::Edge > >

Free function for constrained minimum parametric problems.

Template parameters
DiGraph Type of the directed graph representation
Ratio Type representing the parameter value
Fn1 Type of distance calculation function
Fn2 Type of zero cancellation function
Mapping Type of distance mapping (node -> distance)
Domain Type of the domain for distance calculations
Parameters
digraph in The directed graph to analyze
ratio in Initial parameter value for optimization
distance in Function calculating edge distance as function of r
zero_cancel in Function calculating parameter from a cycle
dist in/out Distance mapping updated during execution
domain in Type deduction parameter for distance domain
pick_one_only in If true, stop after first improving cycle
Returns std::pair<Ratio, std::vector<typename MinParametricSolver<DiGraph, Ratio, Domain>::Edge>> Optimal parameter and critical cycle

This function provides a functional interface for solving constrained parametric network problems without requiring class instantiation. It combines the flexibility of callback-based programming with sophisticated constraint handling.

Problem formulation:

min  r
s.t. dist[v] - dist[u] <= distance(e, r)
     forall e(u, v) in G(V, E)
     subject to update_ok(old_dist, new_dist) == true

Algorithm features:

  • Alternating predecessor/successor search strategy
  • Constraint-aware relaxation through update_ok callback
  • Early termination option for faster convergence
  • Memory-efficient cycle enumeration

Usage patterns:

  1. Basic constrained optimization:

    auto distance = [](double r, const Edge& e) { return e.cost - r * e.time; };
auto zero_cancel = [](const Cycle& c) { return calculate_ratio(c); };
auto update_ok = [](double old, double new) { return new < old; };

auto [ratio, cycle] = min_parametric(graph, r0, distance, zero_cancel, dist, 0.0);

  2. Step-size limited optimization:

    auto update_ok = [max_step](double old, double new) {
    return std::abs(new - old) <= max_step;
};

  3. Threshold-based improvements:

    auto update_ok = [min_improvement](double old, double new) {
    return old - new >= min_improvement;
};

Return value:

  • First element: Optimal parameter value found
  • Second element: Critical cycle achieving this value (empty if none)