Title: Integer-valued algorithms for constrained optimal allocations in stratified sampling
Authors: Ulf Friedrich - Trier University (Germany) [presenting]
Ralf Muennich - University of Trier (Germany)
Sven de Vries - Trier University (Germany)
Matthias Wagner - Trier University (Germany)
Abstract: In stratified random sampling, minimizing the variance of a total estimate leads to the optimal allocation by Neyman and Tschuprow. This original method is in practice rarely appropriate since in many applications constraints on the sizes of certain strata have to be considered. Moreover, classical algorithms for this allocation problem yield real-valued rather than integer-valued solutions. When a rounding strategy is applied to obtain an integral solution, the rounded solution is not optimal in general and often infeasible. The integral allocation problem with upper and lower bounds is modeled as a separable and convex optimization problem and new algorithms are presented for its solution. The methods exploit the special polyhedral structure of the set of feasible allocations and share the important feature of computing the globally optimal, integral solution. It is proved that the problem is solvable in polynomial time complexity using these methods. Finally, the practical relevance is illustrated by solving numerical examples with several thousand strata and many constraints.