fieldopt-core 0.2.3

Field-survey design under real field cost: travel matrices, GRASP routing of field work (TSP/VRP), spatially balanced sampling (local pivotal method), Horvitz-Thompson estimation with local-mean variance, and cost-aware allocation. Pure Rust, no dependencies.
Documentation
//! Cost-aware allocation across strata (or frames treated as strata).
//!
//! Minimises the field cost `sum_h c_h n_h` subject to a target variance of
//! the estimated total under stratified sampling,
//! `sum_h N_h^2 S_h^2 / n_h - sum_h N_h S_h^2 = V0`, or minimises the variance
//! subject to a cost budget. The solution is the classical optimum
//! `n_h proportional to N_h S_h / sqrt(c_h)` (Cochran, 1977, Section 5.5),
//! scaled to meet the constraint, then bounded to `[2, N_h]`. Bounding makes
//! the result approximate when a bound is active; the function reports the
//! variance and cost actually attained.

/// One stratum of the allocation problem.
#[derive(Clone, Copy, Debug)]
pub struct Stratum {
    /// Number of population units.
    pub size: usize,
    /// Standard deviation of the study variable within the stratum.
    pub sd: f64,
    /// Cost of one unit (interview plus expected access cost).
    pub cost: f64,
}

/// An allocation and what it attains.
#[derive(Clone, Debug, PartialEq)]
pub struct Allocation {
    /// Sample size per stratum.
    pub n: Vec<usize>,
    /// Total cost `sum c_h n_h`.
    pub cost: f64,
    /// Variance of the estimated total attained.
    pub variance: f64,
    /// Whether a bound (`2 <= n_h <= N_h`) was active.
    pub bounded: bool,
}

fn validate(strata: &[Stratum]) -> Result<(), String> {
    if strata.is_empty() {
        return Err("at least one stratum is needed".into());
    }
    for (h, s) in strata.iter().enumerate() {
        if s.size < 2 {
            return Err(format!("stratum {h} has fewer than two units"));
        }
        if !s.sd.is_finite() || s.sd < 0.0 {
            return Err(format!("stratum {h} has an invalid standard deviation"));
        }
        if !s.cost.is_finite() || s.cost <= 0.0 {
            return Err(format!("stratum {h} must have a positive cost"));
        }
    }
    Ok(())
}

fn variance_of(strata: &[Stratum], n: &[usize]) -> f64 {
    strata
        .iter()
        .zip(n)
        .map(|(s, &nh)| {
            let big_n = s.size as f64;
            big_n * big_n * s.sd * s.sd / nh as f64 * (1.0 - nh as f64 / big_n)
        })
        .sum()
}

fn finish(strata: &[Stratum], raw: &[f64]) -> Allocation {
    let mut bounded = false;
    let n: Vec<usize> = strata
        .iter()
        .zip(raw)
        .map(|(s, &r)| {
            let up = (r - 1e-9).ceil();
            let v = up.max(2.0).min(s.size as f64);
            if (v - up).abs() > 1e-9 {
                bounded = true;
            }
            v as usize
        })
        .collect();
    let cost = strata
        .iter()
        .zip(&n)
        .map(|(s, &nh)| s.cost * nh as f64)
        .sum();
    Allocation {
        variance: variance_of(strata, &n),
        cost,
        n,
        bounded,
    }
}

/// Allocation that minimises cost subject to variance at most `target_variance`.
pub fn allocate_for_variance(
    strata: &[Stratum],
    target_variance: f64,
) -> Result<Allocation, String> {
    validate(strata)?;
    if !target_variance.is_finite() || target_variance <= 0.0 {
        return Err("the target variance must be positive".into());
    }
    // Strata whose unrounded optimum exceeds their size are taken completely
    // (they then contribute no variance) and the rest is re-solved for the
    // same target, until no new stratum hits its size.
    let h = strata.len();
    let mut full = vec![false; h];
    let mut raw = vec![0.0; h];
    loop {
        let a: f64 = (0..h)
            .filter(|&i| !full[i])
            .map(|i| strata[i].size as f64 * strata[i].sd * strata[i].cost.sqrt())
            .sum();
        let b: f64 = (0..h)
            .filter(|&i| !full[i])
            .map(|i| strata[i].size as f64 * strata[i].sd * strata[i].sd)
            .sum();
        let denom = target_variance + b;
        let mut new_full = false;
        for i in 0..h {
            if full[i] {
                raw[i] = strata[i].size as f64;
                continue;
            }
            raw[i] = strata[i].size as f64 * strata[i].sd / strata[i].cost.sqrt() * a / denom;
            if raw[i] >= strata[i].size as f64 {
                full[i] = true;
                new_full = true;
            }
        }
        if !new_full {
            break;
        }
    }
    let mut out = finish(strata, &raw);
    out.bounded = out.bounded || full.iter().any(|&f| f);
    Ok(out)
}

