IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v92y2015icp1-12.html
   My bibliography  Save this article

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

Author

Listed:
  • Friedrich, Ulf
  • Münnich, Ralf
  • de Vries, Sven
  • Wagner, Matthias

Abstract

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.

Suggested Citation

  • Friedrich, Ulf & Münnich, Ralf & de Vries, Sven & Wagner, Matthias, 2015. "Fast integer-valued algorithms for optimal allocations under constraints in stratified sampling," Computational Statistics & Data Analysis, Elsevier, vol. 92(C), pages 1-12.
    • Handle: RePEc:eee:csdana:v:92:y:2015:i:c:p:1-12
    DOI: 10.1016/j.csda.2015.06.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0167947315001413
    Download Restriction: Full text for ScienceDirect subscribers only.
    File URL: https://libkey.io/10.1016/j.csda.2015.06.003?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Dorit S. Hochbaum, 1994. "Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems," Mathematics of Operations Research, INFORMS, vol. 19(2), pages 390-409, May.
    2. Ralf Münnich & Ekkehard Sachs & Matthias Wagner, 2012. "Numerical solution of optimal allocation problems in stratified sampling under box constraints," AStA Advances in Statistical Analysis, Springer;German Statistical Society, vol. 96(3), pages 435-450, July.
    3. Burgard, Jan Pablo & Münnich, Ralf T., 2012. "Modelling over and undercounts for design-based Monte Carlo studies in small area estimation: An application to the German register-assisted census," Computational Statistics & Data Analysis, Elsevier, vol. 56(10), pages 2856-2863.
    4. Horst Stenger & Siegfried Gabler, 2005. "Combining random sampling and census strategies - Justification of inclusion probabilities equal to 1," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 61(2), pages 137-156, April.
    5. Bernard O. Koopman, 1953. "The Optimum Distribution of Effort," Operations Research, INFORMS, vol. 1(2), pages 52-63, February.
    6. Lalitha Sanathanan, 1971. "On an Allocation Problem with Multistage Constraints," Operations Research, INFORMS, vol. 19(7), pages 1647-1663, December.
    7. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.
    8. Valliant, Richard & Gentle, James E., 1997. "An application of mathematical programming to sample allocation," Computational Statistics & Data Analysis, Elsevier, vol. 25(3), pages 337-360, August.
    9. Carrizosa, Emilio & Romero Morales, Dolores, 2007. "A biobjective method for sample allocation in stratified sampling," European Journal of Operational Research, Elsevier, vol. 177(2), pages 1074-1089, March.
    10. Bretthauer, Kurt M. & Ross, Anthony & Shetty, Bala, 1999. "Nonlinear integer programming for optimal allocation in stratified sampling," European Journal of Operational Research, Elsevier, vol. 116(3), pages 667-680, August.
    11. Giovanni Maria Giorgi, 2010. "Book reviews. Prevost "A total science: statistics in liberal and fascist Italy"," Metron - International Journal of Statistics, Dipartimento di Statistica, Probabilità e Statistiche Applicate - University of Rome, vol. 0(1), pages 105-110.
    12. Ralf Münnich & Jan Burgard & Martin Vogt, 2013. "Small Area-Statistik: Methoden und Anwendungen," AStA Wirtschafts- und Sozialstatistisches Archiv, Springer;Deutsche Statistische Gesellschaft - German Statistical Society, vol. 6(3), pages 149-191, March.
    13. K. S. Srikantan, 1963. "A Problem in Optimum Allocation," Operations Research, INFORMS, vol. 11(2), pages 265-273, April.
    14. Siegfried Gabler & Matthias Ganninger & Ralf Münnich, 2012. "Optimal allocation of the sample size to strata under box constraints," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 75(2), pages 151-161, February.
    15. Groenevelt, H., 1991. "Two algorithms for maximizing a separable concave function over a polymatroid feasible region," European Journal of Operational Research, Elsevier, vol. 54(2), pages 227-236, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. repec:csb:stintr:v:17:y:2016:i:1:p:25-40 is not listed on IDEAS
    2. Ravichandran Arun & Pashley Nicole E. & Dasgupta Tirthankar & Libgober Brian, 2024. "Optimal allocation of sample size for randomization-based inference from 2K factorial designs," Journal of Causal Inference, De Gruyter, vol. 12(1), pages 1-18, January.
    3. M. G. M. Khan & Jacek Wesołowski, 2019. "Neyman-type sample allocation for domains-efficient estimation in multistage sampling," AStA Advances in Statistical Analysis, Springer;German Statistical Society, vol. 103(4), pages 563-592, December.
    4. Jan Pablo Burgard & Ralf Münnich & Martin Rupp, 2020. "Qualitätszielfunktionen für stark variierende Gemeindegrößen im Zensus 2021 [Quality measures respecting highly varying community sizes within the 2021 German Census]," AStA Wirtschafts- und Sozialstatistisches Archiv, Springer;Deutsche Statistische Gesellschaft - German Statistical Society, vol. 14(1), pages 5-65, March.
    5. Martijn H. H. Schoot Uiterkamp & Marco E. T. Gerards & Johann L. Hurink, 2022. "On a Reduction for a Class of Resource Allocation Problems," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1387-1402, May.
    6. Ralf Münnich & Jan Pablo Burgard & Siegfried Gabler & Matthias Ganninger & Jan-Philipp Kolb, 2016. "Small Area Estimation In The German Census 2011," Statistics in Transition New Series, Polish Statistical Association, vol. 17(1), pages 25-40, March.
    7. Wesołowski Jacek, 2019. "Multi-Domain Neyman-Tchuprov Optimal Allocation," Statistics in Transition New Series, Polish Statistical Association, vol. 20(4), pages 1-12, December.
    8. Münnich Ralf & Burgard Jan Pablo & Gabler Siegfried & Ganninger Matthias & Kolb Jan-Philipp, 2016. "Small Area Estimation in the German Census 2011," Statistics in Transition New Series, Polish Statistical Association, vol. 17(1), pages 25-40, March.
    9. Jacek Wesołowski, 2019. "Multi-Domain Neyman-Tchuprov Optimal Allocation," Statistics in Transition New Series, Polish Statistical Association, vol. 20(4), pages 1-12, December.
    10. Ralf Münnich & Siegfried Gabler & Christian Bruch & Jan Pablo Burgard & Tobias Enderle & Jan-Philipp Kolb & Thomas Zimmermann, 2015. "Tabellenauswertungen im Zensus unter Berücksichtigung fehlender Werte," AStA Wirtschafts- und Sozialstatistisches Archiv, Springer;Deutsche Statistische Gesellschaft - German Statistical Society, vol. 9(3), pages 269-304, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Patriksson, Michael, 2008. "A survey on the continuous nonlinear resource allocation problem," European Journal of Operational Research, Elsevier, vol. 185(1), pages 1-46, February.
    2. Martijn H. H. Schoot Uiterkamp & Marco E. T. Gerards & Johann L. Hurink, 2022. "On a Reduction for a Class of Resource Allocation Problems," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1387-1402, May.
    3. Zeyang Wu & Kameng Nip & Qie He, 2021. "A New Combinatorial Algorithm for Separable Convex Resource Allocation with Nested Bound Constraints," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1197-1212, July.
    4. Ralf Münnich & Siegfried Gabler & Christian Bruch & Jan Pablo Burgard & Tobias Enderle & Jan-Philipp Kolb & Thomas Zimmermann, 2015. "Tabellenauswertungen im Zensus unter Berücksichtigung fehlender Werte," AStA Wirtschafts- und Sozialstatistisches Archiv, Springer;Deutsche Statistische Gesellschaft - German Statistical Society, vol. 9(3), pages 269-304, December.
    5. Jan Pablo Burgard & Ralf Münnich & Martin Rupp, 2019. "A Generalized Calibration Approach Ensuring Coherent Estimates with Small Area Constraints," Research Papers in Economics 2019-10, University of Trier, Department of Economics.
    6. Patriksson, Michael & Strömberg, Christoffer, 2015. "Algorithms for the continuous nonlinear resource allocation problem—New implementations and numerical studies," European Journal of Operational Research, Elsevier, vol. 243(3), pages 703-722.
    7. M. G. M. Khan & Jacek Wesołowski, 2019. "Neyman-type sample allocation for domains-efficient estimation in multistage sampling," AStA Advances in Statistical Analysis, Springer;German Statistical Society, vol. 103(4), pages 563-592, December.
    8. Ralf Münnich & Jan Pablo Burgard & Siegfried Gabler & Matthias Ganninger & Jan-Philipp Kolb, 2016. "Small Area Estimation In The German Census 2011," Statistics in Transition New Series, Polish Statistical Association, vol. 17(1), pages 25-40, March.
    9. Lee, Zu-Hsu & Deng, Shiming & Lin, Beixin & Yang, James G.S., 2010. "Decision model and analysis for investment interest expense deduction and allocation," European Journal of Operational Research, Elsevier, vol. 200(1), pages 268-280, January.
    10. Sathaye, Nakul & Madanat, Samer, 2011. "A bottom-up solution for the multi-facility optimal pavement resurfacing problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(7), pages 1004-1017, August.
    11. Carrizosa, Emilio, 2010. "Unequal probability sampling from a finite population: A multicriteria approach," European Journal of Operational Research, Elsevier, vol. 201(2), pages 500-504, March.
    12. Allafi, Sabine & Lohn, Alexandra & Nölting, Christopher & Maier, Alexander, 2022. "Die neue Strukturstatistik im Handels- und Dienstleistungsbereich," WISTA – Wirtschaft und Statistik, Statistisches Bundesamt (Destatis), Wiesbaden, vol. 74(5), pages 22-31.
    13. repec:csb:stintr:v:17:y:2016:i:1:p:25-40 is not listed on IDEAS
    14. Bretthauer, Kurt M. & Shetty, Bala, 2002. "The nonlinear knapsack problem - algorithms and applications," European Journal of Operational Research, Elsevier, vol. 138(3), pages 459-472, May.
    15. Ralf Münnich, 2013. "Vorwort des Herausgebers," AStA Wirtschafts- und Sozialstatistisches Archiv, Springer;Deutsche Statistische Gesellschaft - German Statistical Society, vol. 7(3), pages 101-103, December.
    16. Calinescu, Melania & Bhulai, Sandjai & Schouten, Barry, 2013. "Optimal resource allocation in survey designs," European Journal of Operational Research, Elsevier, vol. 226(1), pages 115-121.
    17. ten Eikelder, S.C.M. & van Amerongen, J.H.M., 2023. "Resource allocation problems with expensive function evaluations," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1170-1185.
    18. Thomas Zimmermann, 2019. "Einsatzmöglichkeiten von Small Area-Verfahren bei Kohortenschätzungen im Zensus 2021 [Applicablity of small area estimation methods for demographic cohorts in the Census 2021]," AStA Wirtschafts- und Sozialstatistisches Archiv, Springer;Deutsche Statistische Gesellschaft - German Statistical Society, vol. 13(2), pages 157-177, September.
    19. Zhang, Bin & Hua, Zhongsheng, 2008. "A unified method for a class of convex separable nonlinear knapsack problems," European Journal of Operational Research, Elsevier, vol. 191(1), pages 1-6, November.
    20. Münnich Ralf & Burgard Jan Pablo & Gabler Siegfried & Ganninger Matthias & Kolb Jan-Philipp, 2016. "Small Area Estimation in the German Census 2011," Statistics in Transition New Series, Polish Statistical Association, vol. 17(1), pages 25-40, March.
    21. Thijs Klauw & Marco E. T. Gerards & Johann L. Hurink, 2017. "Resource allocation problems in decentralized energy management," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(3), pages 749-773, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:csdana:v:92:y:2015:i:c:p:1-12. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/csda .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.