{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:41Z","timestamp":1787337521003,"version":"build-2736575974"},"reference-count":20,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI 1562578"],"award-info":[{"award-number":["CMMI 1562578"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI 1149400"],"award-info":[{"award-number":["CMMI 1149400"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Feasibility pump is a successful primal heuristic for mixed-integer linear programs. The algorithm consists of three main components: rounding fractional solution to a mixed-integer one, projection of infeasible solutions to the linear programming relaxation, and a randomization step used when the algorithm stalls. While many generalizations and improvements to the original Feasibility Pump have been proposed, they mainly focus on the rounding and projection steps. We start a more in-depth study of the randomization step in Feasibility Pump. For that, we propose a new randomization step based on the WalkSAT algorithm for solving instances of the Boolean satisfiability problem. First, we provide theoretical analyses for instances with disjoint equality constraints that show the potential of this randomization step; to the best of our knowledge, this is the first time any theoretical analysis of the running-time of Feasibility Pump or its variants has been conducted, even for a special class of instances. Moreover, we propose a practical version of a new randomization step, and incorporate it into a state-of-the-art Feasibility Pump code. Our experiments suggests that this simple-to-implement modification consistently dominates the standard randomization previously used.<\/jats:p>","DOI":"10.1137\/16m1095962","type":"journal-article","created":{"date-parts":[[2018,2,6]],"date-time":"2018-02-06T12:33:02Z","timestamp":1517920382000},"page":"355-378","source":"Crossref","is-referenced-by-count":6,"title":["Improving the Randomization Step in Feasibility Pump"],"prefix":"10.1137","volume":"28","author":[{"given":"Santanu S.","family":"Dey","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andres","family":"Iroume","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Molinaro","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Domenico","family":"Salvagnin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,2,6]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.10.004"},{"key":"atypb2","unstructured":"T. Achterberg,\n                      Constraint Integer Programming\n                      , Ph.D. thesis, Technische Universita\u0308t Berlin, Berlin, 2007."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-008-0212-2"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-014-0068-9"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/110823596"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.10.001"},{"key":"atypb7","first-page":"350","author":"D'Ambrosio C.","year":"2010","journal-title":"Berlin"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0608-x"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0570-3"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"M. Fischetti and A. Lodi,\n                      Heuristics in mixed integer programming\n                      , Wiley Encyclopedia of Operations Research and Management Science, Wiley, Hoboken, NJ, 2011.","DOI":"10.1002\/9780470400531.eorms0376"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-009-0007-3"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/16M1069687"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-011-0025-9"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(92)90007-K"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher and E.Upfal,\n                      Probability and Computing: Randomized Algorithms and Probabilistic Analysis\n                      , Cambridge University Press, New York, 2005.","DOI":"10.1017\/CBO9780511813603"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou,\n                      On selecting a satisfying truth assignment\n                      , in FOCS, IEEE Computer Society, Los Alamitos, CA, pp. 163-169, 1991.","DOI":"10.1109\/SFCS.1991.185365"},{"key":"atypb19","unstructured":"A. Schrijver,\n                      Theory of Linear and Integer Programming\n                      , Wiley, New York, 1986."},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"U. Scho\u0308ning,\n                      A probabilistic algorithm for k-sat and constraint satisfaction problems\n                      , in Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 1999, New York, IEEE Computer Society, Los Alamitos, CA, 1999, pp. 410-414.","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/110855351"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"H. Thorisson,\n                      Coupling, Stationarity, and Regeneration\n                      , Springer, Berlin, 2000.","DOI":"10.1007\/978-1-4612-1236-2"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1095962","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:15:14Z","timestamp":1787336114000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1095962"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1095962"],"URL":"https:\/\/doi.org\/10.1137\/16m1095962","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}