Heuristic algorithms and exact formulations applied to the problem of stratification of primary sampling units

Authors

  • José André de Moura Brito Instituto Brasileiro de Geografia e Estatística (IBGE), Rio de Janeiro, RJ, Brasil.
  • Gustavo Silva Semaan Universidade Federal Rural do Rio de Janeiro (UFRRJ), Três Rios, RJ, Brasil.

DOI:

https://doi.org/10.14488/1676-1901.v26i2.5713

Keywords:

Sampling, Clustering, Metaheuristics, Mathematical Programming, Optimization

Abstract

This article tackles the Primary Sampling Units Stratification Problem (PEUPA)—a complex real-world challenge—by formulating it as a Capacitated Clustering Problem. Several optimization approaches were developed and evaluated, including the Convex Hull Heuristic, four metaheuristics leveraging the Random-Key Optimizer framework (BRKGA, ILS, LNS, and VNS), a GRASP algorithm, and two Mathematical Programming formulations. Computational experiments on 30 real instances from the 2022 Demographic Census database, encompassing diverse problem sizes, were assessed through rigorous Hypothesis Testing, including the non-parametric Friedman Test and the pairwise Wilcoxon Test with Bonferroni Correction. The results consistently demonstrate that GRASP outperforms the other approaches, providing a stable, efficient, and practical solution for the PEUPA in statistical sampling applications.

Downloads

Download data is not yet available.

Author Biographies

José André de Moura Brito, Instituto Brasileiro de Geografia e Estatística (IBGE), Rio de Janeiro, RJ, Brasil.

Possui bacharelado em Matemática pela UFRJ, Mestrado e Doutorado em Engenharia de Sistemas e Computação (Otimização) pela COPPE/UFRJ e Pós-Doutorado em Otimização na Universidade Federal Fluminense. Atualmente é professor da Escola Nacional de Ciências e Estatística (ENCE/IBGE), onde leciona disciplinas na graduação. Também atua como pesquisador colaborador na Pós-Graduação do Instituto de Computação da Universidade Federal Fluminense. Tem experiência nas áreas de Otimização, Computação e Estatística, atuando principalmente nos seguintes temas: Metaheurísticas, Programação Inteira, Otimização Combinatória, Programação Não Diferenciável e Suavização, Análise de Algoritmos, Análise de Agrupamentos e Amostragem.

Gustavo Silva Semaan, Universidade Federal Rural do Rio de Janeiro (UFRRJ), Três Rios, RJ, Brasil.

Professor Associado da Universidade Federal Rural do Rio de Janeiro no Instituto Três Rios (ITR/UFRRJ) onde atua desde 2025. Foi professor da Universidade Federal Fluminense (UFF) (2014-2025). Coordenador de Curso da Computação no INF-UFF (2023-2025). Foi professor daAnhanguera / UNIPLI (2010-2013), UniAcademia / CESJF(2008-2010). Pós-doutorado realizado no Laboratório de Inteligência Computacional (LabIC), no Instituto de Computação (IC) da UFF. Doutor e Mestre em Computação pelo IC-UFF. Pós-graduado em Engenharia de Produção pela UniAmerica (2024). Pós-graduado em Ciência de Dados pela UniAmerica (2025). Bacharel em Sistemas de Informação pela Faculdade Metodista Granbery. Técnico em Informática Industrial pela Universidade Federal de Juiz de Fora (CTU-UFJF). Duas vezes indicado ao Prêmio de Excelência em Docência UFF (19 e 22). Professor homenageado em todas as instituições que foi docente: UFF, Anhanguera(UNIPLI), Centro Universitário UniAcademia (CES-JF). Paraninfo ou patrono de todas as turmas da Licenciatura em Computação durante o tempo que foi docente na UFF (8 turmas: 15, 16, 17, 18, 19, 23, 24 e duas turmas em 25). Homenagem: Membro Honorário do Diretório Acadêmico Alan Turing em 22 (INFES/UFF). Projetos de Pesquisa(proponente): FOPESQ/UFF (21-23) e (17-19); Projetos PIBIC (ENCE/IBGE) (início 25),(24-25) e (20-21); FAPERJ IC (17-18) e (14-15); FAPERJ INST(16-18); FOPIN IC (15-16); PIBIC UFF(14-15). Extensão(proponente): Edital de Fluxo Contínuo EExt/UFRRJ (início 26), FAPERJ Jovens Talentos (19-20) e (20-21). Projetos de Pesquisa(colaborador): Projeto CNPq Universal (início 25),(22-25),(2010) e (2007); CNPq CT-INFO (2007), e FAPERJ Pensa Rio (07-10). Membro do Laboratório de Inteligência Computacional (LabIC) desde 2006. Atua com análise e desenvolvimento de sistemas desde 2001, e como professor no magistério superior desde 2008.

References

ALBIERI, S.; DIAS, A. J. R.(orgs.). 40 anos da unidade de métodos estatísticos do IBGE: alguns passos. Rio de Janeiro: IBGE, Coordenação de Métodos e Qualidade, 2017. 216 p. (Documentos para Disseminação. Memória Institucional, 22). ISBN 978-85-240-4430-4.

