Limite Superior para o Problema da Diversidade Máxima
Resumo
Aplicamos a t–linearização ao modelo quadrático 0−1 natural para o problema da diversidade máxima. Comparamos computacionalmente o modelo obtido com duas outras formulações lineares da literatura. Experimentos computacionais mostram que a t–linearização gera em média menos restrições que as formulações, além de conseguir alcançar um limite superior mais apertado em todas as instâncias usadas. Por outro lado, uma das formulações consegue ser ligeiramente mais rápida na obtenção dos limites.
Referências
Balas, E. (1964). Extension de l’algorithme additif à la programmation en nombres entiers et à la programmation non linéaire. Comptes Rendus Hebdomadaires des Seances de L’Academie des Sciences, 258(21):5136–5139.
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
Glover, F. (1975). Improved linear integer programming formulations of nonlinear integer problems. Management Science, 22(4):455–460.
Glover, F. and Woolsey, E. (1974). Converting the 0-1 polynomial programming problem to a 0-1 linear program. Operations research, 22(1):180–182.
Hammer, P. L. and Rudeanu, S. (1968). Boolean Methods in Operations Research. Springer-Verlag.
Hu, T. C. (1969). Integer programming and network flows.
Kuo, C.-C., Glover, F., and Dhir, K. S. (1993). Analyzing and modeling the maximum diversity problem by zero-one programming. Decision Sciences, 24(6):1171–1185.
Martí, R., Gallego, M., Duarte, A., and Pardo, E. G. (2013). Heuristics and metaheuristics for the maximum diversity problem. Journal of Heuristics, 19(4):591–615.
Rodrigues, C., Quadri, D., Michelon, P., and Gueye, S. (2012). 0-1 quadratic knapsack problems: an exact approach based on a t-linearization. SIAM Journal on Optimization, 22(4):1449–1468.
Rodrigues, C. D. (2010). Abordagens híbridas na solução de problemas de programação inteira da teoria e prática. PhD thesis, Universidade Federal do Ceará e Université d’Avignon.
Soares, P., Campêlo, M., Rodrigues, C. D., and Michelon, P. (2017). t-linearizalização de funções quadráticas de variáveis binárias. Anais do XLIX SBPO.
Zhou, Y., Hao, J.-K., and Duval, B. (2017). Opposition-based memetic search for the maximum diversity problem. IEEE Transactions on Evolutionary Computation, 21(5):731–745.
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
Glover, F. (1975). Improved linear integer programming formulations of nonlinear integer problems. Management Science, 22(4):455–460.
Glover, F. and Woolsey, E. (1974). Converting the 0-1 polynomial programming problem to a 0-1 linear program. Operations research, 22(1):180–182.
Hammer, P. L. and Rudeanu, S. (1968). Boolean Methods in Operations Research. Springer-Verlag.
Hu, T. C. (1969). Integer programming and network flows.
Kuo, C.-C., Glover, F., and Dhir, K. S. (1993). Analyzing and modeling the maximum diversity problem by zero-one programming. Decision Sciences, 24(6):1171–1185.
Martí, R., Gallego, M., Duarte, A., and Pardo, E. G. (2013). Heuristics and metaheuristics for the maximum diversity problem. Journal of Heuristics, 19(4):591–615.
Rodrigues, C., Quadri, D., Michelon, P., and Gueye, S. (2012). 0-1 quadratic knapsack problems: an exact approach based on a t-linearization. SIAM Journal on Optimization, 22(4):1449–1468.
Rodrigues, C. D. (2010). Abordagens híbridas na solução de problemas de programação inteira da teoria e prática. PhD thesis, Universidade Federal do Ceará e Université d’Avignon.
Soares, P., Campêlo, M., Rodrigues, C. D., and Michelon, P. (2017). t-linearizalização de funções quadráticas de variáveis binárias. Anais do XLIX SBPO.
Zhou, Y., Hao, J.-K., and Duval, B. (2017). Opposition-based memetic search for the maximum diversity problem. IEEE Transactions on Evolutionary Computation, 21(5):731–745.
Publicado
26/07/2018
Como Citar
SOARES, Pablo Luiz B.; CAMPÊLO, Manoel.
Limite Superior para o Problema da Diversidade Máxima. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 5-8.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3138.
