{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T05:49:35Z","timestamp":1768456175361,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,1,30]],"date-time":"2021-01-30T00:00:00Z","timestamp":1611964800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,30]],"date-time":"2021-01-30T00:00:00Z","timestamp":1611964800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["UIDB\/04106\/2020"],"award-info":[{"award-number":["UIDB\/04106\/2020"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["UIDP\/04106\/2020"],"award-info":[{"award-number":["UIDP\/04106\/2020"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["PD\/BD\/114185\/2016"],"award-info":[{"award-number":["PD\/BD\/114185\/2016"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"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":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Proximity search is an iterative method to solve complex mathematical programming problems. At each iteration, the objective function of the problem at hand is replaced by the Hamming distance function to a given solution, and a cutoff constraint is added to impose that any new obtained solution improves the objective function value. A mixed integer programming solver is used to find a feasible solution to this modified problem, yielding an improved solution to the original problem. This paper introduces the concept of weighted Hamming distance that allows to design a new method called weighted proximity search. In this new distance function, low weights are associated with the variables whose value in the current solution is promising to change in order to find an improved solution, while high weights are assigned to variables that are expected to remain unchanged. The weights help to distinguish between alternative solutions in the neighborhood of the current solution, and provide guidance to the solver when trying to locate an improved solution. Several strategies to determine weights are presented, including both static and dynamic strategies. The proposed weighted proximity search is compared with the classic proximity search on instances from three optimization problems: the <jats:italic>p<\/jats:italic>-median problem, the set covering problem, and the stochastic lot-sizing problem. The obtained results show that a suitable choice of weights allows the weighted proximity search to obtain better solutions, for 75<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>%<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the cases, than the ones obtained by using proximity search and for 96<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>%<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of the cases the solutions are better than the ones obtained by running a commercial solver with a time limit.<\/jats:p>","DOI":"10.1007\/s10732-021-09466-0","type":"journal-article","created":{"date-parts":[[2021,1,30]],"date-time":"2021-01-30T20:02:41Z","timestamp":1612036961000},"page":"459-496","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Weighted proximity search"],"prefix":"10.1007","volume":"27","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":[[2021,1,30]]},"reference":[{"issue":"1","key":"9466_CR1","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.orl.2004.04.002","volume":"33","author":"T Achterberg","year":"2005","unstructured":"Achterberg, T., Koch, T., Martin, A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42\u201354 (2005)","journal-title":"Oper. Res. Lett."},{"key":"9466_CR2","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-642-29210-1_12","volume-title":"Operations Research Proceedings 2011","author":"T Achterberg","year":"2012","unstructured":"Achterberg, T., Berthold, T., Hendel, G.: Rouding and propagation heuristics for mixed integer programming. In: Klatte, D., L\u00fcthi, H.-J., Schmedders, K. (eds.) Operations Research Proceedings 2011, pp. 71\u201376. Springer, Berlin (2012)"},{"key":"9466_CR3","first-page":"18","volume-title":"Lecture Notes in Computer Science, Computational Logistics","author":"A Agra","year":"2016","unstructured":"Agra, A., Christiansen, M., Hvattum, L.M., Rodrigues, F.: A MIP based local search heuristic for a stochastic maritime inventory routing problem. In: Paias, A., Ruthmair, M., Vo\u00df, S. (eds.) Lecture Notes in Computer Science, Computational Logistics, vol. 9855, pp. 18\u201334. Springer, Berlin (2016)"},{"issue":"3","key":"9466_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1287\/trsc.2017.0814","volume":"52","author":"A Agra","year":"2018","unstructured":"Agra, A., Christiansen, M., Hvattum, L.M., Rodrigues, F.: Robust optimization for a maritime inventory routing problem. Transp. Sci. 52(3), 509\u2013525 (2018a)","journal-title":"Transp. Sci."},{"issue":"1","key":"9466_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/net.21796","volume":"72","author":"A Agra","year":"2018","unstructured":"Agra, A., Requejo, C., Rodrigues, F.: An adjustable sample average approximation algorithm for the production-inventory-routing problem. Networks 72(1), 5\u201324 (2018b)","journal-title":"Networks"},{"issue":"3","key":"9466_CR6","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1016\/j.ejor.2014.04.023","volume":"238","author":"E Alvarez-Miranda","year":"2014","unstructured":"Alvarez-Miranda, E., Cacchiani, V., Lodi, A., Parriani, T., Schmidt, D.: Single-commodity robust network design problem: complexity, instances and heuristic solutions. Eur. J. Oper. Res. 238(3), 711\u2013723 (2014)","journal-title":"Eur. J. Oper. Res."},{"key":"9466_CR7","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0377-2217(85)90040-2","volume":"21","author":"J Beasley","year":"1985","unstructured":"Beasley, J.: A note on solving large p-median problems. Eur. J. Oper. Res. 21, 270\u2013273 (1985)","journal-title":"Eur. J. Oper. Res."},{"issue":"6","key":"9466_CR8","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1016\/j.orl.2013.08.007","volume":"41","author":"T Berthold","year":"2013","unstructured":"Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611\u2013614 (2013)","journal-title":"Oper. Res. Lett."},{"key":"9466_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s12532-013-0060-9","volume":"6","author":"T Berthold","year":"2014","unstructured":"Berthold, T.: RENS\u2014the optimal rounding. Math. Program. Comput. 6, 33\u201354 (2014)","journal-title":"Math. Program. Comput."},{"key":"9466_CR10","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10732-015-9306-1","volume":"22","author":"N Boland","year":"2016","unstructured":"Boland, N., Fischetti, M., Monaci, M., Savelsbergh, M.: Proximity Benders: a decomposition heuristic for stochastic programming. J. Heuristics 22, 181\u2013198 (2016)","journal-title":"J. Heuristics"},{"key":"9466_CR11","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":"3","key":"9466_CR12","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9466_CR13","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":"9466_CR14","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10107-004-0570-3","volume":"104","author":"M Fischetti","year":"2005","unstructured":"Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Program. 104(1), 91\u2013104 (2005)","journal-title":"Math. Program."},{"issue":"7","key":"9466_CR15","doi-asserted-by":"publisher","first-page":"2146","DOI":"10.1287\/mnsc.2016.2461","volume":"63","author":"M Fischetti","year":"2016","unstructured":"Fischetti, M., Ljubic, I., Sinnl, M.: Redesigning Benders decomposition for large-scale facility location. Manag. Sci. 63(7), 2146\u20132162 (2016)","journal-title":"Manag. Sci."},{"issue":"1\u20133","key":"9466_CR16","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":"9466_CR17","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"},{"issue":"4","key":"9466_CR18","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s10732-015-9283-4","volume":"22","author":"M Fischetti","year":"2016","unstructured":"Fischetti, M., Monaci, M.: Proximity search heuristics for wind farm optimal layout. J. Heuristics 22(4), 459\u2013474 (2016)","journal-title":"J. Heuristics"},{"key":"9466_CR19","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 (1997)"},{"key":"9466_CR20","first-page":"3218","volume-title":"Wiley Encyclopedia of Operations Research and Management Science","author":"LM Hvattum","year":"2011","unstructured":"Hvattum, L.M., Esbensen, E.F.: Metaheuristics for stochastic problems. In: Cochran, J., Cox Jr., L., Keskinocak, P., Kharoufeh, J., Smith, J. (eds.) Wiley Encyclopedia of Operations Research and Management Science, pp. 3218\u20133229. Wiley, New York (2011)"},{"issue":"2","key":"9466_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1287\/ijoc.11.2.173","volume":"11","author":"JT Linderoth","year":"1999","unstructured":"Linderoth, J.T., Savelsbergh, M.W.P.: A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11(2), 173\u2013187 (1999)","journal-title":"INFORMS J. Comput."},{"key":"9466_CR22","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.disopt.2016.01.005","volume":"19","author":"DR Morrison","year":"2016","unstructured":"Morrison, D.R., Jacobson, S.H., Sauppe, J.J., Sewell, E.C.: Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning. Discr. Optim. 19, 79\u2013102 (2016)","journal-title":"Discr. Optim."},{"issue":"3","key":"9466_CR23","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1016\/j.ejor.2019.03.015","volume":"277","author":"F Rodrigues","year":"2019","unstructured":"Rodrigues, F., Agra, A., Christiansen, M., Hvattum, L.M., Requejo, C.: Comparing techniques for modelling uncertainty in a maritime inventory routing problem. Eur. J. Oper. Res. 277(3), 831\u2013845 (2019)","journal-title":"Eur. J. Oper. Res."},{"key":"9466_CR24","doi-asserted-by":"crossref","unstructured":"Rodrigues, F., Agra, A., Requejo, C., Delage, E.: Lagrangian duality for robust problems with decomposable functions: the case of a robust inventory problem. INFORMS J. Comput. (2020). https:\/\/doi.org\/10.1287\/ijoc.2020.0978","DOI":"10.1287\/ijoc.2020.0978"},{"key":"9466_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."},{"key":"9466_CR26","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/3-540-49481-2_30","volume-title":"Principles and Practice of Constraint Programming\u2014CP98","author":"P Shaw","year":"1998","unstructured":"Shaw, P.: Using constraint programming and local search methods to solve vehicle routing problems. In: Maher, M., Puget, J.-F. (eds.) Principles and Practice of Constraint Programming\u2014CP98, pp. 417\u2013431. Springer, Berlin (1998)"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-021-09466-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-021-09466-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-021-09466-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,20]],"date-time":"2021-05-20T09:30:42Z","timestamp":1621503042000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-021-09466-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,30]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["9466"],"URL":"https:\/\/doi.org\/10.1007\/s10732-021-09466-0","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,30]]},"assertion":[{"value":"26 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 December 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}