The derivation of "optimal allocation" of sample sizes to different strata in stratified random sampling does not take into account the integrality, non-negativity and upper bound restrictions on the sample sizes. One of the consequences of this is that the formula at times requires more than 100% sampling in some strata. In this paper an exact integer programming formulation is proposed and an efficient method of finding optimal solution is given. An alternative method using incremental or marginal analysis approach is also given. A numerical example illustrating the non-optimality of the current procedures and the corresponding optimal solution obtained by the methods of the paper is also presented.