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    // Strata whose unrounded optimum exceeds their size are taken completely
102    // (they then contribute no variance) and the rest is re-solved for the
103    // same target, until no new stratum hits its size.
104    let h = strata.len();
105    let mut full = vec![false; h];
106    let mut raw = vec![0.0; h];
107    loop {
108        let a: f64 = (0..h)
109            .filter(|&i| !full[i])
110            .map(|i| strata[i].size as f64 * strata[i].sd * strata[i].cost.sqrt())
111            .sum();
112        let b: f64 = (0..h)
113            .filter(|&i| !full[i])
114            .map(|i| strata[i].size as f64 * strata[i].sd * strata[i].sd)
115            .sum();
116        let denom = target_variance + b;
117        let mut new_full = false;
118        for i in 0..h {
119            if full[i] {
120                raw[i] = strata[i].size as f64;
121                continue;
122            }
123            raw[i] = strata[i].size as f64 * strata[i].sd / strata[i].cost.sqrt() * a / denom;
124            if raw[i] >= strata[i].size as f64 {
125                full[i] = true;
126                new_full = true;
127            }
128        }
129        if !new_full {
130            break;
131        }
132    }
133    let mut out = finish(strata, &raw);
134    out.bounded = out.bounded || full.iter().any(|&f| f);
135    Ok(out)
136}
137
138pub fn allocate_for_budget(strata: &[Stratum], budget: f64) -> Result<Allocation, String> {
139    validate(strata)?;
140    if !budget.is_finite() || budget <= 0.0 {
141        return Err("the budget must be positive".into());
142    }
143    let h = strata.len();
144    let a_all: f64 = strata
145        .iter()
146        .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
147        .sum();
148    if a_all <= 0.0 {
149        return Err("every stratum has zero standard deviation; nothing to allocate".into());
150    }
151    // Strata whose optimum exceeds their size are taken completely; their
152    // cost is removed from the budget and the rest is re-solved.
153    let mut full = vec![false; h];
154    let mut raw = vec![0.0; h];
155    loop {
156        let spent: f64 = (0..h)
157            .filter(|&i| full[i])
158            .map(|i| strata[i].cost * strata[i].size as f64)
159            .sum();
160        let left = budget - spent;
161        if left <= 0.0 {
162            return Err(
163                "the budget does not cover the strata that must be taken completely".into(),
164            );
165        }
166        let a: f64 = (0..h)
167            .filter(|&i| !full[i])
168            .map(|i| strata[i].size as f64 * strata[i].sd * strata[i].cost.sqrt())
169            .sum();
170        let mut new_full = false;
171        for i in 0..h {
172            if full[i] {
173                raw[i] = strata[i].size as f64;
174                continue;
175            }
176            raw[i] = if a > 0.0 {
177                left * strata[i].size as f64 * strata[i].sd / strata[i].cost.sqrt() / a
178            } else {
179                2.0
180            };
181            if raw[i] >= strata[i].size as f64 {
182                full[i] = true;
183                new_full = true;
184            }
185        }
186        if !new_full {
187            break;
188        }
189    }
190    let mut a = finish(strata, &raw);
191    a.bounded = a.bounded || full.iter().any(|&f| f);
192    repair_budget(strata, budget, &mut a);
193    Ok(a)
194}
195
196/// Rounding can push the cost above the budget; drop units, one at a time,
197/// (this is a rounding repair, not a bound: `bounded` is left as it is),
198/// from the stratum whose unit removal raises the variance least per unit of
199/// cost saved, keeping `n_h >= 2`, until the cost fits. Then add units back
200/// greedily while they still fit.
201fn repair_budget(strata: &[Stratum], budget: f64, a: &mut Allocation) {
202    let gain = |n: &[usize], h: usize, delta: i64| -> f64 {
203        let mut m = n.to_vec();
204        m[h] = (m[h] as i64 + delta) as usize;
205        variance_of(strata, &m)
206    };
207    while a.cost > budget + 1e-9 {
208        let mut best: Option<(usize, f64)> = None;
209        for (h, s) in strata.iter().enumerate() {
210            if a.n[h] > 2 {
211                let rate = (gain(&a.n, h, -1) - a.variance) / s.cost;
212                if best.map_or(true, |(_, r)| rate < r) {
213                    best = Some((h, rate));
214                }
215            }
216        }
217        match best {
218            Some((h, _)) => {
219                a.n[h] -= 1;
220                a.cost -= strata[h].cost;
221                a.variance = variance_of(strata, &a.n);
222            }
223            None => break,
224        }
225    }
226    loop {
227        let mut best: Option<(usize, f64)> = None;
228        for (h, s) in strata.iter().enumerate() {
229            if a.n[h] < s.size && a.cost + s.cost <= budget + 1e-9 {
230                let rate = (a.variance - gain(&a.n, h, 1)) / s.cost;
231                if best.map_or(true, |(_, r)| rate > r) {
232                    best = Some((h, rate));
233                }
234            }
235        }
236        match best {
237            Some((h, _)) => {
238                a.n[h] += 1;
239                a.cost += strata[h].cost;
240                a.variance = variance_of(strata, &a.n);
241            }
242            None => break,
243        }
244    }
245}
246
247#[cfg(test)]
248mod tests {
249    use super::*;
250
251    #[test]
252    fn neyman_with_cost() {
253        let strata = vec![
254            Stratum {
255                size: 1000,
256                sd: 10.0,
257                cost: 1.0,
258            },
259            Stratum {
260                size: 1000,
261                sd: 10.0,
262                cost: 4.0,
263            },
264        ];
265        let a = allocate_for_variance(&strata, 1e6).unwrap();
266        // equal N and S: n_h proportional to 1 / sqrt(c_h) => ratio 2:1
267        assert!(
268            (a.n[0] as f64 / a.n[1] as f64 - 2.0).abs() < 0.1,
269            "{:?}",
270            a.n
271        );
272        assert!(a.variance <= 1e6 * 1.05);
273        let b = allocate_for_budget(&strata, a.cost).unwrap();
274        assert!((b.variance - a.variance).abs() / a.variance < 0.05);
275        assert!(
276            b.cost <= a.cost + 1e-9,
277            "cost {} exceeds budget {}",
278            b.cost,
279            a.cost
280        );
281        let c = allocate_for_budget(
282            &[
283                Stratum {
284                    size: 2000,
285                    sd: 12.0,
286                    cost: 40.0,
287                },
288                Stratum {
289                    size: 800,
290                    sd: 30.0,
291                    cost: 180.0,
292                },
293            ],
294            20000.0,
295        )
296        .unwrap();
297        assert!(c.cost <= 20000.0 && c.cost > 19600.0, "cost {}", c.cost);
298        assert!(allocate_for_variance(&strata, -1.0).is_err());
299        assert!(allocate_for_variance(
300            &[Stratum {
301                size: 1,
302                sd: 1.0,
303                cost: 1.0
304            }],
305            1.0
306        )
307        .is_err());
308    }
309
310    #[test]
311    fn full_strata_keep_the_target() {
312        // frame B is tiny and cheap: taken completely; the target must still hold
313        let strata = vec![
314            Stratum {
315                size: 680,
316                sd: 24.0,
317                cost: 103.0,
318            },
319            Stratum {
320                size: 100,
321                sd: 32.0,
322                cost: 45.0,
323            },
324        ];
325        let a = allocate_for_variance(&strata, 119_025.0).unwrap();
326        assert_eq!(a.n[1], 100);
327        assert!(
328            a.variance <= 119_025.0 * (1.0 + 1e-9),
329            "variance {}",
330            a.variance
331        );
332        assert!(a.bounded);
333        let b = allocate_for_budget(&strata, 20_000.0).unwrap();
334        assert!(b.cost <= 20_000.0 + 1e-9);
335        assert!(b.n[1] <= 100);
336    }
337
338    #[test]
339    fn bounds_are_reported() {
340        let strata = vec![Stratum {
341            size: 10,
342            sd: 100.0,
343            cost: 1.0,
344        }];
345        // a huge target variance would allow fewer than two units: bounded below at 2
346        let a = allocate_for_variance(&strata, 1e9).unwrap();
347        assert_eq!(a.n[0], 2);
348        assert!(a.bounded);
349        // a tiny target variance asks for the whole stratum: n = N, variance zero
350        let b = allocate_for_variance(&strata, 1e-6).unwrap();
351        assert_eq!(b.n[0], 10);
352        assert_eq!(b.variance, 0.0);
353    }
354}