{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T03:01:48Z","timestamp":1762052508701,"version":"build-2065373602"},"reference-count":48,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2022,6,2]],"date-time":"2022-06-02T00:00:00Z","timestamp":1654128000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["20K11973"],"award-info":[{"award-number":["20K11973"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The quadratic unconstrained binary optimization (QUBO) problem is categorized as an NP-hard combinatorial optimization problem. The variable neighborhood search (VNS) algorithm is one of the leading algorithms used to solve QUBO problems. As neighborhood structure change is the central concept in the VNS algorithm, the design of the neighborhood structure is crucial. This paper presents a modified VNS algorithm called \u201cB-VNS\u201d, which can be used to solve QUBO problems. A binomial trial was used to construct the neighborhood structure, and this was used with the aim of reducing computation time. The B-VNS and VNS algorithms were tested on standard QUBO problems from Glover and Beasley, on standard max-cut problems from Helmberg\u2013Rendl, and on those proposed by Burer, Monteiro, and Zhang. Finally, Mann\u2013Whitney tests were conducted using \u03b1=0.05, to statistically compare the performance of the two algorithms. It was shown that the B-VNS and VNS algorithms are able to provide good solutions, but the B-VNS algorithm runs substantially faster. Furthermore, the B-VNS algorithm performed the best in all of the max-cut problems, regardless of problem size, and it performed the best in QUBO problems, with sizes less than 500. The results suggest that the use of binomial distribution, to construct the neighborhood structure, has the potential for further development.<\/jats:p>","DOI":"10.3390\/a15060192","type":"journal-article","created":{"date-parts":[[2022,6,2]],"date-time":"2022-06-02T11:05:02Z","timestamp":1654167902000},"page":"192","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Constructing the Neighborhood Structure of VNS Based on Binomial Distribution for Solving QUBO Problems"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6797-2785","authenticated-orcid":false,"given":"Dhidhi","family":"Pambudi","sequence":"first","affiliation":[{"name":"Graduate School of Science and Technology for Innovation, Yamaguchi University, 1677-1, Yoshida, Yamaguchi 753-8512, Japan"},{"name":"Department of Mathematics Education, Faculty of Teacher Training and Education, Sebelas Maret University, Surakarta 57126, Indonesia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8189-4672","authenticated-orcid":false,"given":"Masaki","family":"Kawamura","sequence":"additional","affiliation":[{"name":"Graduate School of Science and Technology for Innovation, Yamaguchi University, 1677-1, Yoshida, Yamaguchi 753-8512, Japan"}]}],"member":"1968","published-online":{"date-parts":[[2022,6,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Paschos, V.T. (2014). Applications of Combinatorial Optimizations, John Wiley & Sons, Ltd.","DOI":"10.1002\/9781119005384"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Talbi, E.G. (2009). Metaheuristics, John Wiley & Sons, Ltd.","DOI":"10.1002\/9780470496916"},{"key":"ref_3","unstructured":"Pardalos, P.M., and Rebennack, S. Metaheuristic Optimization: Algorithm Analysis and Open Problems. Proceedings of the Experimental Algorithms."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Gass, S.I., and Fu, M.C. (2013). Metaheuristics. Encyclopedia of Operations Research and Management Science, Springer.","DOI":"10.1007\/978-1-4419-1153-7"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Glover, F., and Kochenberger, G.A. (2003). Handbook of Metaheuristics, Springer.","DOI":"10.1007\/b101874"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Papalitsas, C., Andronikos, T., Giannakis, K., Theocharopoulou, G., and Fanarioti, S. (2019). A QUBO Model for the Traveling Salesman Problem with Time Windows. Algorithms, 12.","DOI":"10.20944\/preprints201909.0154.v1"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"10029","DOI":"10.1038\/s41598-021-89461-4","article-title":"QUBO formulations for training machine learning models","volume":"11","author":"Date","year":"2021","journal-title":"Sci. Rep."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Karp, R.M. (2010). Reducibility Among Combinatorial Problems. 50 Years of Integer Programming 1958\u20132008: From the Early Years to the State-of-the-Art, Springer.","DOI":"10.1007\/978-3-540-68279-0_8"},{"key":"ref_9","unstructured":"Glover, F., Kochenberger, G., and Du, Y. (2022, May 06). A Tutorial on Formulating and Using QUBO Models. CoRR 2018, Available online: http:\/\/xxx.lanl.gov\/abs\/1811.11538."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0377-2217(00)00242-3","article-title":"Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem","volume":"134","author":"Katayama","year":"2001","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1287\/mnsc.44.3.336","article-title":"Adaptive Memory Tabu Search for Binary Quadratic Programs","volume":"44","author":"Glover","year":"1998","journal-title":"Manag. Sci."},{"key":"ref_12","unstructured":"Merz, P., and Freisleben, B. (1999). Genetic Algorithms for Binary Quadratic Programming, Morgan Kaufmann Publishers Inc.. GECCO\u201999."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/s10732-007-9009-3","article-title":"Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)","volume":"13","author":"Boros","year":"2007","journal-title":"J. Heuristics"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","article-title":"Variable neighborhood search","volume":"24","author":"Hansen","year":"1997","journal-title":"Comput. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Duarte, A., S\u00e1nchez, A., Fern\u00e1ndez, F., and Cabido, R. (2005, January 25\u201329). A Low-Level Hybridization between Memetic Algorithm and VNS for the Max-Cut Problem. Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation, Washington, DC, USA. GECCO\u201905.","DOI":"10.1145\/1068009.1068178"},{"key":"ref_16","unstructured":"Kim, S.H., Kim, Y.H., and Moon, B.R. (2001, January 7\u201311). A Hybrid Genetic Algorithm for the MAX CUT Problem. Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, San Fransisco, CA, USA. GECCO\u201901."},{"key":"ref_17","unstructured":"Festa, P., Pardalos, P., Resende, M., and Ribeiro, C. (2001, January 16\u201320). GRASP and VNS for Max-Cut. Proceedings of the Extended Abstracts of the Fourth Metaheuristics International Conference, Porto, Portugal."},{"key":"ref_18","unstructured":"Resende, M. (2001, January 16\u201320). GRASP With Path Re-linking and VNS for MAXCUT. Proceedings of the 4th MIC, Porto, Portugal."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"77321","DOI":"10.1109\/ACCESS.2020.2986895","article-title":"Solving the Problem of Large-Scale Optimal Scheduling of Distributed Energy Resources in Smart Grids Using an Improved Variable Neighborhood Search","volume":"8","author":"Ramli","year":"2020","journal-title":"IEEE Access"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"68686","DOI":"10.1109\/ACCESS.2018.2879600","article-title":"Multi-Objective Parallel Variable Neighborhood Search for Energy Consumption Scheduling in Blocking Flow Shops","volume":"6","author":"Wang","year":"2018","journal-title":"IEEE Access"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"134042","DOI":"10.1109\/ACCESS.2020.3010577","article-title":"A Hybrid Coral Reefs Optimization\u2014Variable Neighborhood Search Approach for the Unequal Area Facility Layout Problem","volume":"8","author":"Abraham","year":"2020","journal-title":"IEEE Access"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"21258","DOI":"10.1109\/ACCESS.2021.3056067","article-title":"An Adaptive Variable Neighborhood Search Ant Colony Algorithm for Vehicle Routing Problem With Soft Time Windows","volume":"9","author":"He","year":"2021","journal-title":"IEEE Access"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"El Cadi, A.A., Atitallah, R.B., Mladenovi\u0107, N., and Artiba, A. (2015, January 21\u201323). A Variable Neighborhood Search (VNS) metaheuristic for Multiprocessor Scheduling Problem with Communication Delays. Proceedings of the 2015 International Conference on Industrial Engineering and Systems Management (IESM), Seville, Spain.","DOI":"10.1109\/IESM.2015.7380290"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1502","DOI":"10.1109\/TLA.2021.9468443","article-title":"A VNS Algorithm for PID Controller: Hardware-In-The-Loop Approach","volume":"19","author":"Silva","year":"2021","journal-title":"IEEE Latin Am. Trans."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Phanden, R.K., Demir, H.I., and Gupta, R.D. (2018, January 7\u20139). Application of genetic algorithm and variable neighborhood search to solve the facility layout planning problem in job shop production system. Proceedings of the 2018 7th International Conference on Industrial Technology and Management (ICITM), Oxford, UK.","DOI":"10.1109\/ICITM.2018.8333959"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"108782","DOI":"10.1109\/ACCESS.2020.2999935","article-title":"Uncertain Scenario Based MicroGrid Optimization via Hybrid Levy Particle Swarm Variable Neighborhood Search Optimization (HL_PS_VNSO)","volume":"8","author":"Dabhi","year":"2020","journal-title":"IEEE Access"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"99380","DOI":"10.1109\/ACCESS.2020.2997379","article-title":"An Improved Discrete Migrating Birds Optimization Algorithm for the No-Wait Flow Shop Scheduling Problem","volume":"8","author":"Zhang","year":"2020","journal-title":"IEEE Access"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Zhang, C., Xie, Z., Shao, X., and Tian, G. (2015, January 22\u201324). An effective VNSSA algorithm for the blocking flowshop scheduling problem with makespan minimization. Proceedings of the 2015 International Conference on Advanced Mechatronic Systems (ICAMechS), Beijing, China.","DOI":"10.1109\/ICAMechS.2015.7287134"},{"key":"ref_29","unstructured":"Montemayor, A.S., Duarte, A., Pantrigo, J.J., Cabido, R., and Carlos, J. (2005, January 23\u201325). High-performance VNS for the Max-cut problem using commodity graphics hardware. Proceedings of the Mini-Euro Conference on VNS (MECVNS 05), Tenerife, Spain."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1016\/j.cam.2007.08.018","article-title":"A modified VNS metaheuristic for max-bisection problems","volume":"220","author":"Ling","year":"2008","journal-title":"J. Comput. Appl. Math."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Gendreau, M., and Potvin, J.Y. (2010). Variable Neighborhood Search. Handbook of Metaheuristics, Springer. Chapter 3.","DOI":"10.1007\/978-1-4419-1665-5"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/s10288-008-0089-1","article-title":"Variable neighbourhood search: Methods and applications","volume":"6","author":"Hansen","year":"2008","journal-title":"4OR"},{"key":"ref_33","unstructured":"Hansen, P., and Mladenovi\u0107, N. (2003). A Tutorial on Variable Neighborhood Search, Les Cahiers Du Gerad, Hec Montreal and Gerad. Technical report."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1033","DOI":"10.1080\/1055678021000090033","article-title":"Randomized heuristics for the Max-Cut problem","volume":"17","author":"Festa","year":"2002","journal-title":"Optim. Methods Softw."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1057\/jors.1990.166","article-title":"OR-Library: Distributing Test Problems by Electronic Mail","volume":"41","author":"Beasley","year":"1990","journal-title":"J. Oper. Res. Soc."},{"key":"ref_36","unstructured":"Beasley, J.E. (2021, September 22). OR-Library. Available online: http:\/\/people.brunel.ac.uk\/~mastjjb\/jeb\/orlib\/files."},{"key":"ref_37","unstructured":"Beasley, J.E. (1998). Heuristic Algorithms for the Unconstrained Binary Quadratic Programming Problem, The Management School, Imperial College. Technical report."},{"key":"ref_38","unstructured":"Wiegele, A. (2007). Biq Mac Library\u2014A Collection of Max-Cut and Quadratic 0-1 Programming Instances of Medium Size, Alpen-Adria-Universit\u00e4t Klagenfurt, Institut f\u00fcr Mathematik, Universit\u00e4tsstr. Technical report."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1137\/S1052623497328987","article-title":"A Spectral Bundle Method for Semidefinite Programming","volume":"10","author":"Helmberg","year":"2000","journal-title":"SIAM J. Optim."},{"key":"ref_40","unstructured":"Ye, Y. (2021, September 22). Gset. Available online: https:\/\/web.stanford.edu\/~yyye\/yyye\/Gset."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1137\/S1052623400382467","article-title":"Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs","volume":"12","author":"Burer","year":"2002","journal-title":"SIAM J. Optim."},{"key":"ref_42","unstructured":"(2021, September 22). Mart\u00ed; Duarte; Laguna. Maxcut Problem. Available online: http:\/\/grafo.etsii.urjc.es\/optsicom\/maxcut\/set2.zip."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/s10732-011-9189-8","article-title":"Solving large scale Max Cut problems via tabu search","volume":"19","author":"Kochenberger","year":"2013","journal-title":"J. Heuristics"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"3100","DOI":"10.1016\/j.cor.2011.12.006","article-title":"Probabilistic GRASP-Tabu Search algorithms for the UBQP problem","volume":"40","author":"Wang","year":"2013","journal-title":"Comput. Oper. Res."},{"key":"ref_45","first-page":"29","article-title":"Application of Multistart Tabu Search to the Max-Cut Problem","volume":"31","author":"Palubeckis","year":"2004","journal-title":"Inf. Technol. Control"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1016\/j.disopt.2007.02.001","article-title":"A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)","volume":"5","author":"Boros","year":"2008","journal-title":"Discret. Optim."},{"key":"ref_47","unstructured":"JASP Team (2022, May 06). JASP, Version 0.16; Computer software; JASP Team. Available online: https:\/\/jasp-stats.org\/faq\/."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/s10898-019-00866-y","article-title":"Cooperative versus non-cooperative parallel variable neighborhood search strategies: A case study on the capacitated vehicle routing problem","volume":"78","author":"Kalatzantonakis","year":"2020","journal-title":"J. Glob. Optim."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/6\/192\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:23:47Z","timestamp":1760138627000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/6\/192"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,2]]},"references-count":48,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2022,6]]}},"alternative-id":["a15060192"],"URL":"https:\/\/doi.org\/10.3390\/a15060192","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,6,2]]}}}