pub fn allocate_for_budget(strata: &[Stratum], budget: f64) -> Result<Allocation, String> {
    validate(strata)?;
    if !budget.is_finite() || budget <= 0.0 {
        return Err("the budget must be positive".into());
    }
    let h = strata.len();
    let a_all: f64 = strata
        .iter()
        .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
        .sum();
    if a_all <= 0.0 {
        return Err("every stratum has zero standard deviation; nothing to allocate".into());
    }
    // Strata whose optimum exceeds their size are taken completely; their
    // cost is removed from the budget and the rest is re-solved.
    let mut full = vec![false; h];
    let mut raw = vec![0.0; h];
    loop {
        let spent: f64 = (0..h)
            .filter(|&i| full[i])
            .map(|i| strata[i].cost * strata[i].size as f64)
            .sum();
        let left = budget - spent;
        if left <= 0.0 {
            return Err(
                "the budget does not cover the strata that must be taken completely".into(),
            );
        }
        let a: f64 = (0..h)
            .filter(|&i| !full[i])
            .map(|i| strata[i].size as f64 * strata[i].sd * strata[i].cost.sqrt())
            .sum();
        let mut new_full = false;
        for i in 0..h {
            if full[i] {
                raw[i] = strata[i].size as f64;
                continue;
            }
            raw[i] = if a > 0.0 {
                left * strata[i].size as f64 * strata[i].sd / strata[i].cost.sqrt() / a
            } else {
                2.0
            };
            if raw[i] >= strata[i].size as f64 {
                full[i] = true;
                new_full = true;
            }
        }
        if !new_full {
            break;
        }
    }
    let mut a = finish(strata, &raw);
    a.bounded = a.bounded || full.iter().any(|&f| f);
    repair_budget(strata, budget, &mut a);
    Ok(a)
}

/// Rounding can push the cost above the budget; drop units, one at a time,
/// (this is a rounding repair, not a bound: `bounded` is left as it is),
/// from the stratum whose unit removal raises the variance least per unit of
/// cost saved, keeping `n_h >= 2`, until the cost fits. Then add units back
/// greedily while they still fit.
fn repair_budget(strata: &[Stratum], budget: f64, a: &mut Allocation) {
    let gain = |n: &[usize], h: usize, delta: i64| -> f64 {
        let mut m = n.to_vec();
        m[h] = (m[h] as i64 + delta) as usize;
        variance_of(strata, &m)
    };
    while a.cost > budget + 1e-9 {
        let mut best: Option<(usize, f64)> = None;
        for (h, s) in strata.iter().enumerate() {
            if a.n[h] > 2 {
                let rate = (gain(&a.n, h, -1) - a.variance) / s.cost;
                if best.map_or(true, |(_, r)| rate < r) {
                    best = Some((h, rate));
                }
            }
        }
        match best {
            Some((h, _)) => {
                a.n[h] -= 1;
                a.cost -= strata[h].cost;
                a.variance = variance_of(strata, &a.n);
            }
            None => break,
        }
    }
    loop {
        let mut best: Option<(usize, f64)> = None;
        for (h, s) in strata.iter().enumerate() {
            if a.n[h] < s.size && a.cost + s.cost <= budget + 1e-9 {
                let rate = (a.variance - gain(&a.n, h, 1)) / s.cost;
                if best.map_or(true, |(_, r)| rate > r) {
                    best = Some((h, rate));
                }
            }
        }
        match best {
            Some((h, _)) => {
                a.n[h] += 1;
                a.cost += strata[h].cost;
                a.variance = variance_of(strata, &a.n);
            }
            None => break,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn neyman_with_cost() {
        let strata = vec![
            Stratum {
                size: 1000,
                sd: 10.0,
                cost: 1.0,
            },
            Stratum {
                size: 1000,
                sd: 10.0,
                cost: 4.0,
            },
        ];
        let a = allocate_for_variance(&strata, 1e6).unwrap();
        // equal N and S: n_h proportional to 1 / sqrt(c_h) => ratio 2:1
        assert!(
            (a.n[0] as f64 / a.n[1] as f64 - 2.0).abs() < 0.1,
            "{:?}",
            a.n
        );
        assert!(a.variance <= 1e6 * 1.05);
        let b = allocate_for_budget(&strata, a.cost).unwrap();
        assert!((b.variance - a.variance).abs() / a.variance < 0.05);
        assert!(
            b.cost <= a.cost + 1e-9,
            "cost {} exceeds budget {}",
            b.cost,
            a.cost
        );
        let c = allocate_for_budget(
            &[
                Stratum {
                    size: 2000,
                    sd: 12.0,
                    cost: 40.0,
                },
                Stratum {
                    size: 800,
                    sd: 30.0,
                    cost: 180.0,
                },
            ],
            20000.0,
        )
        .unwrap();
        assert!(c.cost <= 20000.0 && c.cost > 19600.0, "cost {}", c.cost);
        assert!(allocate_for_variance(&strata, -1.0).is_err());
        assert!(allocate_for_variance(
            &[Stratum {
                size: 1,
                sd: 1.0,
                cost: 1.0
            }],
            1.0
        )
        .is_err());
    }

    #[test]
    fn full_strata_keep_the_target() {
        // frame B is tiny and cheap: taken completely; the target must still hold
        let strata = vec![
            Stratum {
                size: 680,
                sd: 24.0,
                cost: 103.0,
            },
            Stratum {
                size: 100,
                sd: 32.0,
                cost: 45.0,
            },
        ];
        let a = allocate_for_variance(&strata, 119_025.0).unwrap();
        assert_eq!(a.n[1], 100);
        assert!(
            a.variance <= 119_025.0 * (1.0 + 1e-9),
            "variance {}",
            a.variance
        );
        assert!(a.bounded);
        let b = allocate_for_budget(&strata, 20_000.0).unwrap();
        assert!(b.cost <= 20_000.0 + 1e-9);
        assert!(b.n[1] <= 100);
    }

    #[test]
    fn bounds_are_reported() {
        let strata = vec![Stratum {
            size: 10,
            sd: 100.0,
            cost: 1.0,
        }];
        // a huge target variance would allow fewer than two units: bounded below at 2
        let a = allocate_for_variance(&strata, 1e9).unwrap();
        assert_eq!(a.n[0], 2);
        assert!(a.bounded);
        // a tiny target variance asks for the whole stratum: n = N, variance zero
        let b = allocate_for_variance(&strata, 1e-6).unwrap();
        assert_eq!(b.n[0], 10);
        assert_eq!(b.variance, 0.0);
    }
}