The feasibility pump |
| |
Authors: | Matteo Fischetti Fred Glover Andrea Lodi |
| |
Affiliation: | (1) DEI, University of Padova, Via Gradenigo 6/A, 35100 Padova, Italy;(2) Leeds School of Business, University of Colorado at Boulder, 419 UCB, Boulder, CO 80309-0419, USA;(3) DEIS, University of Bologna, Viale Risorgimento 2, 40136 Bologna, Italy |
| |
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,xj integer ∀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*j if j ∈ and := x*j otherwise, 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.We start from any x* ∈ P, and define its rounding . At each FP iteration we look for a point x* ∈ P that is as close as possible to the current by solving the problem min {Δ(x, ): x ∈ P}. Assuming Δ(x, ) is chosen appropriately, this is an easily solvable LP problem. If Δ(x*, )=0, then x* is a feasible MIP solution and we are done. Otherwise, we replace by the rounding of x*, and repeat.We report computational results on a set of 83 difficult 0-1 MIPs, using the commercial software ILOG-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. |
| |
Keywords: | 90C06 90C10 90C11 90C27 90C59 |
本文献已被 SpringerLink 等数据库收录! |
|