{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:39:02Z","timestamp":1740145142774,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T00:00:00Z","timestamp":1686096000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004837","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["RTI2018-097580-B-I00"],"award-info":[{"award-number":["RTI2018-097580-B-I00"]}],"id":[{"id":"10.13039\/501100004837","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100014374","name":"Universitat Polit\u00e8cnica de Catalunya","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100014374","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>As a heuristic for obtaining feasible points of mixed integer linear problems, the feasibility pump (FP) generates two sequences of points: one of feasible solutions for the relaxed linear problem; and another of integer points obtained by rounding the linear solutions. In a previous work, the present authors proposed a variant of FP, named analytic center FP, which obtains integer solutions by rounding points in the segment between the linear solution and the analytic center of the polyhedron of the relaxed problem. This work introduces a new FP variant that replaces the analytic center with the Chebyshev center. Two of the benefits of using the Chebyshev center are: (i) it requires the solution of a linear optimization problem (unlike the analytic center, which involves a convex nonlinear optimization problem for its exact solution); and (ii) it is invariant to redundant constraints (unlike the analytic center, which may not be well centered within the polyhedron for problems with highly rank-deficient matrices). The computational results obtained with a set of more than 200 MIPLIB2003 and MIPLIB2010 instances show that the Chebyshev center FP is competitive and can serve as an alternative to other FP variants.<\/jats:p>","DOI":"10.1007\/s11590-023-02018-4","type":"journal-article","created":{"date-parts":[[2023,6,7]],"date-time":"2023-06-07T08:02:41Z","timestamp":1686124961000},"page":"1757-1790","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Chebyshev center as an alternative to the analytic center in the feasibility pump"],"prefix":"10.1007","volume":"17","author":[{"given":"Daniel","family":"Baena","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3573-4568","authenticated-orcid":false,"given":"Jordi","family":"Castro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,7]]},"reference":[{"key":"2018_CR1","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.disopt.2006.10.004","volume":"4","author":"T Achterberg","year":"2007","unstructured":"Achterberg, T., Berthold, T.: Improving the feasibility pump. Discrete Optim. 4, 77\u201386 (2007). https:\/\/doi.org\/10.1016\/j.disopt.2006.10.004","journal-title":"Discrete Optim."},{"key":"2018_CR2","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/j.orl.2005.07.009","volume":"34","author":"T Achterberg","year":"2006","unstructured":"Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34, 361\u2013372 (2006). https:\/\/doi.org\/10.1016\/j.orl.2005.07.009","journal-title":"Oper. Res. Lett."},{"key":"2018_CR3","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/j.orl.2011.07.005","volume":"39","author":"D Baena","year":"2011","unstructured":"Baena, D., Castro, J.: Using the analytic center in the feasibility pump. Oper. Res. Lett. 39, 310\u2013317 (2011). https:\/\/doi.org\/10.1016\/j.orl.2011.07.005","journal-title":"Oper. Res. Lett."},{"key":"2018_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s11590-016-1046-0","volume":"11","author":"P Belotti","year":"2017","unstructured":"Belotti, P., Berthold, T.: Three ideas for a feasibility pump for nonconvex MINLP. Optim. Lett. 11, 3\u201315 (2017). https:\/\/doi.org\/10.1007\/s11590-016-1046-0","journal-title":"Optim. Lett."},{"key":"2018_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.disopt.2006.10.001","volume":"4","author":"L Bertacco","year":"2007","unstructured":"Bertacco, L., Fischetti, M., Lodi, A.: A feasibility pump heuristic for general mixed-integer problems. Discrete Optim. 4, 63\u201376 (2007). https:\/\/doi.org\/10.1016\/j.disopt.2006.10.001","journal-title":"Discrete Optim."},{"key":"2018_CR6","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s12532-014-0068-9","volume":"6","author":"NL Boland","year":"2014","unstructured":"Boland, N.L., Eberhard, A.C., Engineer, F.G., Fischetti, M., Savelsbergh, M.W.P., Tsoukalas, A.: Boosting the feasibility pump. Math. Program. Comput. 6, 255\u2013279 (2014). https:\/\/doi.org\/10.1007\/s12532-014-0068-9","journal-title":"Math. Program. Comput."},{"key":"2018_CR7","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s10107-008-0212-2","volume":"119","author":"P Bonami","year":"2009","unstructured":"Bonami, P., Cornu\u00e9jols, G., Lodi, A., Margot, F.: A feasibility pump for mixed integer nonlinear programs. Math Program 119, 331\u2013352 (2009). https:\/\/doi.org\/10.1007\/s10107-008-0212-2","journal-title":"Math Program"},{"key":"2018_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambidge University Press, Cambridge (2004). https:\/\/doi.org\/10.1017\/CBO9780511804441"},{"key":"2018_CR9","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s10107-012-0608-x","volume":"136","author":"C D\u2019Ambrosio","year":"2012","unstructured":"D\u2019Ambrosio, C., Frangioni, A., Liberti, L., Lodi, A.: A storm of feasibility pumps for nonconvex MINLP. Math. Program. 136, 375\u2013402 (2012). https:\/\/doi.org\/10.1007\/s10107-012-0608-x","journal-title":"Math. Program."},{"key":"2018_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-006-0044-x","volume":"113","author":"A Deza","year":"2008","unstructured":"Deza, A., Nematollahi, E., Terlaky, T.: How good are interior point methods? Klee\u2013Minty cubes tighten iteration-complexity bounds. Math. Program. 113, 1\u201314 (2008). https:\/\/doi.org\/10.1007\/s10107-006-0044-x","journal-title":"Math. Program."},{"key":"2018_CR11","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s12532-011-0025-9","volume":"3","author":"T Koch","year":"2011","unstructured":"Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K.: MIPLIB 2010. Mixed integer programming library version 5. Math. Program. Comput. 3, 103 (2011). https:\/\/doi.org\/10.1007\/s12532-011-0025-9","journal-title":"Math. Program. Comput."},{"key":"2018_CR12","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, 91\u2013104 (2005). https:\/\/doi.org\/10.1007\/s10107-004-0570-3","journal-title":"Math Program"},{"key":"2018_CR13","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, 201\u2013222 (2009). https:\/\/doi.org\/10.1007\/s12532-009-0007-3","journal-title":"Math Program Comput"},{"key":"2018_CR14","doi-asserted-by":"publisher","first-page":"1335","DOI":"10.1016\/j.cor.2010.12.008","volume":"38","author":"J Naoum-Sawaya","year":"2011","unstructured":"Naoum-Sawaya, J., Elhedhli, S.: An interior point cutting plane heuristic for mixed integer programming. Comput Oper Res 38, 1335\u20131341 (2011). https:\/\/doi.org\/10.1016\/j.cor.2010.12.008","journal-title":"Comput Oper Res"},{"key":"2018_CR15","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032701","volume-title":"Interior Point Algorithms. Theory and Analysis","author":"Y Ye","year":"1997","unstructured":"Ye, Y.: Interior Point Algorithms. Theory and Analysis. Wiley, New York (1997)"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02018-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-023-02018-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-023-02018-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,20]],"date-time":"2023-09-20T08:21:32Z","timestamp":1695198092000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-023-02018-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,7]]},"references-count":15,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["2018"],"URL":"https:\/\/doi.org\/10.1007\/s11590-023-02018-4","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2023,6,7]]},"assertion":[{"value":"27 June 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}