Nonlinear integer programming for optimal allocation in stratified sampling

A stratified random sampling plan is one in which the elements of the population are first divided into nonoverlapping groups, and then a simple random sample is selected from each group. In this paper, we focus on determining the optimal sample size of each group. We show that various versions of this problem can be transformed into a particular nonlinear program with a convex objective function, a single linear constraint, and bounded variables. Two branch and bound algorithms are presented for solving the problem. The first algorithm solves the transformed subproblems in the branch and bound tree using a variable pegging procedure. The second algorithm solves the subproblems by performing a search to identify the optimal Lagrange multiplier of the single constraint. We also present linearization and dynamic programming methods that can be used for solving the stratified sampling problem. Computational testing indicates that the pegging branch and bound algorithm is fastest for some classes of problems, and the linearization method is fastest for other classes of problems.