{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T16:10:45Z","timestamp":1778256645745,"version":"3.51.4"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,4,16]],"date-time":"2022-04-16T00:00:00Z","timestamp":1650067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,16]],"date-time":"2022-04-16T00:00:00Z","timestamp":1650067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","award":["UIDB\/04106\/2020"],"award-info":[{"award-number":["UIDB\/04106\/2020"]}]},{"name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","award":["UIDP\/04106\/2020"],"award-info":[{"award-number":["UIDP\/04106\/2020"]}]},{"name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","award":["UIDB\/05069\/2020"],"award-info":[{"award-number":["UIDB\/05069\/2020"]}]},{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["AXIOM"],"award-info":[{"award-number":["AXIOM"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Local search algorithms are frequently used to handle complex optimization problems involving binary decision variables. One way of implementing a local search procedure is by using a mixed-integer programming solver to explore a neighborhood defined through a constraint that limits the number of binary variables whose values are allowed to change in a given iteration. Recognizing that not all variables are equally promising to change when searching for better neighboring solutions, we propose a weighted iterated local branching heuristic. This new procedure differs from similar existing methods since it considers groups of binary variables and associates with each group a limit on the number of variables that can change. The groups of variables are defined using weights that indicate the expected contribution of flipping the variables when trying to identify improving solutions in the current neighborhood. When the mixed-integer programming solver fails to identify an improving solution in a given iteration, the proposed heuristic may force the search into new regions of the search space by utilizing the group of variables that are least promising to flip. The weighted iterated local branching heuristic is tested on benchmark instances of the optimum satisfiability problem, and computational results show that the weighted method is superior to an alternative method without weights.<\/jats:p>","DOI":"10.1007\/s10732-022-09496-2","type":"journal-article","created":{"date-parts":[[2022,4,16]],"date-time":"2022-04-16T15:02:38Z","timestamp":1650121358000},"page":"329-350","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Weighted iterated local branching for mathematical programming problems with binary variables"],"prefix":"10.1007","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3770-5456","authenticated-orcid":false,"given":"Filipe","family":"Rodrigues","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4672-6099","authenticated-orcid":false,"given":"Agostinho","family":"Agra","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0490-9978","authenticated-orcid":false,"given":"Lars Magnus","family":"Hvattum","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0529-5090","authenticated-orcid":false,"given":"Cristina","family":"Requejo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,16]]},"reference":[{"key":"9496_CR1","first-page":"1","volume-title":"Handbook of heuristics","author":"A Alsheddy","year":"2016","unstructured":"Alsheddy, A., Voudouris, C., Tsang, E.P.K., Alhindi, A.: Guided local search. In: Mart\u00ed, R., Panos, P., Resende, M.G. (eds.) Handbook of heuristics, pp. 1\u201337. Springer International Publishing, Cham (2016)"},{"issue":"3","key":"9496_CR2","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/937503.937505","volume":"35","author":"C Blum","year":"2003","unstructured":"Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Sur. 35(3), 268\u2013308 (2003)","journal-title":"ACM Comput. Sur."},{"key":"9496_CR3","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.ins.2013.02.041","volume":"237","author":"I Boussa\u00efd","year":"2013","unstructured":"Boussa\u00efd, I., Lepagnot, J., Siarry, P.: A survey on optimization metaheuristics. Inf. Sci. 237, 82\u2013117 (2013)","journal-title":"Inf. Sci."},{"issue":"1","key":"9496_CR4","first-page":"23","volume":"26","author":"R da Silva","year":"2020","unstructured":"da Silva, R., Hvattum, L.M., Glover, F.: Combining solutions of the optimum satisfiability problem using evolutionary tunneling. MENDEL Soft Comput. J. 26(1), 23\u201329 (2020)","journal-title":"MENDEL Soft Comput. J."},{"issue":"1","key":"9496_CR5","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10107-004-0518-7","volume":"102","author":"E Danna","year":"2005","unstructured":"Danna, E., Rothberg, E., Pape, C.L.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102(1), 71\u201390 (2005)","journal-title":"Math. Program."},{"issue":"1","key":"9496_CR6","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s11590-020-01577-0","volume":"15","author":"AT Dauer","year":"2021","unstructured":"Dauer, A.T., de Athayde Prata, B.: Variable fixing heuristics for solving multiple depot vehicle scheduling problem with heterogeneous fleet and time windows. Optim. Lett. 15(1), 153\u2013170 (2021)","journal-title":"Optim. Lett."},{"key":"9496_CR7","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1023\/A:1023717307746","volume":"9","author":"T Davoine","year":"2003","unstructured":"Davoine, T., Hammer, P., Vizv\u00e1ri, B.: A heuristic for Boolean optimization problems. J. Heuristics 9, 229\u2013247 (2003)","journal-title":"J. Heuristics"},{"key":"9496_CR8","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/j.entcs.2019.08.039","volume":"346","author":"A Faria","year":"2019","unstructured":"Faria, A., de Souza, S., de S\u00e1, E., Silva, C.: Variable neighborhood descent branching applied to the multi-way number partitioning problem. Elect. Notes Theor. Comput. Sci. 346, 437\u2013447 (2019)","journal-title":"Elect. Notes Theor. Comput. Sci."},{"issue":"1\u20133","key":"9496_CR9","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s10107-003-0395-5","volume":"98","author":"M Fischetti","year":"2003","unstructured":"Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1\u20133), 23\u201347 (2003)","journal-title":"Math. Program."},{"issue":"6","key":"9496_CR10","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/s10732-014-9266-x","volume":"20","author":"M Fischetti","year":"2014","unstructured":"Fischetti, M., Monaci, M.: Proximity search for 0$$-$$1 mixed-integer convex programming. J. Heuristics 20(6), 709\u2013731 (2014)","journal-title":"J. Heuristics"},{"key":"9496_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-6089-0","volume-title":"Tabu search","author":"F Glover","year":"1997","unstructured":"Glover, F., Laguna, M.: Tabu search. Kluwer Academic Publisher, Boston, Dordrecht, London (1997)"},{"key":"9496_CR12","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.cor.2016.06.016","volume":"76","author":"PH Gonz\u00e1lez","year":"2016","unstructured":"Gonz\u00e1lez, P.H., Simonetti, L., Michelon, P., Martinhon, C., Santos, E.: A variable fixing heuristic with local branching for the fixed charge uncapacitated network design problem with user-optimal flow. Comput Oper. Res. 76, 134\u2013146 (2016)","journal-title":"Comput Oper. Res."},{"key":"9496_CR13","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s10732-018-9392-y","volume":"25","author":"F Hernandez","year":"2019","unstructured":"Hernandez, F., Gendreau, M., Jabali, O., Rei, W.: A local branching matheuristic for the multi-vehicle routing problem with stochastic demands. J. Heuristics 25, 215\u2013245 (2019)","journal-title":"J. Heuristics"},{"key":"9496_CR14","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.dam.2017.09.010","volume":"242","author":"A Hill","year":"2018","unstructured":"Hill, A., Vo\u00df, S.: Generalized local branching heuristics and the capacitated ring tree problem. Discrete Appl. Math. 242, 34\u201352 (2018)","journal-title":"Discrete Appl. Math."},{"key":"9496_CR15","first-page":"1","volume-title":"Integer programming: theory and practice","author":"LM Hvattum","year":"2006","unstructured":"Hvattum, L.M., L\u00f8kketangen, A., Glover, F.: New heuristics and adaptive memory procedures for Boolean optimization problems. In: Karlof, J. (ed.) Integer programming: theory and practice, pp. 1\u201318. CRC Press, Boca Raton, FL (2006)"},{"key":"9496_CR16","first-page":"13","volume":"7","author":"LM Hvattum","year":"2012","unstructured":"Hvattum, L.M., L\u00f8kketangen, A., Glover, F.: Comparisons of commercial MIP solvers and an adaptive memory (tabu search) procedure for a class of 0\u20131 integer programming problems. Algorithm. Oper. Res. 7, 13\u201321 (2012)","journal-title":"Algorithm. Oper. Res."},{"issue":"1","key":"9496_CR17","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.dam.2003.06.006","volume":"142","author":"LM Hvattum","year":"2004","unstructured":"Hvattum, L.M., L\u00f8kketangen, A., Glover, F.: Adaptive memory search for Boolean optimization problems. Discrete Appl. Math. 142(1), 99\u2013109 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"4598","key":"9496_CR18","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671\u2013680 (1983)","journal-title":"Science"},{"key":"9496_CR19","unstructured":"Li, C., Many\u00e0, F.: MaxSAT, hard and soft constraints. In A.\u00a0Biere, M.\u00a0Heule, H.\u00a0van Maaren, and T.\u00a0Walsh, editors, Handbook of Satisfiability, volume 185 of Frontiers in artificial intelligence and applications, pages 613\u2013631. IOS Press, (2009)"},{"key":"9496_CR20","unstructured":"Li, X.: Optimization algorithms for the minimum-cost satisfiability problem. Phd thesis, North Carolina State University, Raleigh, North Carolina, (2004)"},{"key":"9496_CR21","doi-asserted-by":"crossref","unstructured":"Raidl, G., Puchinger, J.: Combining (integer) linear programming techniques and metaheuristics for combinatorial optimization. In C.\u00a0B. C., M.\u00a0Aguilera, A.\u00a0Roli, and M.\u00a0Sampels, (eds), Hybrid metaheuristics, 114 of Studies in computational intelligence, pp. 31\u201362. Springer, Berlin, Heidelberg, (2008)","DOI":"10.1007\/978-3-540-78295-7_2"},{"key":"9496_CR22","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1287\/trsc.1090.0295","volume":"44","author":"W Rei","year":"2010","unstructured":"Rei, W., Gendreau, M., Soriana, P.: A hybrid monte carlo local branching algorithm for the single vehicle routing problem with stochastic demands. Transp. Sci. 44, 136\u2013146 (2010)","journal-title":"Transp. Sci."},{"issue":"3","key":"9496_CR23","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s10732-021-09466-0","volume":"27","author":"F Rodrigues","year":"2021","unstructured":"Rodrigues, F., Agra, A., Hvattum, L.M., Requejo, C.: Weighted proximity search. J. Heuristics 27(3), 459\u2013496 (2021)","journal-title":"J. Heuristics"},{"key":"9496_CR24","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1016\/j.cor.2008.09.003","volume":"37","author":"I Rodr\u00edguez-Mart\u00edn","year":"2010","unstructured":"Rodr\u00edguez-Mart\u00edn, I., Salazar-Gonz\u00e1lez, J.: A local branching heuristic for the capacitated fixed-charge network design problem. Comput. Oper. Res. 37, 575\u2013581 (2010)","journal-title":"Comput. Oper. Res."},{"key":"9496_CR25","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1287\/ijoc.1060.0189","volume":"19","author":"E Rothberg","year":"2007","unstructured":"Rothberg, E.: An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS J. Comput. 19, 534\u2013541 (2007)","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"9496_CR26","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1287\/ijoc.2018.0822","volume":"31","author":"R Sadykov","year":"2019","unstructured":"Sadykov, R., Vanderbeck, F., Pessoa, A., Tahiri, I., Uchoa, E.: Primal heuristics for branch and price: the assets of diving methods. INFORMS J. Comput. 31(2), 251\u2013267 (2019)","journal-title":"INFORMS J. Comput."},{"key":"9496_CR27","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/j.ejor.2016.07.004","volume":"257","author":"M Samavati","year":"2017","unstructured":"Samavati, M., Essam, D., Nehring, M., Sarker, R.: A local branching heuristic for the open pit mine production scheduling problem. Euro. J. Oper. Res. 257, 261\u2013271 (2017)","journal-title":"Euro. J. Oper. Res."},{"issue":"3","key":"9496_CR28","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/s10732-020-09460-y","volume":"27","author":"F Sarayloo","year":"2021","unstructured":"Sarayloo, F., Crainic, T.G., Rei, W.: A reduced cost-based restriction and refinement matheuristic for stochastic network design problem. J. Heuristics 27(3), 325\u2013351 (2021)","journal-title":"J. Heuristics"},{"issue":"4","key":"9496_CR29","doi-asserted-by":"publisher","first-page":"6532","DOI":"10.4249\/scholarpedia.6532","volume":"10","author":"K S\u00f6rensen","year":"2015","unstructured":"S\u00f6rensen, K., Glover, F.: Metaheuristics. Scholarpedia 10(4), 6532 (2015)","journal-title":"Scholarpedia"},{"key":"9496_CR30","first-page":"1","volume-title":"Handbook of heuristics","author":"T St\u00fctzle","year":"2017","unstructured":"St\u00fctzle, T., Ruiz, R.: Iterated local search. In: Mart\u00ed, R., Panos, P., Resende, M.G.C. (eds.) Handbook of heuristics, pp. 1\u201327. Springer International Publishing, Cham (2017)"},{"key":"9496_CR31","doi-asserted-by":"crossref","unstructured":"Wang, Y., L\u00fc, Z., Glover, F., Hao, J.-K.: Effective variable fixing and scoring strategies for binary quadratic programming. In P.\u00a0Merz and J.-K. Hao, (eds), Evolutionary computation in combinatorial optimization, pp. 72\u201383, Berlin, Heidelberg, (2011). Springer Berlin Heidelberg","DOI":"10.1007\/978-3-642-20364-0_7"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-022-09496-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-022-09496-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-022-09496-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,30]],"date-time":"2022-04-30T08:06:30Z","timestamp":1651305990000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-022-09496-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,16]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["9496"],"URL":"https:\/\/doi.org\/10.1007\/s10732-022-09496-2","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,16]]},"assertion":[{"value":"15 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 April 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}