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 r < 2.0 - 1e-9 || r > s.size as f64 + 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
138/// Allocation of minimum variance for a budget (cost-optimal allocation of
139/// Cochran 1977, Section 5.5, with the cost function `sum c_h n_h`). Strata
140/// whose optimum exceeds their size are taken completely and the rest is
141/// re-solved; every stratum keeps at least two units (one when it has a
142/// single unit), and the budget must cover that floor. Rounding is repaired
143/// so that the cost stays within the budget.
144pub fn allocate_for_budget(strata: &[Stratum], budget: f64) -> Result<Allocation, String> {
145    validate(strata)?;
146    if !budget.is_finite() || budget <= 0.0 {
147        return Err("the budget must be positive".into());
148    }
149    let floor_cost: f64 = strata.iter().map(|s| s.cost * (s.size.min(2)) as f64).sum();
150    if floor_cost > budget + 1e-9 {
151        return Err(format!(
152            "the budget {budget} does not cover two units per stratum (cost {floor_cost})"
153        ));
154    }
155    let h = strata.len();
156    let a_all: f64 = strata
157        .iter()
158        .map(|s| s.size as f64 * s.sd * s.cost.sqrt())
159        .sum();
160    if a_all <= 0.0 {
161        return Err("every stratum has zero standard deviation; nothing to allocate".into());
162    }
163    // Strata whose optimum exceeds their size are taken completely; their
164    // cost is removed from the budget and the rest is re-solved.
165    let mut full = vec![false; h];
166    let mut raw = vec![0.0; h];
167    loop {
168        let spent: f64 = (0..h)
169            .filter(|&i| full[i])
170            .map(|i| strata[i].cost * strata[i].size as f64)
171            .sum();
172        let left = budget - spent;
173        if left <= 0.0 {
174            return Err(
175                "the budget does not cover the strata that must be taken completely".into(),
176            );
177        }
178        let a: f64 = (0..h)
179            .filter(|&i| !full[i])
180            .map(|i| strata[i].size as f64 * strata[i].sd * strata[i].cost.sqrt())
181            .sum();
182        let mut new_full = false;
183        for i in 0..h {
184            if full[i] {
185                raw[i] = strata[i].size as f64;
186                continue;
187            }
188            raw[i] = if a > 0.0 {
189                left * strata[i].size as f64 * strata[i].sd / strata[i].cost.sqrt() / a
190            } else {
191                2.0
192            };
193            if raw[i] >= strata[i].size as f64 {
194                full[i] = true;
195                new_full = true;
196            }
197        }
198        if !new_full {
199            break;
200        }
201    }
202    let mut a = finish(strata, &raw);
203    a.bounded = a.bounded || full.iter().any(|&f| f);
204    repair_budget(strata, budget, &mut a);
205    Ok(a)
206}
207
208/// Rounding can push the cost above the budget; drop units, one at a time,
209/// (this is a rounding repair, not a bound: `bounded` is left as it is),
210/// from the stratum whose unit removal raises the variance least per unit of
211/// cost saved, keeping `n_h >= 2`, until the cost fits. Then add units back
212/// greedily while they still fit.
213fn repair_budget(strata: &[Stratum], budget: f64, a: &mut Allocation) {
214    let gain = |n: &[usize], h: usize, delta: i64| -> f64 {
215        let mut m = n.to_vec();
216        m[h] = (m[h] as i64 + delta) as usize;
217        variance_of(strata, &m)
218    };
219    while a.cost > budget + 1e-9 {
220        let mut best: Option<(usize, f64)> = None;
221        for (h, s) in strata.iter().enumerate() {
222            if a.n[h] > 2 {
223                let rate = (gain(&a.n, h, -1) - a.variance) / s.cost;
224                if best.map_or(true, |(_, r)| rate < r) {
225                    best = Some((h, rate));
226                }
227            }
228        }
229        match best {
230            Some((h, _)) => {
231                a.n[h] -= 1;
232                a.cost -= strata[h].cost;
233                a.variance = variance_of(strata, &a.n);
234            }
235            None => break,
236        }
237    }
238    loop {
239        let mut best: Option<(usize, f64)> = None;
240        for (h, s) in strata.iter().enumerate() {
241            if a.n[h] < s.size && a.cost + s.cost <= budget + 1e-9 {
242                let rate = (a.variance - gain(&a.n, h, 1)) / s.cost;
243                if best.map_or(true, |(_, r)| rate > r) {
244                    best = Some((h, rate));
245                }
246            }
247        }
248        match best {
249            Some((h, _)) => {
250                a.n[h] += 1;
251                a.cost += strata[h].cost;
252                a.variance = variance_of(strata, &a.n);
253            }
254            None => break,
255        }
256    }
257}
258
259/// Multivariate allocation: minimum cost `sum c_h n_h` such that the variance
260/// of the estimated total of every study variable `j` is at most its target,
261/// `sum_h N_h^2 S_hj^2 / n_h - sum_h N_h S_hj^2 <= V0_j` (Bethel 1989;
262/// Chromy 1987). `sd` is `H x J` row-major (one column per variable, in the
263/// same units as `targets`). The Lagrangian solution `n_h = sqrt(sum_j mu_j
264/// a_hj / c_h)` is found by multiplicative updates of the multipliers; strata
265/// whose solution exceeds their size are taken completely and the rest
266/// re-solved; every stratum keeps at least two units. Returns the allocation
267/// and, in `attained`, the variance of each variable.
268#[derive(Clone, Debug, PartialEq)]
269pub struct MultiAllocation {
270    pub n: Vec<usize>,
271    pub cost: f64,
272    /// Variance attained for each variable.
273    pub attained: Vec<f64>,
274    /// Whether a bound (`2 <= n_h <= N_h`) moved the solution.
275    pub bounded: bool,
276    /// Multipliers of the constraints: zero for a constraint that is slack.
277    pub multipliers: Vec<f64>,
278}
279
280pub fn allocate_multivariate(
281    sizes: &[usize],
282    costs: &[f64],
283    sd: &[f64],
284    targets: &[f64],
285) -> Result<MultiAllocation, String> {
286    let h = sizes.len();
287    let j = targets.len();
288    if h == 0 || j == 0 || costs.len() != h || sd.len() != h * j {
289        return Err("sizes and costs need one entry per stratum, sd one row per stratum and one column per target".into());
290    }
291    if sizes.iter().any(|&n| n < 2) {
292        return Err("every stratum needs at least two units".into());
293    }
294    if costs.iter().any(|c| !c.is_finite() || *c <= 0.0) {
295        return Err("costs must be positive".into());
296    }
297    if sd.iter().any(|s| !s.is_finite() || *s < 0.0) {
298        return Err("standard deviations must be finite and non-negative".into());
299    }
300    if targets.iter().any(|v| !v.is_finite() || *v <= 0.0) {
301        return Err("target variances must be positive".into());
302    }
303    let big_n: Vec<f64> = sizes.iter().map(|&n| n as f64).collect();
304    // constraint j: sum_h a_hj / n_h <= b_j
305    let a = |hh: usize, jj: usize| big_n[hh].powi(2) * sd[hh * j + jj].powi(2);
306    let b: Vec<f64> = (0..j)
307        .map(|jj| {
308            targets[jj]
309                + (0..h)
310                    .map(|hh| big_n[hh] * sd[hh * j + jj].powi(2))
311                    .sum::<f64>()
312        })
313        .collect();
314    let mut full = vec![false; h];
315    let mut raw = vec![0.0; h];
316    let mut mu = vec![1.0; j];
317    loop {
318        // budget left for each constraint after the full strata
319        let b_left: Vec<f64> = (0..j)
320            .map(|jj| {
321                b[jj]
322                    - (0..h)
323                        .filter(|&hh| full[hh])
324                        .map(|hh| a(hh, jj) / big_n[hh])
325                        .sum::<f64>()
326            })
327            .collect();
328        if b_left.iter().any(|v| *v <= 0.0) {
329            return Err("a target variance cannot be met even by observing every unit".into());
330        }
331        let free: Vec<usize> = (0..h).filter(|&hh| !full[hh]).collect();
332        if free.is_empty() {
333            break;
334        }
335        // binding set: constraints that cannot be satisfied are those with positive mu
336        for _ in 0..20_000 {
337            for &hh in &free {
338                let num: f64 = (0..j).map(|jj| mu[jj] * a(hh, jj)).sum();
339                raw[hh] = (num / costs[hh]).sqrt().max(1e-9);
340            }
341            let ratios: Vec<f64> = (0..j)
342                .map(|jj| free.iter().map(|&hh| a(hh, jj) / raw[hh]).sum::<f64>() / b_left[jj])
343                .collect();
344            let mut done = true;
345            for jj in 0..j {
346                let r = ratios[jj];
347                if r > 1.0 + 1e-9 || (mu[jj] > 1e-12 && r < 1.0 - 1e-9) {
348                    done = false;
349                }
350                mu[jj] *= r.powf(0.5);
351                if mu[jj] < 1e-14 {
352                    mu[jj] = 0.0;
353                }
354            }
355            if mu.iter().all(|v| *v == 0.0) {
356                mu = vec![1e-6; j];
357            }
358            if done {
359                break;
360            }
361        }
362        // scale up so that no constraint is violated after the solve
363        let worst = (0..j)
364            .map(|jj| free.iter().map(|&hh| a(hh, jj) / raw[hh]).sum::<f64>() / b_left[jj])
365            .fold(0.0, f64::max);
366        if worst > 1.0 {
367            for &hh in &free {
368                raw[hh] *= worst;
369            }
370        }
371        let mut new_full = false;
372        for &hh in &free {
373            if raw[hh] >= big_n[hh] - 1e-9 {
374                full[hh] = true;
375                raw[hh] = big_n[hh];
376                new_full = true;
377            }
378        }
379        if !new_full {
380            break;
381        }
382    }
383    let mut bounded = full.iter().any(|&f| f);
384    let n: Vec<usize> = (0..h)
385        .map(|hh| {
386            let up = (raw[hh] - 1e-9).ceil();
387            if up < 2.0 {
388                bounded = true;
389            }
390            (up.max(2.0).min(big_n[hh])) as usize
391        })
392        .collect();
393    let cost = (0..h).map(|hh| costs[hh] * n[hh] as f64).sum();
394    let attained: Vec<f64> = (0..j)
395        .map(|jj| {
396            (0..h)
397                .map(|hh| a(hh, jj) / n[hh] as f64 - big_n[hh] * sd[hh * j + jj].powi(2))
398                .sum()
399        })
400        .collect();
401    Ok(MultiAllocation {
402        n,
403        cost,
404        attained,
405        bounded,
406        multipliers: mu,
407    })
408}
409
410#[cfg(test)]
411mod tests {
412    use super::*;
413
414    #[test]
415    fn multivariate_allocation_meets_every_target_at_minimum_cost() {
416        // two strata, two variables; the second variable is the binding one in stratum 2
417        let sizes = [1000usize, 500];
418        let costs = [10.0, 30.0];
419        let sd = [5.0, 2.0, 3.0, 9.0]; // H x J
420                                       // targets from the univariate optimum of each variable at n = 120 total
421        let s1 = [
422            Stratum {
423                size: 1000,
424                sd: 5.0,
425                cost: 10.0,
426            },
427            Stratum {
428                size: 500,
429                sd: 3.0,
430                cost: 30.0,
431            },
432        ];
433        let s2 = [
434            Stratum {
435                size: 1000,
436                sd: 2.0,
437                cost: 10.0,
438            },
439            Stratum {
440                size: 500,
441                sd: 9.0,
442                cost: 30.0,
443            },
444        ];
445        let v1 = allocate_for_budget(&s1, 2000.0).unwrap().variance;
446        let v2 = allocate_for_budget(&s2, 2000.0).unwrap().variance;
447        let m = allocate_multivariate(&sizes, &costs, &sd, &[v1, v2]).unwrap();
448        assert!(
449            m.attained[0] <= v1 * (1.0 + 1e-6),
450            "{} vs {v1}",
451            m.attained[0]
452        );
453        assert!(
454            m.attained[1] <= v2 * (1.0 + 1e-6),
455            "{} vs {v2}",
456            m.attained[1]
457        );
458        // each univariate solution costs 2000; meeting both must cost at least that
459        assert!(m.cost >= 2000.0 - costs[1]);
460        // and no cheaper integer allocation meets both targets (grid search)
461        let var = |n1: usize, n2: usize, jj: usize| -> f64 {
462            let a = |hh: usize| (sizes[hh] as f64).powi(2) * sd[hh * 2 + jj].powi(2);
463            let c = |hh: usize| sizes[hh] as f64 * sd[hh * 2 + jj].powi(2);
464            a(0) / n1 as f64 + a(1) / n2 as f64 - c(0) - c(1)
465        };
466        for n1 in 2..400usize {
467            for n2 in 2..200usize {
468                let c = 10.0 * n1 as f64 + 30.0 * n2 as f64;
469                if c < m.cost - 1e-9 && var(n1, n2, 0) <= v1 && var(n1, n2, 1) <= v2 {
470                    panic!(
471                        "cheaper feasible allocation ({n1}, {n2}) at cost {c} < {}",
472                        m.cost
473                    );
474                }
475            }
476        }
477        // a single variable reproduces the univariate allocation
478        let uni = allocate_for_variance(&s1, v1).unwrap();
479        let one = allocate_multivariate(&sizes, &costs, &[5.0, 3.0], &[v1]).unwrap();
480        assert_eq!(one.n, uni.n);
481        // a tiny target takes every unit
482        let all = allocate_multivariate(&sizes, &costs, &sd, &[1e-9, v2]).unwrap();
483        assert_eq!(all.n, vec![1000, 500]);
484        assert!(all.bounded);
485        assert!(allocate_multivariate(&sizes, &costs, &sd, &[v1]).is_err());
486    }
487
488    #[test]
489    fn budget_below_the_floor_is_refused_and_small_optima_are_flagged() {
490        let s = [Stratum {
491            size: 10,
492            sd: 1.0,
493            cost: 10.0,
494        }];
495        assert!(allocate_for_budget(&s, 5.0).is_err());
496        let a = allocate_for_budget(&s, 20.0).unwrap();
497        assert_eq!(a.n, vec![2]);
498        assert!(a.cost <= 20.0 + 1e-9);
499        // raw optimum 1.5 rounds to 2 and is reported as bounded
500        let one = [Stratum {
501            size: 100,
502            sd: 1.0,
503            cost: 1.0,
504        }];
505        let v = 100.0f64.powi(2) / 1.5 * (1.0 - 1.5 / 100.0);
506        let a = allocate_for_variance(&one, v).unwrap();
507        assert_eq!(a.n, vec![2]);
508        assert!(a.bounded);
509    }
510
511    #[test]
512    fn neyman_with_cost() {
513        let strata = vec![
514            Stratum {
515                size: 1000,
516                sd: 10.0,
517                cost: 1.0,
518            },
519            Stratum {
520                size: 1000,
521                sd: 10.0,
522                cost: 4.0,
523            },
524        ];
525        let a = allocate_for_variance(&strata, 1e6).unwrap();
526        // equal N and S: n_h proportional to 1 / sqrt(c_h) => ratio 2:1
527        assert!(
528            (a.n[0] as f64 / a.n[1] as f64 - 2.0).abs() < 0.1,
529            "{:?}",
530            a.n
531        );
532        assert!(a.variance <= 1e6 * 1.05);
533        let b = allocate_for_budget(&strata, a.cost).unwrap();
534        assert!((b.variance - a.variance).abs() / a.variance < 0.05);
535        assert!(
536            b.cost <= a.cost + 1e-9,
537            "cost {} exceeds budget {}",
538            b.cost,
539            a.cost
540        );
541        let c = allocate_for_budget(
542            &[
543                Stratum {
544                    size: 2000,
545                    sd: 12.0,
546                    cost: 40.0,
547                },
548                Stratum {
549                    size: 800,
550                    sd: 30.0,
551                    cost: 180.0,
552                },
553            ],
554            20000.0,
555        )
556        .unwrap();
557        assert!(c.cost <= 20000.0 && c.cost > 19600.0, "cost {}", c.cost);
558        assert!(allocate_for_variance(&strata, -1.0).is_err());
559        assert!(allocate_for_variance(
560            &[Stratum {
561                size: 1,
562                sd: 1.0,
563                cost: 1.0
564            }],
565            1.0
566        )
567        .is_err());
568    }
569
570    #[test]
571    fn full_strata_keep_the_target() {
572        // frame B is tiny and cheap: taken completely; the target must still hold
573        let strata = vec![
574            Stratum {
575                size: 680,
576                sd: 24.0,
577                cost: 103.0,
578            },
579            Stratum {
580                size: 100,
581                sd: 32.0,
582                cost: 45.0,
583            },
584        ];
585        let a = allocate_for_variance(&strata, 119_025.0).unwrap();
586        assert_eq!(a.n[1], 100);
587        assert!(
588            a.variance <= 119_025.0 * (1.0 + 1e-9),
589            "variance {}",
590            a.variance
591        );
592        assert!(a.bounded);
593        let b = allocate_for_budget(&strata, 20_000.0).unwrap();
594        assert!(b.cost <= 20_000.0 + 1e-9);
595        assert!(b.n[1] <= 100);
596    }
597
598    #[test]
599    fn bounds_are_reported() {
600        let strata = vec![Stratum {
601            size: 10,
602            sd: 100.0,
603            cost: 1.0,
604        }];
605        // a huge target variance would allow fewer than two units: bounded below at 2
606        let a = allocate_for_variance(&strata, 1e9).unwrap();
607        assert_eq!(a.n[0], 2);
608        assert!(a.bounded);
609        // a tiny target variance asks for the whole stratum: n = N, variance zero
610        let b = allocate_for_variance(&strata, 1e-6).unwrap();
611        assert_eq!(b.n[0], 10);
612        assert_eq!(b.variance, 0.0);
613    }
614}