Algoritmos heurísticos e formulações exatas aplicados ao Problema de estratificação de unidades primárias de amostragem

Autores

  • 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

Palavras-chave:

Amostragem, Agrupamento, Metaheurísticas, Programação Matemática, Otimização

Resumo

Este artigo investiga o Problema de Estratificação de Unidades Primárias de Amostragem (PEUPA), um caso real e de elevada complexidade computacional, formulado como um Problema de Agrupamento Capacitado. Foram desenvolvidas e avaliadas múltiplas abordagens de otimização, incluindo a Heurística da Envoltória Convexa, quatro metaheurísticas baseadas no Otimizador de Chaves Aleatórias (BRKGA, ILS, LNS e VNS), um algoritmo GRASP e duas formulações de Programação Matemática. Experimentos computacionais conduzidos com 30 instâncias reais do Censo Demográfico 2022, de diferentes portes, foram analisados por meio de Testes de Hipóteses — especificamente, o Teste de Friedman (não paramétrico) e o Teste de Wilcoxon pareado com Correção de Bonferroni —, revelando diferenças estatisticamente significativas entre as abordagens. Os resultados demonstram a superioridade e a estabilidade do GRASP frente às demais técnicas, consolidando-o como uma solução eficiente e promissora para a resolução do PEUPA em contextos práticos de amostragem estatística.

Downloads

Não há dados estatísticos.

Biografia do Autor

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.

Referências

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

Publicado

07-07-2026

Como Citar

Brito, J. A. de M., & Semaan, G. S. (2026). Algoritmos heurísticos e formulações exatas aplicados ao Problema de estratificação de unidades primárias de amostragem . Revista Produção Online, 26(2), 5713 . https://doi.org/10.14488/1676-1901.v26i2.5713

Edição

v. 26 n. 2 (2026): Fluxo contínuo

Seção

Artigos

Licença

Copyright (c) 2026 Revista Produção Online

Creative Commons License
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.

A Revista se reserva no direito de efetuar, no artigo publicado, alterações de ordem normativa, ortográfica e gramatical, com vistas a manter o padrão culto da língua, respeitando, porém, o estilo dos autores.

A obra publicada é de inteira responsabilidade do(s) autor(es), cabendo à Revista Produção Online apenas a avaliação da obra, na qualidade de veículo de publicação científica. A Revista Produção Online não se responsabiliza por eventuais violações à Lei nº 9.610/1998, Lei de Direito Autoral.

A revista Produção Online permite que o autor detenha o copyright dos artigos aceitos para publicação, sem restrições.

Esta obra está licenciada sob uma Licença Creative Commons.