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 v = r.ceil().max(2.0).min(s.size as f64);
72            if (v - r.ceil()).abs() > 1e-9 {
73                bounded = true;
74            }
75            v as usize
76        })
77        .collect();
78    let cost = strata
79        .iter()
80        .zip(&n)
81        .map(|(s, &nh)| s.cost * nh as f64)
82        .sum();
83    Allocation {
84        variance: variance_of(strata, &n),
85        cost,
86        n,
87        bounded,
88    }
89}
90
91/// Allocation that minimises cost subject to variance at most `target_variance`.
92pub fn allocate_for_variance(
93    strata: &[Stratum],
94    target_variance: f64,
95) -> Result<Allocation, String> {
96    validate(strata)?;
97    if !target_variance.is_finite() || target_variance <= 0.0 {
98        return Err("the target variance must be positive".into());
99    }
100    let a: f64 = strata
101        .iter()
102        .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
103        .sum();
104    let b: f64 = strata.iter().map(|s| s.size as f64 * s.sd * s.sd).sum();
105    let denom = target_variance + b;
106    let raw: Vec<f64> = strata
107        .iter()
108        .map(|s| s.size as f64 * s.sd / s.cost.sqrt() * a / denom)
109        .collect();
110    Ok(finish(strata, &raw))
111}
112
113/// Allocation that minimises variance subject to cost at most `budget`.
114pub fn allocate_for_budget(strata: &[Stratum], budget: f64) -> Result<Allocation, String> {
115    validate(strata)?;
116    if !budget.is_finite() || budget <= 0.0 {
117        return Err("the budget must be positive".into());
118    }
119    let a: f64 = strata
120        .iter()
121        .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
122        .sum();
123    if a <= 0.0 {
124        return Err("every stratum has zero standard deviation; nothing to allocate".into());
125    }
126    let raw: Vec<f64> = strata
127        .iter()
128        .map(|s| budget * s.size as f64 * s.sd / s.cost.sqrt() / a)
129        .collect();
130    let mut a = finish(strata, &raw);
131    repair_budget(strata, budget, &mut a);
132    Ok(a)
133}
134
135/// Rounding can push the cost above the budget; drop units, one at a time,
136/// (this is a rounding repair, not a bound: `bounded` is left as it is),
137/// from the stratum whose unit removal raises the variance least per unit of
138/// cost saved, keeping `n_h >= 2`, until the cost fits. Then add units back
139/// greedily while they still fit.
140fn repair_budget(strata: &[Stratum], budget: f64, a: &mut Allocation) {
141    let gain = |n: &[usize], h: usize, delta: i64| -> f64 {
142        let mut m = n.to_vec();
143        m[h] = (m[h] as i64 + delta) as usize;
144        variance_of(strata, &m)
145    };
146    while a.cost > budget + 1e-9 {
147        let mut best: Option<(usize, f64)> = None;
148        for (h, s) in strata.iter().enumerate() {
149            if a.n[h] > 2 {
150                let rate = (gain(&a.n, h, -1) - a.variance) / s.cost;
151                if best.map_or(true, |(_, r)| rate < r) {
152                    best = Some((h, rate));
153                }
154            }
155        }
156        match best {
157            Some((h, _)) => {
158                a.n[h] -= 1;
159                a.cost -= strata[h].cost;
160                a.variance = variance_of(strata, &a.n);
161            }
162            None => break,
163        }
164    }
165    loop {
166        let mut best: Option<(usize, f64)> = None;
167        for (h, s) in strata.iter().enumerate() {
168            if a.n[h] < s.size && a.cost + s.cost <= budget + 1e-9 {
169                let rate = (a.variance - gain(&a.n, h, 1)) / s.cost;
170                if best.map_or(true, |(_, r)| rate > r) {
171                    best = Some((h, rate));
172                }
173            }
174        }
175        match best {
176            Some((h, _)) => {
177                a.n[h] += 1;
178                a.cost += strata[h].cost;
179                a.variance = variance_of(strata, &a.n);
180            }
181            None => break,
182        }
183    }
184}
185
186#[cfg(test)]
187mod tests {
188    use super::*;
189
190    #[test]
191    fn neyman_with_cost() {
192        let strata = vec![
193            Stratum {
194                size: 1000,
195                sd: 10.0,
196                cost: 1.0,
197            },
198            Stratum {
199                size: 1000,
200                sd: 10.0,
201                cost: 4.0,
202            },
203        ];
204        let a = allocate_for_variance(&strata, 1e6).unwrap();
205        // equal N and S: n_h proportional to 1 / sqrt(c_h) => ratio 2:1
206        assert!(
207            (a.n[0] as f64 / a.n[1] as f64 - 2.0).abs() < 0.1,
208            "{:?}",
209            a.n
210        );
211        assert!(a.variance <= 1e6 * 1.05);
212        let b = allocate_for_budget(&strata, a.cost).unwrap();
213        assert!((b.variance - a.variance).abs() / a.variance < 0.05);
214        assert!(
215            b.cost <= a.cost + 1e-9,
216            "cost {} exceeds budget {}",
217            b.cost,
218            a.cost
219        );
220        let c = allocate_for_budget(
221            &[
222                Stratum {
223                    size: 2000,
224                    sd: 12.0,
225                    cost: 40.0,
226                },
227                Stratum {
228                    size: 800,
229                    sd: 30.0,
230                    cost: 180.0,
231                },
232            ],
233            20000.0,
234        )
235        .unwrap();
236        assert!(c.cost <= 20000.0 && c.cost > 19600.0, "cost {}", c.cost);
237        assert!(allocate_for_variance(&strata, -1.0).is_err());
238        assert!(allocate_for_variance(
239            &[Stratum {
240                size: 1,
241                sd: 1.0,
242                cost: 1.0
243            }],
244            1.0
245        )
246        .is_err());
247    }
248
249    #[test]
250    fn bounds_are_reported() {
251        let strata = vec![Stratum {
252            size: 10,
253            sd: 100.0,
254            cost: 1.0,
255        }];
256        // a huge target variance would allow fewer than two units: bounded below at 2
257        let a = allocate_for_variance(&strata, 1e9).unwrap();
258        assert_eq!(a.n[0], 2);
259        assert!(a.bounded);
260        // a tiny target variance asks for the whole stratum: n = N, variance zero
261        let b = allocate_for_variance(&strata, 1e-6).unwrap();
262        assert_eq!(b.n[0], 10);
263        assert_eq!(b.variance, 0.0);
264    }
265}