Metaheuristic ILS with path relinking for the number partitioning problem

Article Sidebar

PDF HTML
Published: Jul 1, 2017
DOI: https://doi.org/10.14807/ijmp.v8i5.597
Keywords:
Number Partitioning Problem NPP metaheuristics path relinking combinatorial Optimization

Main Article Content

Cesar Augusto Souza de Oliveira
Federal Center for Technological Education (CEFET-MG)
William de Paula Ferreira
Industrial Engineering at University of Sao Paulo (PPGEP / Poli-USP); Federal Institute of Education, Science and Technology of Sao Paulo (IFSP) Campus Suzano
Reinaldo Carlos Mendes
Federal Center for Technological Education of Minas Gerais (CEFET-MG)
Gleisson de Assis
Federal Center for Technological Education of Minas Gerais (CEFET-MG)
Marcone Jamilson Freitas Souza
Federal University of Ouro Preto (UFOP)
صندلی اداری

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.

Downloads

Download data is not yet available.

Article Details

Issue
Vol. 8 No. 5 (2017): Independent Journal of Management & Production (Special Edition)
Section
Articles

1. Proposal of Policy for Free Access Periodics

Authors whom publish in this magazine should agree to the following terms:

a. Authors should keep the copyrights and grant to the magazine the right of the first publication, with the work simultaneously permitted under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 that allows the sharing of the work with recognition of the authorship of the work and initial publication in this magazine.

b. Authors should have authorization for assuming additional contracts separately, for non-exclusive distribution of the version of the work published in this magazine (e.g.: to publish in an institutional repository or as book chapter), with recognition of authorship and initial publication in this magazine.

c. Authors should have permission and should be stimulated to publish and to distribute its work online (e.g.: in institutional repositories or its personal page) to any point before or during the publishing process, since this can generate productive alterations, as well as increasing the impact and the citation of the published work (See The Effect of Free Access).

 

Proposal of Policy for Periodic that offer Postponed Free Access

Authors whom publish in this magazine should agree to the following terms:

 

a. Authors should keep the copyrights and grant to the magazine the right of the first publication, with the work simultaneously permitted under the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 [SPECIFY TIME HERE] after the publication, allowing the sharing of the work with recognition of the authorship of the work and initial publication in this magazine.

 

b. Authors should have authorization for assuming additional contracts separately, for non-exclusive distribution of the version of the work published in this magazine (e.g.: to publish in institutional repository or as book chapter), with recognition of authorship and initial publication in this magazine.

 

c. Authors should have permission and should be stimulated to publish and to distribute its work online (e.g.: in institutional repositories or its personal page) to any point before or during the publishing process, since this can generate productive alterations, as well as increasing the impact and the citation of the published work (See The Effect of Free Access).


d. They allow some kind of open dissemination. Authors can disseminate their articles in open access, but with specific conditions imposed by the editor that are related to:
     Version of the article that can be deposited in the repository:
           Pre-print: before being reviewed by pairs.
           Post-print: once reviewed by pairs, which can be:
                  The version of the author that has been accepted for publication.
                  The editor's version, that is, the article published in the magazine.
           At which point the article can be made accessible in an open manner: before it is published in the magazine, immediately afterwards or if a period of seizure is required, which can range from six months to several years.
      Where to leave open: on the author's personal web page, only departmental websites, the repository of the institution, the file of the research funding agency, among others.

Crossref
Scopus
Google Scholar
Europe PMC

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.

فروشگاه اینترنتی