Periodicity.: Special Edition IFLOG-2016, July - 2017
e-ISSN......: 2236-269X
Cover Image

Metaheuristic ILS with path relinking for the number partitioning problem

Cesar Augusto Souza de Oliveira, William de Paula Ferreira, Reinaldo Carlos Mendes, Gleisson de Assis, Marcone Jamilson Freitas Souza

Abstract


This study brings an implementation of a metaheuristic procedure to solve the Number Partitioning Problem (NPP), which is a classic NP-hard combinatorial optimization problem. The presented problem has applications in different areas, such as: logistics, production and operations management, besides important relationships with other combinatorial problems. This paper aims to perform a comparative analysis between the proposed algorithm with others metaheuristics using a group of instances available on the literature. Implementations of constructive heuristics, local search and metaheuristics ILS with path relinking as mechanism of intensification and diversification were made in order to improve solutions, surpassing the others algorithms.

Keywords


Number Partitioning Problem; NPP; metaheuristics; path relinking; combinatorial Optimization

Full Text:

PDF HTML

References


ARAGON, C. R.; JOHNSON, D.; MCGEOCH, L.; SCHEVON, C. (1991) Optimization by simulated annealing: An experimental evaluation; part ii, graph coloring and number partitioning. Operations Research, v. 39, n. 3, p. 378–406.

ARGÜELLO, M. F.; FEO, T. A.; GOLDSCHMIDT, O. (1996) Randomized methods for the number partitioning problem. Computers & Operations Research, v. 23, n. 2, p. 103–111.

BERRETTA, R.; MOSCATO, P. (1999) The number partitioning problem: an open challenge for evolutionary computation? In New ideas in optimization. McGraw-Hill Ltd., UK, p. 261-278.

CITESEER. KARP, R. M. (1972) Reducibility among combinatorial problems. Springer.

COOK, S. A. (1971) The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing, n. 15, p. 1–158. ACM.

ARAUJO, S. A.; CONSTANTINO, A. A.; MENDONÇA NETO, C. F. X. (2004) Meta-heurísticaspara o problema de partição de números. XXXVI – SBPO. São João del-Rei.

DIAZ, A.; GLOVER, F.; GHAZIRI, H.; GONZÁLEZ, J.; LAGUNA, M.; MOSCATO, P.; AND TSENG, F. (1996) Optimización heurıstica y redes neuronales. Editorial Paraninfo, n. 235, p. 158–159.

DUCHA, F. A.; DE SOUZA, S. R. (2013) Algorithms analysis for the number partition problem. XXXIV CILAMCE.

DUCHA, F. A. (2014) Algoritmos e modelos para solução do problema de partição de números. Dissertation (Master in Mathematical and Computational Modeling). Belo Horizonte: MMC/CEFET-MG, Available at: http://www.files.scire.net.br/atrio/cefet-mg-ppgmmc_upl/THESIS/193/fernando_andrade_ducha.pdf. Access: 22/12/2016.

GAREY, M. R.; JOHNSON, D. S. (1979) Computers and intractability: a guide to the theory of np-completeness. San Francisco, LA: Freeman.

GENT, I. P.; WALSH, T. (1995) The number partition phase transition. Department of Computer Science, University of Strathclyde.

H. W. CORLEY; ROBERTA JR., S. D. (1972) A Partitioning Problem with Applications in Regional Design. Operations Research, v. 20, n. 5 (Sep. - Oct.), p. 1010-1019.

HOFFMAN, K.; PADBERG, M. (2008) Set covering, packing and partitioning problems Set Covering, Packing and Partitioning Problems. Encyclopedia of Optimization, Springer US, p. 3482-3486.

LARSEN J. Set Partitioning and Applications. Available at: http://www2.imm.dtu.dk/courses/02735/sppintro.pdf. Access: 09/10/2016.

MACDONALD, P. (1976) Combinatorial Programming: Methods and Applications. Journal of the Operational Research Society, v. 27, n. 3, p. 640-640.

PEDROSO, J. P.; KUBO, M. (2010) Heuristics and exact methods for number partitioning. European Journal of Operational Research, v. 202, n. 1, p. 73-81.

PERCUS, A.; ISTRATE, G.; MOORE, C. (2006) Computational complexity and statistical physics. Oxford University Press..

STADLER, P. F.; HORDIJK, W.; FONTANARI, J. F. (2003) Phase transition and landscape statistics of the number partitioning problem. Physical Review, v. 67, n. 5, p. 056701.




DOI: http://dx.doi.org/10.14807/ijmp.v8i5.597

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 Cesar Augusto Souza de Oliveira, William de Paula Ferreira, Reinaldo Carlos Mendes, Gleisson de Assis, Marcone Jamilson Freitas Souza

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

LIBRARIES BY

Logo Gaudeamus

Logo INDIANA

Logo CHENG KUNG

Logo UTEP

Logo MOBIUS

Logo UNIVEM

Logo Kennedy

Logo Columbia

Logo UCS

Logo MSG/UFF

Logo OPT

Logo Biblioteca Professor Milton Cabral Moreira

Logo UFL

Logo ULRICHSWEB

Logo UNISA