BATISTA, A.S.; FRANÇA, K.C.B.; BERDET, M.; PINTO, M.A.B. Metropolização, homicídios e segurança pública na área metropolitana de Brasília: o município de Águas Lindas de Goiás. Sociedade & Estado, Brasília, v. 31, n. 2, p. 433-457, 2016.

BISPO DOS SANTOS, J. A importância das informações estatísticas do Censo do IBGE 2022 para a gestão das políticas públicas no município de Irará (Bahia); RECIMA21 - Revista Científica Multidisciplinar, v. 6, n. 3, 2025.

BRITO, J. A. M.; BRITO, L. R. Algoritmos VNS e genéticos aplicados ao problema de agrupamento com soma mínima de distâncias. In: Anais do XL Simpósio Brasileiro de Pesquisa Operacional. João Pessoa: Sociedade Brasileira de Pesquisa Operacional, 2008. p. 1150–1161.

BRITO, J. A. M.; MONTENEGRO, F. M. T.; FREITAS, M. P. S. Algoritmos de otimização aplicados à estratificação da amostra mestra. In Anais da III Escola de Amostragem e Metodologia de Pesquisa - ESAMP, Juiz de Fora, 2011.

BOLFARINE, H.; BUSSAB, W. O. Elementos de amostragem. 1. ed. São Paulo: Blucher, 2005. 290 p.

CHAOVALITWONGSE, W. A.; ANDROULAKIS, I. P.; PARDALOS, P. M. Quadratic integer programming: complexity and equivalent forms. In: FLOUDAS, C.; PARDALOS, P. (eds.). Encyclopedia of Optimization. Boston: Springer, 2008.

CHAVES, A. A.; RESENDE, M. G. C.; SCHUETZ, M. J. A.; BRUBAKER, J. K.; KATZGRABER, H. G.; ARRUDA, E. F.; SILVA, R. M. A. A random-key optimizer for combinatorial optimization. arXiv preprint arXiv:2411.04293, 2024.

COCHRAN, W. G. Sampling Techniques. 3. ed. New York: John Wiley & Sons, 1977.

CONFORTI, M.; CORNUÉJOLS, G.; ZAMBELLI, G. Integer programming. Cham: Springer International Publishing, 2014. 787 p.

CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R.L.; STEIN, C. Introduction to Algorithms. 4. ed. Cambridge (MA): The MIT Press, 2022.

DEPARTAMENTO ADMINISTRATIVO NACIONAL DE ESTADÍSTICA (DANE). Metodología general gran encuesta integrada de hogares (GEIH). Documento metodológico. Bogotá: DANE, 2016.

FRANK, M.; WOLFE, P. An algorithm for quadratic programming. Naval Research Logistics Quarterly, v. 3, n. 1-2, p. 95-110, 1956.

GARCIA, R.P.; DE LIMA, B.S.L.P.; LEMONGE, A.C.C.; JACOB, B.P. An enhanced surrogate-assisted differential evolution for constrained optimization problems. Soft Computing, v. 27, p. 6391-6414, 2023.

GASPAR-CUNHA, A.; TAKAHASHI, R. H. C.; ANTUNES, C. H. Manual de computação evolutiva e meta-heurística. Belo Horizonte: UFMG, 2013.

GENDREAU, M.; POTVIN, J.-Y. Handbook of metaheuristics. 2. ed. New York: Springer, 2010.

GIBBONS, J. D.; CHAKRABORTI, S. Nonparametric statistical inference. Statistics: A Series of Textbooks and Monographs. 6. ed. Boca Raton: Chapman and Hall/CRC, 2020.

GUIGNARD, M.; AHLATCIOGLU, A. The convex hull heuristic for nonlinear integer programming problems with linear constraints and application to quadratic 0-1 problems. Journal of Heuristics, 27(1): 251–26, 2021.

HANSEN, P.; JAUMARD, B. Cluster analysis and mathematical programming. Mathematical Programming, v. 79, p. 191-215, 1997.

HOLLANDER, M.; WOLFE, D. A.; CHICKEN, E. Nonparametric Statistical Methods. 3rd ed. Hoboken: John Wiley & Sons, 2014.

IBGE. Amostra Mestra Para o Sistema Integrado de Pesquisas Domiciliares: IBGE, 2007. (Textos para Discussão - Diretoria de Pesquisas, n. 23).

IBGE. Pesquisa Nacional por Amostra de Domicílios Contínua Notas técnicas Versão 1.15: IBGE, 2023. (Notas técnicas, n. 1.15).

JIAO, L. C.; LI, L.; SHANG, R. H.; LIU, F.; STOLKIN, R. A novel selection evolutionary strategy for constrained optimization. Information Sciences, Amsterdam, v. 239, n. 1, p. 122-141, 2013. DOI: 10.1016/j.ins.2013.03.002.

LEE, J.; LEYFFER, S. (eds.). Mixed integer nonlinear programming. v. 154. IMA Volumes in Mathematics and its Applications. New York: Springer, 2012.

