D. Baena Mirabete, J. Castro Pérez
The feasibility pump (FP) of Fischetti, Glover and Lodi has proved to be a successful heuristic for finding feasible solutions of MILPs. Briefly, FP alternates between two sequences of points: one of feasible solutions for the relaxed problem (but not integer), and another of integer points (but not feasible for the relaxed problem). Integer points are obtained from the feasible ones by some rounding procedure. This work extends FP, such that the integer point is obtained by rounding a point on the (feasible) segment between the computed feasible point and the analytic center for the relaxed linear problem. When the selected point to be rounded is one particular endpoint of the segment, this analytic center FP (AC-FP) variant behaves as the standard FP. AC-FP is also compared with the recent analytic center feasibility method (ACFM). Computational results show that AC-FP may outperform FP and ACFM in some MILP instances, either in time or quality of the solution.
Palabras clave: analytic center, interior-point methods , mixed-integer linear programming , feasibility problem , primal heuristics
Programado
JB6 Optimización matemática
19 de abril de 2012 10:30
Sala Roma I
