The Feasibility Pump. Fischetti, M., Glover, F., & Lodi, A. Mathematical Programming, 104(1):91–104, September, 2005. doi abstract bibtex In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min\cTx:Ax$≥$b,xjinteger $∀$j $∈$ \. Trivially, a feasible solution can be defined as a point x* $∈$ P:=\x:Ax$≥$b\ that is equal to its rounding , where the rounded point is defined by := x*jif j $∈$ and := x*jotherwise, and [$·$] represents scalar rounding to the nearest integer. Replacing ``equal'' with ``as close as possible'' relative to a suitable distance function $Δ$(x*, ), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP.
@article{fischetti05feasibility,
title = {The Feasibility Pump},
author = {Fischetti, Matteo and Glover, Fred and Lodi, Andrea},
year = {2005},
month = sep,
journal = {Mathematical Programming},
volume = {104},
number = {1},
pages = {91--104},
issn = {1436-4646},
doi = {10.1007/s10107-004-0570-3},
abstract = {In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min\{cTx:Ax{$\geq$}b,xjinteger {$\forall$}j {$\in$} \}. Trivially, a feasible solution can be defined as a point x* {$\in$} P:=\{x:Ax{$\geq$}b\} that is equal to its rounding , where the rounded point is defined by := x*jif j {$\in$} and := x*jotherwise, and [{$\cdot$}] represents scalar rounding to the nearest integer. Replacing ``equal'' with ``as close as possible'' relative to a suitable distance function {$\Delta$}(x*, ), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP.},
langid = {english},
file = {/Users/acosta/Documents/zotero files/Fischetti et al. - 2005 - The feasibility pump.pdf}
}
Downloads: 0
{"_id":"96LoLGE9egH3uBZvS","bibbaseid":"fischetti-glover-lodi-thefeasibilitypump-2005","authorIDs":["G95oAQQDbf3AqEmTB","KSQdWeDJjGbBo8G2T","WvauJnM2f2MC9dmWt","k7LaJZqXagaznaPKe","waDQsarscgfshSMhZ"],"author_short":["Fischetti, M.","Glover, F.","Lodi, A."],"bibdata":{"bibtype":"article","type":"article","title":"The Feasibility Pump","author":[{"propositions":[],"lastnames":["Fischetti"],"firstnames":["Matteo"],"suffixes":[]},{"propositions":[],"lastnames":["Glover"],"firstnames":["Fred"],"suffixes":[]},{"propositions":[],"lastnames":["Lodi"],"firstnames":["Andrea"],"suffixes":[]}],"year":"2005","month":"September","journal":"Mathematical Programming","volume":"104","number":"1","pages":"91–104","issn":"1436-4646","doi":"10.1007/s10107-004-0570-3","abstract":"In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min\\cTx:Ax$≥$b,xjinteger $∀$j $∈$ \\. Trivially, a feasible solution can be defined as a point x* $∈$ P:=\\x:Ax$≥$b\\ that is equal to its rounding , where the rounded point is defined by := x*jif j $∈$ and := x*jotherwise, and [$·$] represents scalar rounding to the nearest integer. Replacing ``equal'' with ``as close as possible'' relative to a suitable distance function $Δ$(x*, ), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP.","langid":"english","file":"/Users/acosta/Documents/zotero files/Fischetti et al. - 2005 - The feasibility pump.pdf","bibtex":"@article{fischetti05feasibility,\n title = {The Feasibility Pump},\n author = {Fischetti, Matteo and Glover, Fred and Lodi, Andrea},\n year = {2005},\n month = sep,\n journal = {Mathematical Programming},\n volume = {104},\n number = {1},\n pages = {91--104},\n issn = {1436-4646},\n doi = {10.1007/s10107-004-0570-3},\n abstract = {In this paper we consider the NP-hard problem of finding a feasible solution (if any exists) for a generic MIP problem of the form min\\{cTx:Ax{$\\geq$}b,xjinteger {$\\forall$}j {$\\in$} \\}. Trivially, a feasible solution can be defined as a point x* {$\\in$} P:=\\{x:Ax{$\\geq$}b\\} that is equal to its rounding , where the rounded point is defined by := x*jif j {$\\in$} and := x*jotherwise, and [{$\\cdot$}] represents scalar rounding to the nearest integer. Replacing ``equal'' with ``as close as possible'' relative to a suitable distance function {$\\Delta$}(x*, ), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP.},\n langid = {english},\n file = {/Users/acosta/Documents/zotero files/Fischetti et al. - 2005 - The feasibility pump.pdf}\n}\n\n","author_short":["Fischetti, M.","Glover, F.","Lodi, A."],"key":"fischetti05feasibility","id":"fischetti05feasibility","bibbaseid":"fischetti-glover-lodi-thefeasibilitypump-2005","role":"author","urls":{},"metadata":{"authorlinks":{}}},"bibtype":"article","biburl":"https://www.dropbox.com/s/6qxz2tlaz2bi6av/costaam.bib?dl=1","creationDate":"2020-05-11T16:15:11.426Z","downloads":0,"keywords":[],"search_terms":["feasibility","pump","fischetti","glover","lodi"],"title":"The Feasibility Pump","year":2005,"dataSources":["pqA4PfX5cEBnCgHnj","C8ZTSgdcqKrDKQsFr"]}