LEVIN, M. Sh. Capacitated Clustering Problem. Journal of Communications Technology and Electronics, v. 69, n. 1, p. 118-127, 2024.

LOHR, S. L. Sampling - Design and Analysis. New York: Chapman and Hall/CRC, 2021.

LÓPEZ-IBÁÑEZ, M.; DUBOIS-LACOSTE, J.; PÉREZ CÁCERES, L.; BIRATTARI, M.; STÜTZLE, T. G. The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, Amsterdam, v. 3, p. 43-58, 2016.

MALAGUTI, J. G.; ALVES, P. Amostra mestra do Sistema Integrado de Pesquisas Domiciliares Nacional: revisão e discussão das propostas de atualização. Ciência & Saúde Coletiva, Rio de Janeiro, v. 29, e03712024, 2024. DOI: 10.1590/1413-812320242911.03712024.

MARTINEZ-GAVARA, A.; LANDA-SILVA, D.; CAMPOS, V.; MARTÍ, R.. Randomized heuristics for the capacitated clustering problem. Information Sciences, 417:154–168, 2017.

MARTÍ, R.l; PARDALOS, P.M.; RESENDE, M.G.C. (eds.). Handbook of Heuristics. Cham: Springer, 2018. ISBN 978-3-319-07123-7 (impresso); ISBN 978-3-319-07124-4 (e-book).

MENDES, B. G. A investigação da saúde nos censos demográficos do Brasil: possibilidades de análise, vantagens e limitações. Boletim do Instituto de Saúde – BIS, São Paulo, v. 16, n. 2, p. 6–14, 2015.

MONTENEGRO, F. M. T.; TORREÃO, J. R. A.; MACULAN, N. Microcanonical optimization algorithm for the Euclidean Steiner problem in R^nwith application to phylogenetic inference. Physical Review E, v. 68, n. 5, 2003.

MUIÑOS, R. Muestra maestra urbana de viviendas de la República Argentina MMUVRA 2011. [S.l.], 2018. (Reunión del Grupo de Trabajo sobre Encuestas a Hogares de la Conferencia Estadística de las Américas). Disponível em: https://biblioteca.indec.gob.ar/bases/minde/2mi600.pdf. Acesso em: jun. 2025.

MULVEY, J. M.; BECK, M.P. Solving capacitated clustering problems. European Journal of Operational Research, 18:339–348, 1984.

NASCIMENTO, M. C.; TOLEDO, F.M.; DE CARVALHO, A.C. Investigation of a new GRASP-based clustering algorithm applied to biological data. Computers & Operations Research, v. 37, n. 8, p. 1381-1388, 2010.

NEGREIROS, M.; MACULAN, N.; PALHANO, W.C.; Muritiba, A.E.F.; BATISTA, P.L.F.. Capacitated Clustering Models to Real-Life Applications. In: IntechOpen: IntechOpen, 2022. Disponível em: 10.5992/intechopen.1000213. Acesso em: 15 out. 2025.

RESENDE, M.G.C.; RIBEIRO, C.C. Optimization by GRASP: Greedy Randomized Adaptive Search Procedures. New York: Springer, 2016.

SERPA, D. R. Abordagens heurísticas para problemas de agrupamentos. Dissertação (Mestrado) — Instituto Nacional de Pesquisas Espaciais (INPE), São José dos Campos, 2011.

TOSI, D.; KOKAJ, R.; ROCCETTI, M. 15 years of big data: a systematic literature review. Journal of Big Data, v. 11, art. 73, 2024.

VON HOHENBALKEN, B. Simplicial decomposition in nonlinear programming algorithms. Mathematical Programming, v. 13, p. 49-68, 1977.

WOLSEY, L. A. Integer Programming. New York: Wiley-Interscience, 1998.

YAGI, P. A.; QUIROZ, E. A. P.; LENGUA, M. A. C. A systematic literature review on quadratic programming. In: Proceedings of the 7th International Congress on Information and Communication Technology (ICICT 2022). Singapore: Springer Nature, 2022. p. 739–747.

ZHOU, Q.; BENLIC, U.; WU, Q.; HAO, J. Heuristic search to the capacitated clustering problem. European Journal of Operational Research, v. 275, p. 123-139, 2018.

Downloads

Published

2026-07-07

How to Cite

Brito, J. A. de M., & Semaan, G. S. (2026). Heuristic algorithms and exact formulations applied to the problem of stratification of primary sampling units. Revista Produção Online, 26(2), 5713 . https://doi.org/10.14488/1676-1901.v26i2.5713

Issue

Vol. 26 No. 2 (2026): Fluxo contínuo

Section

Papers

License

Copyright (c) 2026 Revista Produção Online

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The Journal reserves the right to make spelling and grammatical changes, aiming to keep a default language, respecting, however, the style of the authors.

The published work is responsibility of the (s) author (s), while the Revista Produção Online is only responsible for the evaluation of the paper. The Revista Produção Online is not responsible for any violations of Law No. 9.610 / 1998, the Copyright Act.

The journal allows the authors to keep the copyright of accepted articles, without restrictions


 
This work is licensed under a Creative Commons License .