netoptim_rs/
optscaling_oracle.rs

1use crate::network_oracle::{Cut, GradVec, NetworkOracle, OracleFn};
2use petgraph::graph::{DiGraph, EdgeReference};
3
4pub struct OptScalingOracle<'a, V, F>
5where
6    F: Fn(&EdgeReference<f64>) -> (f64, f64),
7{
8    network: NetworkOracle<'a, V, f64, Ratio<F>>,
9}
10
11struct Ratio<F> {
12    get_cost: F,
13}
14
15impl<F> Ratio<F> {
16    fn new(get_cost: F) -> Self {
17        Ratio { get_cost }
18    }
19}
20
21impl<F> OracleFn<f64> for Ratio<F>
22where
23    F: Fn(&EdgeReference<f64>) -> (f64, f64),
24{
25    type X = GradVec;
26
27    fn eval(&self, edge: &EdgeReference<f64>, x: &GradVec) -> f64 {
28        let (aij, aji) = (self.get_cost)(edge);
29        f64::min(x.0[0] - aji, aij - x.0[1])
30    }
31
32    fn grad(&self, edge: &EdgeReference<f64>, x: &GradVec) -> GradVec {
33        let (aij, aji) = (self.get_cost)(edge);
34        if x.0[0] - aji < aij - x.0[1] {
35            GradVec(vec![1.0, 0.0])
36        } else {
37            GradVec(vec![0.0, -1.0])
38        }
39    }
40}
41
42impl<'a, V, F> OptScalingOracle<'a, V, F>
43where
44    F: Fn(&EdgeReference<f64>) -> (f64, f64),
45{
46    pub fn new(gra: &'a DiGraph<V, f64>, potential: Vec<f64>, get_cost: F) -> Self {
47        let ratio = Ratio::new(get_cost);
48        let network = NetworkOracle::new(gra, potential, ratio);
49        OptScalingOracle { network }
50    }
51
52    pub fn assess_optim(&mut self, x: &[f64; 2], gamma: &mut f64) -> (Cut<GradVec>, bool) {
53        let cut = self.network.assess_feas(&GradVec(x.to_vec()));
54        if let Some(c) = cut {
55            return (c, false);
56        }
57        let s = x[0] - x[1];
58        let fj = s - *gamma;
59        if fj < 0.0 {
60            *gamma = s;
61            return ((GradVec(vec![1.0, -1.0]), 0.0), true);
62        }
63        ((GradVec(vec![1.0, -1.0]), fj), false)
64    }
65}
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70    use petgraph::graph::DiGraph;
71
72    #[test]
73    fn test_optscaling_oracle_improves() {
74        let gra = DiGraph::<(), f64>::from_edges([(0, 1, 1.0), (1, 0, 1.0)]);
75        let potential = vec![0.0, 0.0];
76        let get_cost = |_edge: &EdgeReference<f64>| (1.0, 1.0);
77        let mut oracle = OptScalingOracle::new(&gra, potential, get_cost);
78        let x = [2.0, 0.0]; // pi=2, psi=0 → s=2, with gamma=3, fj=-1 < 0 → update
79        let mut gamma = 3.0;
80        let (_cut, updated) = oracle.assess_optim(&x, &mut gamma);
81        assert!(updated);
82        assert_eq!(gamma, 2.0);
83    }
84
85    #[test]
86    fn test_optscaling_oracle_infeasible() {
87        let gra = DiGraph::<(), f64>::from_edges([(0, 1, 1.0), (1, 0, 1.0)]);
88        let potential = vec![0.0, 0.0];
89        let get_cost = |_edge: &EdgeReference<f64>| (1.0, 1.0);
90        let mut oracle = OptScalingOracle::new(&gra, potential, get_cost);
91        let x = [0.0, 0.0]; // pi=0, psi=0 → infeasible (negative cycle)
92        let mut gamma = 0.0;
93        let (_cut, updated) = oracle.assess_optim(&x, &mut gamma);
94        assert!(!updated); // infeasible → no gamma update
95    }
96}
netoptim_rs/optscaling_oracle.rs

netoptim_rs/
optscaling_oracle.rs
