|
| | NetworkOracle (const Graph &gra, Mapping &utx, Fn h) |
| | Construct a new network oracle object.
|
| |
| | NetworkOracle (const NetworkOracle &)=default |
| | Copy constructor.
|
| |
| template<typename Num > |
| auto | update (const Num &gamma) -> void |
| | Update the oracle with a new parameter value.
|
| |
| template<typename Arr > |
| auto | assess_feas (const Arr &xval) -> std::optional< std::pair< Arr, double > > |
| | Assess feasibility and generate cutting plane if needed.
|
| |
| template<typename Arr > |
| auto | operator() (const Arr &xvar) -> std::optional< std::pair< Arr, double > > |
| | Function call operator for cutting plane methods.
|
| |
template<typename Graph, typename Mapping, typename Fn>
requires HasKeyType<Graph>
class NetworkOracle< Graph, Mapping, Fn >
Oracle for Parametric Network Problems.
This class implements a separation oracle for network feasibility problems. It uses Howard's method for negative cycle detection to check feasibility and generate cutting planes when violations are found.
The oracle maintains:
- A reference to the graph structure
- A mapping of vertex potentials (utx)
- A negative cycle finder for violation detection
- A function h that evaluates edge constraints
- Template Parameters
-
| Graph | Type of the directed graph |
| Mapping | Type of vertex potential mapping |
| Fn | Type of the constraint function h, providing eval(edge, x) and grad(edge, x) methods operating on the graph's native edge data |
template<typename Graph , typename Mapping , typename Fn >
template<typename Arr >
| auto NetworkOracle< Graph, Mapping, Fn >::assess_feas |
( |
const Arr & |
xval | ) |
-> std::optional<std::pair<Arr, double>> |
|
inline |
Assess feasibility and generate cutting plane if needed.
This is the main oracle method that checks if the current point xval is feasible with respect to the network constraints. Uses Howard's method for negative cycle detection operating on the graph's native edge data. If infeasible, returns a cutting plane (gradient and function value) that separates the infeasible point from the feasible region.
The oracle solves the feasibility problem:
\[
\text{find } x, u \quad \text{s.t.} \quad u_j - u_i \le h(\text{edge}_{ij}, x) \; \forall
(i, j) \in E
\]
If infeasible, it returns a cutting plane \((g, f)\) from a violating cycle \(C\):
\[
g = -\sum_{e \in C} \nabla h(e, x), \quad f = -\sum_{e \in C} h(e, x)
\]
- Template Parameters
-
| Arr | Type of the input array/vector |
- Parameters
-
| [in] | xval | input values to be assessed for feasibility |
- Returns
- Empty if feasible, otherwise a pair containing gradient and function value
template<typename Graph , typename Mapping , typename Fn >
template<typename Num >
| auto NetworkOracle< Graph, Mapping, Fn >::update |
( |
const Num & |
gamma | ) |
-> void |
|
inline |
Update the oracle with a new parameter value.
Updates the internal constraint function with a new parameter value, typically used in parametric optimization where the constraints depend on a parameter that changes during the algorithm.
- Parameters
-
| [in] | gamma | the new parameter value (best-so-far optimal value) |
