#include <digraphx/min_parametric_q.hpp>

template<typename DiGraph, typename Ratio, typename Domain>

MinParametricSolver class

Minimum Parametric Solver with constraint support.

This class implements algorithms for solving constrained parametric network optimization problems. It extends the basic parametric solver by incorporating constraint handling through callback functions and providing both predecessor and successor-based algorithm variants.

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 approach:

1. Initialize with starting parameter value
2. Use constrained negative cycle detection
3. Apply update constraints during relaxation
4. Adjust parameter based on violating cycles
5. Alternate between predecessor/successor methods

Key innovations:

• Constraint-aware relaxation: Updates validated by callback
• Dual algorithm support: Both forward and reverse relaxation
• Alternating strategy: Improves robustness and convergence
• Early termination: Option to stop after first improvement

Constraint handling: The UpdateOk callback enables sophisticated constraint strategies:

// Example: Only allow significant improvements
auto update_ok = [](double old_val, double new_val) {
    return new_val < old_val - 0.01;  // Minimum improvement threshold
};

// Example: Bounded updates
auto update_ok = [](double old_val, double new_val) {
    return std::abs(new_val - old_val) <= max_step_size;
};

Use cases:

• Resource allocation with capacity constraints
• Economic equilibrium with market frictions
• Network optimization with budget limitations
• Scheduling with time window constraints