{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T03:22:26Z","timestamp":1768706546033,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T00:00:00Z","timestamp":1728259200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T00:00:00Z","timestamp":1728259200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003500","name":"Universit\u00e0 degli Studi di Padova","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003500","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Prog. Comp."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We describe a diving heuristic framework based on constraint propagation for mixed integer linear programs. The proposed approach is an extension of the common fix-and-propagate scheme, with the addition of solution repairing after each step. The repair logic is loosely based on the WalkSAT strategy for boolean satisfiability. Different strategies for variable ranking and value selection, as well as other options, yield different diving heuristics. The overall method is relatively inexpensive, as it is basically LP-free: the full linear programming relaxation is solved only at the beginning (and only for the ranking strategies that make use of it), while additional, typically much smaller, LPs are only used to compute values for the continuous variables (if any), once at the bottom of a dive. While individual strategies are not very robust in finding feasible solutions on a heterogeneous testbed, a portfolio approach proved quite effective. In particular, it could consistently find feasible solutions in 189 out of 240 instances from the public MIPLIB 2017 benchmark testbed, in a matter of a few seconds of runtime. The framework has also been implemented inside the commercial MIP solver Xpress and shown to give a small performance improvement in time to optimality on a large internal heterogeneous testbed.\n<\/jats:p>","DOI":"10.1007\/s12532-024-00269-5","type":"journal-article","created":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T09:01:59Z","timestamp":1728291719000},"page":"111-139","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A fix-propagate-repair heuristic for mixed integer programming"],"prefix":"10.1007","volume":"17","author":[{"given":"Domenico","family":"Salvagnin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Roberti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matteo","family":"Fischetti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,7]]},"reference":[{"key":"269_CR1","unstructured":"Achterberg, T.: Constraint integer programming. Ph.D. thesis, Technische Universit\u00e4t Berlin (2007)"},{"key":"269_CR2","doi-asserted-by":"crossref","unstructured":"Achterberg, T., Wunderling, R.: Mixed integer programming: analyzing 12 years of progress. In: Facets of combinatorial optimization, pp. 449\u2013481 (2013)","DOI":"10.1007\/978-3-642-38189-8_18"},{"key":"269_CR3","unstructured":"Berthold, T.: Primal heuristics for mixed integer programs. Master\u2019s thesis, Technische Universit\u00e4t Berlin (2006)"},{"issue":"6","key":"269_CR4","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). https:\/\/doi.org\/10.1016\/j.orl.2013.08.007","journal-title":"Oper. Res. Lett."},{"key":"269_CR5","unstructured":"Berthold, T.: Heuristic algorithms in global MINLP solvers. Ph.D. thesis, Technische Universit\u00e4t Berlin (2014)"},{"key":"269_CR6","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-The optimal rounding. Math. Program. Comput. 6, 33\u201354 (2014)","journal-title":"Math. Program. Comput."},{"key":"269_CR7","doi-asserted-by":"crossref","unstructured":"Berthold, T., Feydy, T., Stuckey, P.J.: Rapid learning for binary programs. In: CPAIOR 2010 Proceedings, 6140, 51\u201355 (2010)","DOI":"10.1007\/978-3-642-13520-0_8"},{"issue":"1","key":"269_CR8","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s10732-014-9271-0","volume":"21","author":"T Berthold","year":"2015","unstructured":"Berthold, T., Hendel, G.: Shift-and-propagate. J. Heuristics 21(1), 73\u2013106 (2015)","journal-title":"J. Heuristics"},{"key":"269_CR9","doi-asserted-by":"crossref","unstructured":"Berthold, T., Perregaard, M., Meszaros, C.: Four good reasons to use an interior point solver within a MIP solver. In: Operations Research Proceedings, pp. 159\u2013164 (2018)","DOI":"10.1007\/978-3-319-89920-6_22"},{"key":"269_CR10","doi-asserted-by":"crossref","unstructured":"Bonami, P., Salvagnin, D., Tramontani, A.: Implementing automatic Benders decomposition in a modern MIP solver. In: IPCO 2020 Proceedings, Springer, pp. 78\u201390 (2020)","DOI":"10.1007\/978-3-030-45771-6_7"},{"key":"269_CR11","unstructured":"Danna, E.: Performance variability in mixed integer programming. MIP 2008 workshop in New York City (2008). http:\/\/coral.ie.lehigh.edu\/~jeff\/mip-2008\/program.pdf"},{"issue":"1","key":"269_CR12","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":"5","key":"269_CR13","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s10732-007-9021-7","volume":"13","author":"J Eckstein","year":"2007","unstructured":"Eckstein, J., Nediak, M.: Pivot, cut, and dive: a heuristic for 0\u20131 mixed integer programming. J. Heuristics 13(5), 471\u2013503 (2007)","journal-title":"J. Heuristics"},{"key":"269_CR14","unstructured":"FICO: FICO Xpress reference manual (2024)"},{"issue":"1","key":"269_CR15","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":"1\u20133","key":"269_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":"5","key":"269_CR17","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1016\/j.cor.2006.08.004","volume":"35","author":"M Fischetti","year":"2008","unstructured":"Fischetti, M., Lodi, A.: Repairing MIP infeasibility through local branching. Comput. Oper. Res. 35(5), 1436\u20131445 (2008)","journal-title":"Comput. Oper. Res."},{"key":"269_CR18","doi-asserted-by":"publisher","DOI":"10.1002\/9780470400531.eorms0376","volume-title":"Heuristics in mixed integer programming","author":"M Fischetti","year":"2011","unstructured":"Fischetti, M., Lodi, A.: Heuristics in mixed integer programming. Wiley, Hoboken (2011). https:\/\/doi.org\/10.1002\/9780470400531.eorms0376"},{"issue":"2\u20133","key":"269_CR19","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s12532-009-0007-3","volume":"1","author":"M Fischetti","year":"2009","unstructured":"Fischetti, M., Salvagnin, D.: Feasibility pump 2.0. Math. Program. Comput. 1(2\u20133), 201\u2013222 (2009)","journal-title":"Math. Program. Comput."},{"key":"269_CR20","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1007\/s12532-019-00159-1","volume":"11","author":"G Gamrath","year":"2019","unstructured":"Gamrath, G., Berthold, T., Heinz, S., Winkler, M.: Structure-driven fix-and-propagate heuristics for mixed integer programming. Math. Program. Comput. 11, 675\u2013702 (2019)","journal-title":"Math. Program. Comput."},{"key":"269_CR21","doi-asserted-by":"crossref","unstructured":"Ghosh, S.: DINS, a MIP improvement heuristic. In: Fischetti, M., Williamson, D.P. (eds.) Integer programming and combinatorial optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25\u201327, 2007, proceedings, lecture notes in computer science, vol. 4513, pp. 310\u2013323. Springer (2007)","DOI":"10.1007\/978-3-540-72792-7_24"},{"key":"269_CR22","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s12532-020-00194-3","volume":"13","author":"A Gleixner","year":"2021","unstructured":"Gleixner, A., Hendel, G., Gamrath, G., Achterberg, T., Bastubbe, M., Berthold, T., Christophel, P., Jarck, K., Koch, T., Linderoth, J., L\u00fcbbecke, M., Mittelmann, H.D., Ozyurt, D., Ralphs, T., Salvagnin, D., Shinano, Y.: MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. Math. Program. Comput. 13, 443\u2013490 (2021)","journal-title":"Math. Program. Comput."},{"key":"269_CR23","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1287\/ijoc.9.1.73","volume":"9","author":"J Gondzio","year":"1997","unstructured":"Gondzio, J.: Presolve analysis of linear programs prior to applying an interior point method. INFORMS J. Comput. 9, 73\u201391 (1997)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"269_CR24","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/s12532-021-00209-7","volume":"14","author":"G Hendel","year":"2022","unstructured":"Hendel, G.: Adaptive large neighborhood search for mixed integer programming. Math. Program. Comput. 14(1), 185\u2013221 (2022)","journal-title":"Math. Program. Comput."},{"issue":"4","key":"269_CR25","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1023\/A:1006350622830","volume":"24","author":"HH Hoos","year":"2000","unstructured":"Hoos, H.H., St\u00fctzle, T.: Local search algorithms for SAT: an empirical evaluation. J. Autom. Reason. 24(4), 421\u2013481 (2000)","journal-title":"J. Autom. Reason."},{"key":"269_CR26","unstructured":"IBM: ILOG CPLEX 12.10 User\u2019s Manual (2020)"},{"key":"269_CR27","unstructured":"Lin, P., Cai, S., Zou, M., Lin, J.: New characterizations and efficient local search for general integer linear programming (2023). https:\/\/arxiv.org\/abs\/2305.00188"},{"key":"269_CR28","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s12532-023-00234-8","volume":"15","author":"B Luteberget","year":"2023","unstructured":"Luteberget, B., Sartor, G.: Feasibility Jump: an LP-free Lagrangian MIP heuristic. Math. Program. Comput. 15, 365\u2013388 (2023)","journal-title":"Math. Program. Comput."},{"key":"269_CR29","doi-asserted-by":"crossref","unstructured":"Maros, I.: Computational Techniques of the Simplex Method. Kluwer Academic Publishers (2002)","DOI":"10.1007\/978-1-4615-0257-9"},{"key":"269_CR30","unstructured":"Mexi, G., Besan\u00e7on, M., Bolusani, S., Chmiela, A., Hoen, A., Gleixner, A.: Scylla: a matrix-free fix-propagate-and-project heuristic for mixed-integer optimization (2023). https:\/\/arxiv.org\/abs\/2307.03466"},{"key":"269_CR31","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: algorithms and Complexity. Dover (1982)"},{"key":"269_CR32","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s10107-006-0009-0","volume":"110","author":"J Patel","year":"2007","unstructured":"Patel, J., Chinneck, J.W.: Active-constraint variable ordering for faster feasibility of mixed integer linear programs. Math. Program. 110, 445\u2013474 (2007)","journal-title":"Math. Program."},{"issue":"8","key":"269_CR33","doi-asserted-by":"publisher","first-page":"1143","DOI":"10.1016\/j.cor.2010.10.025","volume":"38","author":"J Pryor","year":"2011","unstructured":"Pryor, J., Chinneck, J.W.: Faster integer-feasibility in mixed-integer linear programs by branching to force change. Comput. Oper. Res. 38(8), 1143\u20131152 (2011)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"269_CR34","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(4), 534\u2013541 (2007)","journal-title":"INFORMS J. Comput."},{"key":"269_CR35","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1287\/ijoc.6.4.445","volume":"6","author":"MWP Savelsbergh","year":"1994","unstructured":"Savelsbergh, M.W.P.: Preprocessing and probing for mixed integer programming problems. ORSA J. Comput. 6, 445\u2013454 (1994)","journal-title":"ORSA J. Comput."},{"key":"269_CR36","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: 40th annual symposium on foundations of computer science, pp. 410\u2013414. IEEE Press (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"269_CR37","unstructured":"Schulte, C.: Comparing trailing and copying for constraint programming. In: ICLP, pp. 275\u2013289 (1999)"},{"key":"269_CR38","unstructured":"Schulte, C.: Programming constraint services. Ph.D. thesis, Universit\u00e4t des Saarlandes, Naturwissenschaftlich-Technische Fakult\u00e4t I, Fachrichtung Informatik, Saarbr\u00fccken, Germany (2000)"},{"key":"269_CR39","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2005\/06\/P06006","author":"S Seitz","year":"2005","unstructured":"Seitz, S., Alava, M., Orponen, P.: Focused local search for random 3-satisfiability. J. Stat. Mech.: Theory Exp. (2005). https:\/\/doi.org\/10.1088\/1742-5468\/2005\/06\/P06006","journal-title":"J. Stat. Mech.: Theory Exp."},{"key":"269_CR40","unstructured":"Selman, B., Kautz, H.A., Cohen, B.: Noise strategies for improving local search. In: Proceedings of the twelfth AAAI national conference on artificial intelligence, pp. 337\u2013343. AAAI Press (1994)"},{"issue":"5","key":"269_CR41","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/s10732-009-9114-6","volume":"16","author":"C Wallace","year":"2010","unstructured":"Wallace, C.: ZI round, a MIP rounding heuristic. J. Heuristics 16(5), 715\u2013722 (2010)","journal-title":"J. Heuristics"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-024-00269-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-024-00269-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-024-00269-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,17]],"date-time":"2025-02-17T20:46:29Z","timestamp":1739825189000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-024-00269-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,7]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["269"],"URL":"https:\/\/doi.org\/10.1007\/s12532-024-00269-5","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,7]]},"assertion":[{"value":"15 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 October 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}