Skip to main content

fieldopt_core/
allocation.rs

1//! Cost-aware allocation across strata (or frames treated as strata).
2//!
3//! Minimises the field cost `sum_h c_h n_h` subject to a target variance of
4//! the estimated total under stratified sampling,
5//! `sum_h N_h^2 S_h^2 / n_h - sum_h N_h S_h^2 = V0`, or minimises the variance
6//! subject to a cost budget. The solution is the classical optimum
7//! `n_h proportional to N_h S_h / sqrt(c_h)` (Cochran, 1977, Section 5.5),
8//! scaled to meet the constraint, then bounded to `[2, N_h]`. Bounding makes
9//! the result approximate when a bound is active; the function reports the
10//! variance and cost actually attained.
11
12/// One stratum of the allocation problem.
13#[derive(Clone, Copy, Debug)]
14pub struct Stratum {
15    /// Number of population units.
16    pub size: usize,
17    /// Standard deviation of the study variable within the stratum.
18    pub sd: f64,
19    /// Cost of one unit (interview plus expected access cost).
20    pub cost: f64,
21}
22
23/// An allocation and what it attains.
24#[derive(Clone, Debug, PartialEq)]
25pub struct Allocation {
26    /// Sample size per stratum.
27    pub n: Vec<usize>,
28    /// Total cost `sum c_h n_h`.
29    pub cost: f64,
30    /// Variance of the estimated total attained.
31    pub variance: f64,
32    /// Whether a bound (`2 <= n_h <= N_h`) was active.
33    pub bounded: bool,
34}
35
36fn validate(strata: &[Stratum]) -> Result<(), String> {
37    if strata.is_empty() {
38        return Err("at least one stratum is needed".into());
39    }
40    for (h, s) in strata.iter().enumerate() {
41        if s.size < 2 {
42            return Err(format!("stratum {h} has fewer than two units"));
43        }
44        if !s.sd.is_finite() || s.sd < 0.0 {
45            return Err(format!("stratum {h} has an invalid standard deviation"));
46        }
47        if !s.cost.is_finite() || s.cost <= 0.0 {
48            return Err(format!("stratum {h} must have a positive cost"));
49        }
50    }
51    Ok(())
52}
53
54fn variance_of(strata: &[Stratum], n: &[usize]) -> f64 {
55    strata
56        .iter()
57        .zip(n)
58        .map(|(s, &nh)| {
59            let big_n = s.size as f64;
60            big_n * big_n * s.sd * s.sd / nh as f64 * (1.0 - nh as f64 / big_n)
61        })
62        .sum()
63}
64
65fn finish(strata: &[Stratum], raw: &[f64]) -> Allocation {
66    let mut bounded = false;
67    let n: Vec<usize> = strata
68        .iter()
69        .zip(raw)
70        .map(|(s, &r)| {
71            let up = (r - 1e-9).ceil();
72            let v = up.max(2.0).min(s.size as f64);
73            if (v - up).abs() > 1e-9 {
74                bounded = true;
75            }
76            v as usize
77        })
78        .collect();
79    let cost = strata
80        .iter()
81        .zip(&n)
82        .map(|(s, &nh)| s.cost * nh as f64)
83        .sum();
84    Allocation {
85        variance: variance_of(strata, &n),
86        cost,
87        n,
88        bounded,
89    }
90}
91
92/// Allocation that minimises cost subject to variance at most `target_variance`.
93pub fn allocate_for_variance(
94    strata: &[Stratum],
95    target_variance: f64,
96) -> Result<Allocation, String> {
97    validate(strata)?;
98    if !target_variance.is_finite() || target_variance <= 0.0 {
99        return Err("the target variance must be positive".into());
100    }
101    let a: f64 = strata
102        .iter()
103        .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
104        .sum();
105    let b: f64 = strata.iter().map(|s| s.size as f64 * s.sd * s.sd).sum();
106    let denom = target_variance + b;
107    let raw: Vec<f64> = strata
108        .iter()
109        .map(|s| s.size as f64 * s.sd / s.cost.sqrt() * a / denom)
110        .collect();
111    Ok(finish(strata, &raw))
112}
113
114/// Allocation that minimises variance subject to cost at most `budget`.
115pub fn allocate_for_budget(strata: &[Stratum], budget: f64) -> Result<Allocation, String> {
116    validate(strata)?;
117    if !budget.is_finite() || budget <= 0.0 {
118        return Err("the budget must be positive".into());
119    }
120    let a: f64 = strata
121        .iter()
122        .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
123        .sum();
124    if a <= 0.0 {
125        return Err("every stratum has zero standard deviation; nothing to allocate".into());
126    }
127    let raw: Vec<f64> = strata
128        .iter()
129        .map(|s| budget * s.size as f64 * s.sd / s.cost.sqrt() / a)
130        .collect();
131    let mut a = finish(strata, &raw);
132    repair_budget(strata, budget, &mut a);
133    Ok(a)
134}
135
136/// Rounding can push the cost above the budget; drop units, one at a time,
137/// (this is a rounding repair, not a bound: `bounded` is left as it is),
138/// from the stratum whose unit removal raises the variance least per unit of
139/// cost saved, keeping `n_h >= 2`, until the cost fits. Then add units back
140/// greedily while they still fit.
141fn repair_budget(strata: &[Stratum], budget: f64, a: &mut Allocation) {
142    let gain = |n: &[usize], h: usize, delta: i64| -> f64 {
143        let mut m = n.to_vec();
144        m[h] = (m[h] as i64 + delta) as usize;
145        variance_of(strata, &m)
146    };
147    while a.cost > budget + 1e-9 {
148        let mut best: Option<(usize, f64)> = None;
149        for (h, s) in strata.iter().enumerate() {
150            if a.n[h] > 2 {
151                let rate = (gain(&a.n, h, -1) - a.variance) / s.cost;
152                if best.map_or(true, |(_, r)| rate < r) {
153                    best = Some((h, rate));
154                }
155            }
156        }
157        match best {
158            Some((h, _)) => {
159                a.n[h] -= 1;
160                a.cost -= strata[h].cost;
161                a.variance = variance_of(strata, &a.n);
162            }
163            None => break,
164        }
165    }
166    loop {
167        let mut best: Option<(usize, f64)> = None;
168        for (h, s) in strata.iter().enumerate() {
169            if a.n[h] < s.size && a.cost + s.cost <= budget + 1e-9 {
170                let rate = (a.variance - gain(&a.n, h, 1)) / s.cost;
171                if best.map_or(true, |(_, r)| rate > r) {
172                    best = Some((h, rate));
173                }
174            }
175        }
176        match best {
177            Some((h, _)) => {
178                a.n[h] += 1;
179                a.cost += strata[h].cost;
180                a.variance = variance_of(strata, &a.n);
181            }
182            None => break,
183        }
184    }
185}
186
187#[cfg(test)]
188mod tests {
189    use super::*;
190
191    #[test]
192    fn neyman_with_cost() {
193        let strata = vec![
194            Stratum {
195                size: 1000,
196                sd: 10.0,
197                cost: 1.0,
198            },
199            Stratum {
200                size: 1000,
201                sd: 10.0,
202                cost: 4.0,
203            },
204        ];
205        let a = allocate_for_variance(&strata, 1e6).unwrap();
206        // equal N and S: n_h proportional to 1 / sqrt(c_h) => ratio 2:1
207        assert!(
208            (a.n[0] as f64 / a.n[1] as f64 - 2.0).abs() < 0.1,
209            "{:?}",
210            a.n
211        );
212        assert!(a.variance <= 1e6 * 1.05);
213        let b = allocate_for_budget(&strata, a.cost).unwrap();
214        assert!((b.variance - a.variance).abs() / a.variance < 0.05);
215        assert!(
216            b.cost <= a.cost + 1e-9,
217            "cost {} exceeds budget {}",
218            b.cost,
219            a.cost
220        );
221        let c = allocate_for_budget(
222            &[
223                Stratum {
224                    size: 2000,
225                    sd: 12.0,
226                    cost: 40.0,
227                },
228                Stratum {
229                    size: 800,
230                    sd: 30.0,
231                    cost: 180.0,
232                },
233            ],
234            20000.0,
235        )
236        .unwrap();
237        assert!(c.cost <= 20000.0 && c.cost > 19600.0, "cost {}", c.cost);
238        assert!(allocate_for_variance(&strata, -1.0).is_err());
239        assert!(allocate_for_variance(
240            &[Stratum {
241                size: 1,
242                sd: 1.0,
243                cost: 1.0
244            }],
245            1.0
246        )
247        .is_err());
248    }
249
250    #[test]
251    fn bounds_are_reported() {
252        let strata = vec![Stratum {
253            size: 10,
254            sd: 100.0,
255            cost: 1.0,
256        }];
257        // a huge target variance would allow fewer than two units: bounded below at 2
258        let a = allocate_for_variance(&strata, 1e9).unwrap();
259        assert_eq!(a.n[0], 2);
260        assert!(a.bounded);
261        // a tiny target variance asks for the whole stratum: n = N, variance zero
262        let b = allocate_for_variance(&strata, 1e-6).unwrap();
263        assert_eq!(b.n[0], 10);
264        assert_eq!(b.variance, 0.0);
265    }
266}