Top

Published in:

2019 | OriginalPaper | Chapter

A Variable Neighborhood Search Approach for Solving the Multidimensional Multi-Way Number Partitioning Problem

Authors : Alexandre Frias Faria, Sérgio Ricardo de Souza, Marcone Jamilson Freitas Souza, Carlos Alexandre Silva, Vitor Nazário Coelho

Published in: Variable Neighborhood Search

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper presents an implementation of the Variable Neighborhood Search (VNS) metaheuristic for solving the optimization version of the Multidimensional Multi-Way Number Partitioning Problem (MDMWNPP). This problem consists in distributing the vectors of a given sequence into k disjoint subsets such that the sums of each subset form a set of vectors with minimum diameter. The proposed VNS for solving MDMWNPP has a good performance over instances with three and four subsets. A comparative study of results found from this proposed VNS and an implementation of Memetic Algorithm (MA) is carried out, running in the same proportional time interval. Although the average results are different, the statistical tests show that results of the proposed VNS are not significantly better than MA in a set of instances analyzed.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter A Variable Neighborhood Descent Heuristic for the Multi-quay Berth Allocation and Crane Assignment Problem Under Availability Constraints

next chapter A General Variable Neighborhood Search with Mixed VND for the multi-Vehicle multi-Covering Tour Problem

https://browser.geekbench.com/processors/748.

https://browser.geekbench.com/processors/309.

Faria, A.F., de Souza, S.R., Silva, C.A.: Variable neighborhood descent applied to multi-way number partitioning problem. Electron. Notes Discret. Math. 66, 103–110 (2018). https://doi.org/10.1016/j.endm.2018.03.014. 5th International Conference on Variable Neighborhood SearchMathSciNetCrossRefMATH

Gent, I.P., Walsh, T.: Analysis of heuristics for number partitioning. Comput. Intell. 14(3), 430–451 (1998)MathSciNetCrossRef

Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. XLV(9), 1563–1581 (1966)CrossRef

Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416–429 (1969)MathSciNetCrossRef

Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM (JACM) 21(2), 277–292 (1974)MathSciNetCrossRef

Karmarkar, N., Karp, R.M.: The differencing method of set partition. Report UCB/CSD 81/113, Computer Science Division, University of California, Berkeley, CA (1982)

Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Proceedings of a Symposium on the Complexity of Computer Computations. The IBM Research Symposia, pp. 85–103. Springer, Boston (1972). https://doi.org/10.1007/978-1-4684-2001-2_9CrossRef

Kojić, J.: Integer linear programming model for multidimensional two-way number partitioning problem. Comput. Math. Appl. 60(8), 2302–2308 (2010)MathSciNetCrossRef

Korf, R.E.: A complete anytime algorithm for number partitioning. Artif. Intell. 106(2), 181–203 (1998)MathSciNetCrossRef

10.

Korf, R.E.: Multi-way number partitioning. In: Proceedings of the 21st International Joint Conference on Artifical Intelligence (IJCAI 2009), pp. 538–543 (2009)

11.

Korf, R.E., Schreiber, E.L., Moffitt, M.D.: Optimal sequential multi-way number partitioning. In: Proceedings of the International Symposium on Artificial Intelligence and Mathematics (ISAIM-2014) (2014)

12.

Kratica, J., Kojic, J., Savic, A.: Two metaheuristic approaches for solving multidimensional two-way number partitioning problem. Comput. Oper. Res. 46, 59–68 (2014)MathSciNetCrossRef

13.

Labs, P.: Geekbench, May 2018. https://browser.geekbench.com/

14.

Mertens, S.: A complete anytime algorithm for balanced number partitioning (1999). http://arxiv.org/abs/cs.DS/9903011

15.

Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)MathSciNetCrossRef

16.

Moffitt, M.D.: Search strategies for optimal multi-way number partitioning. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pp. 623–629. AAAI Press (2013)

17.

Nijenhuis, A., Wilf, H.S.: Combinatorial Algorithms: For Computers and Calculators. Academic Press, Cambridge (2014)MATH

18.

Orlov, M.: Efficient generation of set partitions. Technical report, Faculty of Engineering and Computer Sciences, University of Ulm (2002). http://www.cs.bgu.ac.il/~orlovm/papers/partitions.pdf

19.

Pedroso, J.P., Kubo, M.: Heuristics and exact methods for number partitioning. Eur. J. Oper. Res. 202(1), 73–81 (2010)MathSciNetCrossRef

20.

Pop, P.C., Matei, O.: A memetic algorithm approach for solving the multidimensional multi-way number partitioning problem. Appl. Math. Modell. 37(22), 9191–9202 (2013)MathSciNetCrossRef

21.

Rodriguez, F.J., Glover, F., García-Martínez, C., Martí, R., Lozano, M.: GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem. Comput. Oper. Res. 78, 243–254 (2017)MathSciNetCrossRef

22.

Schreiber, E.L.: Optimal Multi-Way Number Partitioning. Ph.D. thesis, University of California Los Angeles (2014)

23.

Schreiber, E.L., Korf, R.E.: Cached iterative weakening for optimal multi-way number partitioning. In: Proceedings of the Twenty-Eighth Annual Conference on Artificial Intelligence (AAAI-2014), Quebec City, Canada (2014)

24.

Schroeppel, R., Shamir, A.: A \({T}={O}(2^{n/2})\), \({S}={O}(2^{n/4})\) algorithm for certain NP-complete problems. SIAM J. Comput. 10(3), 456–464 (1981)MathSciNetCrossRef

25.

Sloane, N.: On-Line Encyclopedia of Integer Sequences (1991). https://oeis.org/

Title: A Variable Neighborhood Search Approach for Solving the Multidimensional Multi-Way Number Partitioning Problem
Authors: Alexandre Frias Faria
Sérgio Ricardo de Souza
Marcone Jamilson Freitas Souza
Carlos Alexandre Silva
Vitor Nazário Coelho
Publisher: Springer International Publishing
Book: Variable Neighborhood Search
Print ISBN: 978-3-030-15842-2

Electronic ISBN: 978-3-030-15843-9

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-15843-9_19

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner