The feasibility pump
成果类型：
Article
署名作者：
Fischetti, M; Glover, F; Lodi, A
署名单位：
University of Padua; University of Colorado System; University of Colorado Boulder; University of Bologna
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-004-0570-3
发表日期：
2005
页码：
91-104
关键词：
摘要：
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{c(T) x : Ax >= b, x(j) integer for all j is an element of I}. Trivially, a feasible solution can be defined as a point x*is an element of P := {x : Ax >= b} that is equal to its rounding (x) over tilde, where the rounded point (x) over tilde x is defined by (x) over tilde (j) := [ x*(j)] if j is an element of I and (x) over tilde (j)* := x(j)* otherwise, and [.] represents scalar rounding to the nearest integer. Replacing equal with as close as possible relative to a suitable distance function Delta( x*, (x) over tilde), suggests the following Feasibility Pump (FP) heuristic for finding a feasible solution of a given MIP. We start from any x* is an element of P, and define its rounding (x) over tilde. At each FP iteration we look for a point x* is an element of P that is as close as possible to the current (x) over tilde by solving the problem min{Delta( x, (x) over tilde) : x is an element of P}. Assuming Delta( x, (x) over tilde) is chosen appropriately, this is an easily solvable LP problem. If Delta( x*, (x) over tilde) = 0, then x* is a feasible MIP solution and we are done. Otherwise, we replace (x) over tilde by the rounding of x*, and repeat. We report computational results on a set of 83 difficult 0-1 MIPs, using the commercial software I LOG-Cplex 8.1 as a benchmark. The outcome is that FP, in spite of its simple foundation, proves competitive with ILOG-Cplex both in terms of speed and quality of the first solution delivered. Interestingly, ILOG-Cplex could not find any feasible solution at the root node for 19 problems in our test-bed, whereas FP was unsuccessful in just 3 cases.