Fast integer-valued algorithms for optimal allocations under constraints in stratified sampling

In stratified random sampling, minimizing the variance of a total estimate leads to the optimal allocation. However, in practice, this original method is scarcely appropriate since in many applications additional constraints have to be considered. Three optimization algorithms are presented that solve the integral allocation problem with upper and lower bounds. All three algorithms exploit the fact that the feasible region is a polymatroid and share the important feature of computing the globally optimal integral solution, which generally differs from a solution obtained by rounding. This is in contrast to recent references which, in general, treat the continuous relaxation of the optimization problem. Two algorithms are of polynomial complexity and all of them are fast enough to be applied to complex problems such as the German Census 2011 allocation problem with almost 20,000 strata.